POJ 2180 Bale Figures
とても頭のわるいソースになった。
英語読めな過ぎて「最初のところから25以上離れない」みたいな重要なところを読み飛ばしており仕方なくsetを使っていた。解き終えてからほかの人のブログで知った。
set<string>にしたらTLEになったので仕方なくpair使いまわした。
コメントとか消すのめんどくさいからそのまんま
#include <utility> #include <sstream> #include <cstdio> #include <string> #include <set> #include <iostream> using namespace std; typedef pair<int,int> P; typedef pair<int,P> PP; int ch[7][3]; int d[25003][3]; int main(){ ch[0][0] = 1; ch[1][0] = -1; ch[2][1] = 1; ch[3][1] = -1; ch[4][2] = 1; ch[5][2] = -1; int n; scanf("%d",&n); int ans = 6*n; set<PP> s; // s.insert("0.0.0"); s.insert(PP(0,P(0,0))); n--; int min=0; int zyu = 0; int k = 1; int i = 1; while(n--){ i++; int q; char p; // cin >> q >> p; scanf("%d %c",&q,&p); int a0=d[q][0],a1=d[q][1],a2=d[q][2]; switch(p){ case 'L': a1++; break; case 'R': a1--; break; case 'F': a2++; break; case 'B': a2--; break; case 'O': a0++; break; case 'U': a0--; break; } PP tmp; if(min == a0){ k++; }else if(a0 < min){ k = 1; min = a0; } // cout << tmp<<endl; tmp = PP(a0,P(a1,a2)); set<PP>::iterator it=s.find(tmp); if(it != s.end()){ printf("-1\n"); return 0; } s.insert(tmp); d[i][0] = a0; d[i][1] = a1; d[i][2] = a2; for(int i = 0;i < 6;i++){ PP c = PP(a0+ch[i][0],P(a1+ch[i][1],a2+ch[i][2])); // cout << ":" << c; set<PP>::iterator ite = s.find(c); if(ite != s.end()) zyu++; } // cout << "zyu:" << zyu << endl; } // cout << "zyu:" << zyu << endl; // cout << "k:" << k << endl; ans -= 2*zyu; ans -= k; printf("%d\n",ans); return 0; }