POJ2180BaleFigures

2017/12/05

とても頭のわるいソースになった。

英語読めな過ぎて「最初のところから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
");
			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
",ans);

	return 0;

}