ICPC2014 WF Problem A

_solution.cpp

//
// includes and macros
//
#define rep(i,n) for(int i = 0; i < n; i++)

int main(){
	int n;
	cin >> n;
	//printf("%d\n",n);
	if(n%4 == 0){
		int pre = -1, l = 3, r = n*2-2;
		rep(i,n/4){
			printf("%d to %d\n",r,pre);
			printf("%d to %d\n",l,r);
			pre = l;
			l += 4; r -= 4;
		}
		l = pre-3; r = pre+4;
		rep(i,n/4){
			printf("%d to %d\n",l,pre);
			printf("%d to %d\n",r,l);
			pre = r;
			l -= 4; r += 4;
		}
	} else if(n%4 == 1){
		int pre = -1, l = 3, r = n*2-2;
		rep(i,n/4){
			printf("%d to %d\n",r,pre);
			printf("%d to %d\n",l,r);
			pre = l;
			l += 4; r -= 4;
		}
		printf("%d to %d\n",pre+3,pre);
		l = pre-3; r = pre+6; pre = pre+3;
		rep(i,n/4){
			printf("%d to %d\n",l,pre);
			printf("%d to %d\n",r,l);
			pre = r;
			l -= 4; r += 4;
		}
	} else if(n%4 == 2){
		int pre = -1, l = 3, r = n*2-2;
		rep(i,n/4-1){
			printf("%d to %d\n",r,pre);
			printf("%d to %d\n",l,r);
			pre = l;
			l += 4; r -= 4;
		}
		printf("%d to %d\n",r,pre);
		printf("%d to %d\n",r-3,r);
		printf("%d to %d\n",l-1,r-3);
		printf("%d to %d\n",r-4,l-1);
		pre = r-4; l = l-3; r = r+1;
		rep(i,n/4){
			printf("%d to %d\n",l,pre);
			printf("%d to %d\n",r,l);
			pre = r;
			l -= 4; r += 4;
		}
	} else {
		int pre = -1, l = 3, r = n*2-8;
		rep(i,n/4){
			printf("%d to %d\n",r,pre);
			printf("%d to %d\n",l,r);
			pre = l;
			l += 4; r -= 4;
		}
		printf("%d to %d\n",n*2-4,pre);
		printf("%d to %d\n",n*2-1,n*2-4);
		printf("%d to %d\n",pre+4,-3);
		l = pre-3; r = pre+8; pre = pre+4;
		rep(i,n/4){
			printf("%d to %d\n",l,pre);
			printf("%d to %d\n",r,l);
			pre = r;
			l -= 4; r += 4;
		}
	}
	
	return 0;
}

checker.cpp

int n;
vi d;

inline void pri(){
	rep(i,sz(d)) printf("%d",d[i]);
	puts("");
}

bool check(){
	int now = 0, cnt = 0;
	rep(i,sz(d)){
		if(now != d[i]){
			++cnt;
			now = d[i];
		}
	}
	if(now) ++cnt;
	if(cnt > 3) return false;
	return true;
}

int main(){
	int n;
	cin >> n;
	d = vi(n*2+4,0);
	rep(i,n*2) d[i+4] = (i&1)+1;
	rep(i,n){
		int a, b; string s;
		cin >> a >> s >> b;
		if(d[a+3] == 0 || d[a+3+1] == 0){
			pri();
			printf("invalid : %d %d\n",a,b);
			return 0;
		}
		if(d[b+3] != 0 || d[b+3+1] != 0){
			pri();
			printf("unexpected : %d %d\n",a,b);
			return 0;
		}
		swap(d[a+3],d[b+3]);
		swap(d[a+3+1],d[b+3+1]);
		pri();
	}
	pri();
	puts(check()?"OK":"NG");
	
	return 0;
}

simulate.cpp

#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
#define sz(x) (int)(x).size()
typedef vector<int> vi;
typedef pair<vi,int> P;

int n;
vi d;
set<P> s;

inline void pri(){
	rep(i,sz(d)) printf("%d",d[i]);
	puts("");
}

bool dfs(int dep){
	if(s.count(P(d,dep))) return false;
	s.insert(P(d,dep));
	if(dep == 0){
		int now = 0, cnt = 0;
		rep(i,sz(d)){
			if(now != d[i]){
				++cnt;
				now = d[i];
			}
		}
		if(now) ++cnt;
		if(cnt > 3) return false;
		pri();
		return true;
	}
	vi as, bs;
	rep(i,sz(d)-1){
		if(d[i] && d[i+1]) as.pb(i);
		if(!d[i] && !d[i+1]) bs.pb(i);
	}
	for(int a : as){
		for(int b : bs){
			swap(d[a],d[b]); swap(d[a+1],d[b+1]);
			bool res = dfs(dep-1);
			swap(d[a],d[b]); swap(d[a+1],d[b+1]);
			if(res){
				pri();
				return true;
			}
		}
	}
	return false;
} 

int main(){
	cin >> n;
	d = vi(n*2+4,0);
	rep(i,n*2) d[i+4] = (i&1)+1;
	dfs(n);
	
	return 0;
}