Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2012-05-24

AOJ 2158 Double Sorting

| 02:05 | AOJ 2158 Double Sorting - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - AOJ 2158 Double Sorting - Wrong Answer -- japlj AOJ 2158 Double Sorting - Wrong Answer -- japlj のブックマークコメント

A*てきとうに書いたら間に合わなかったので嘘枝刈り~

MLE -> MLE -> WA -> WA -> MLE -> AC


Submitデバッグで二分探索する人間の屑

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<queue>

using namespace std;

typedef long long Int;

struct state {
  Int st;
  int cost, heur1, heur2;
  
  int score() const {
    return cost + max((heur1+1)/2, (heur2+5)/6);
  }
};

bool operator < (const state& a, const state& b)
{
  return a.score() != b.score() ? a.score() > b.score() : a.cost < b.cost;
}

struct cmp_by_state {
  bool operator () (const state& a, const state& b) {
    return a.st < b.st;
  }
};

#define pos(i) ((i)*3)
#define mask(i) (7LL<<pos(i))
#define at(st, i) (((st) & mask(i)) >> pos(i))
#define swp(st, i, j) (((st) & ~(mask(i)|mask(j))) | (at(st,j)<<pos(i)) | (at(st,i)<<pos(j)))
#define check(st, b) (at(st, 2*(b)) > at(st, 2*(b)+1) ? swp(st, 2*(b), 2*(b)+1) : (st))
#define h2(x, y) (((x)==(y)) ? 1 : ((x)>(y) ? 2 : 0))

int N;

int a_star(Int s, Int t)
{
  state first;
  first.st = s;
  first.cost = first.heur1 = first.heur2 = 0;
  
  for(int i=0; i<N; ++i)
    first.st = check(first.st, i);
  
  for(int i=0; i<2*N; ++i)
    first.heur1 += abs(at(first.st, i) - i/2);
  
  for(int i=0; i<2*N; ++i)
    for(int j=i+1; j<2*N; ++j)
      if(i/2 != j/2)
        first.heur2 += h2(at(first.st, i), at(first.st, j));
        
  priority_queue<state> Q;
  map<state, int, cmp_by_state> proc, done;
  Q.push(first);
  proc[first] = first.score();
  Int cA = 0;
  while(!Q.empty()) {
    state n = Q.top(); Q.pop();
    if((++cA) == 14000) return n.score()+1;
    if(n.st == t) return n.cost;
    if(proc.find(n) != proc.end()) proc.erase(n);
    if(done.find(n) != done.end()) continue;
    done[n] = n.score();
    for(int i=0; i<2*N-2; ++i) {
      for(int j=(i%2)?(i+1):(i+2); j/2-i/2==1; ++j) {
        state next = n;
        
        next.heur1 -= abs(at(n.st, i) - i/2) + abs(at(n.st, j) - j/2);
        next.heur1 += abs(at(n.st, i) - j/2) + abs(at(n.st, j) - i/2);
        
        int p = at(n.st, i), q = at(n.st, j);
        int r = at(n.st, i^1), s = at(n.st, j^1);
        next.heur2 -= h2(p, q) + h2(p, s) + h2(r, q);
        next.heur2 += h2(q, p) + h2(q, s) + h2(r, p);
        
        next.st = swp(n.st, i, j);
        next.st = check(next.st, i/2);
        next.st = check(next.st, j/2);
        
        next.cost++;
        
        map<state, int, cmp_by_state>::iterator open = proc.find(next), close = done.find(next);
        bool open_p = (open != proc.end()), close_p = (close != done.end());
        if((!open_p && !close_p)
          || (open_p && open->first.score() > next.score())
          || (close->first.score() > next.score())) {
          Q.push(next);
          proc[next] = next.score();
          if(done.find(next) != done.end()) done.erase(next);
        }
      }
    }
  }
  
  return -1;
}

int main()
{
  while(scanf("%d", &N), N) {
    Int f = 0, goal = 0;
    for(int i=0, t; i<2*N; ++i) {
      scanf("%d", &t);
      f |= (Int)(t-1) << pos(i);
      goal |= (Int)(i>>1) << pos(i);
    }
    printf("%d\n", a_star(f, goal));
  }
  return 0;
}

PawasPawas2012/11/16 17:25If you're looking to buy these articles make it way eaeisr.

nmxraupufnmxraupuf2012/11/16 22:34YqV87z <a href="http://czvuhitduwfv.com/">czvuhitduwfv</a>

rxlymtrxlymt2012/11/18 20:00gqAnxT <a href="http://yvpuhmsldnjl.com/">yvpuhmsldnjl</a>

fmiiewxtvffmiiewxtvf2014/03/19 17:08yxzdbupqdpefs, <a href="http://www.shozpmhyjw.com/">osirzvcwys</a> , [url=http://www.zprwszrkru.com/]ulbjtpxvox[/url], http://www.fpcxcxpqba.com/ osirzvcwys

KelkadyKelkady2019/09/26 03:08Viagra Cialis Vendita Generic Viagra Overnight Delivery Generico Levitra 10 Mg <a href=http://etrobax.com>cialis overnight shipping from usa</a> Viagra Plus Uses For Amoxicillin Dadha Pharmacy

 |