SRM 474 :: DIV2

250 : system test pass
500 : failed system test
1000 : opened

500
いきなり500から開いて解く方針に切り替え。
N次元なのにNが10^9だと…、ビット演算さようなら。
どうしたらいいのこれ。座標で記録するのは無理だし…うーん。
移動が+と-の2種類しかない、もしかして移動状態を記録すればいいのでは？
適当に紙に書き出す。
(132,+) --> {(132,+)}
(51717,+) --> {(132,+),(51717,+)}
(620,+) --> {(132,+),(51717,+),(620,+)}
(3... ,+) --> {(132,+),(51717,+),(620,+),(3... ,+)}
(620,-) --> {(132,+),(51717,+),(3... ,+)}
(51717,-) --> {(132,+),(3... ,+)}
(3... ,-) --> {(132,+)}　<--同じ状態が出てくる＝同じ場所。it is NOT VALID.
これでいいんじゃね？
set< vector< pair > >　で移動状態を記録すればいい。
書く、バグ発生、初期状態のことすっかり忘れてた。
適当に修正、さらにバグ、え？
適当に修正、おｋ。Submit.

200
substrと+の連結でいいや。
あれ、substrの動作が不安…。
修正、なんか合ってるっぽい？　Submit.

そして。
500落ちる＼(^o^)／
あるぇー、考え方間違ってたかな？…
vector< pair >　sortせずにsetに入れてた…。
同じ状態でも、要素の順番が違えば異なるものとして判定されちゃうよ＼(^o^)／
orz

250

struct PalindromesCount
{
  int count(string A, string B){
    int ret = 0;
    string str1 = A+B;
    string str2 = B+A;
    string rstr1 = string(str1.rbegin(), str1.rend());
    string rstr2 = string(str2.rbegin(), str2.rend());
    if( str1 == rstr1 )ret++;
    if( str2 == rstr2 )ret++;
    for(int i=1; i<A.size(); i++){
      string str = A.substr(0,i) + B + A.substr(i,A.size());
      string rstr = string( str.rbegin(), str.rend() );
      if( str==rstr )ret++;
    }
    return ret;
  }
};

500

struct RouteIntersection
{
  string isValid(int N, vector <int> coords, string moves){
    set< vector< pair<int,char> > > s;
    
    vector< pair<int,char> > t;
    REP(i,coords.size()){
      char mov;
      if( moves[i]=='+' )mov='-';
      else               mov='+';
      pair<int,char> p(coords[i],mov);
      int j;
      if( t.size()==0 ){
        t.push_back( make_pair(coords[i],moves[i]) );
      }else{
        int f = 0;
        for(j=0; j<t.size(); j++){
          if( t[j]==p ){
            t.erase( t.begin()+j );
            f = 1;
            break;
          }
        }
        if( t.size()>0 && !f ){
          t.push_back( make_pair(coords[i],moves[i]) );
        }else if( t.size()==0 ){
          return "NOT VALID";
        }
      }
      sort( all(t) );
      if( s.find( t ) == s.end() ){
        s.insert( t );
      }else{
        return "NOT VALID";
      }
    }
    return "VALID";
  }
};