oj.uz

Submission #26313

# Submission time Handle Problem Language Result Execution time Memory
26313 2017-06-29T07:06:10 Z 윤교준(#1105) Trapezi (COI17_trapezi) C++11
100 / 100
 9 ms 411648 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <tuple>
#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MAXN (44)
#define MAXK (1048576)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int chk[MAXN][MAXK], chkn;
bool d[MAXN][MAXK];
int Ans[MAXN][MAXN], Ansn;
int GA[MAXN][MAXN];
char str[MAXN][MAXN];
int spkey[MAXN];
int whf[MAXN][MAXK];
int N;

int VKchk[MAXK], VKchkn;
void f(vector<int>& VK, int i, int key, int mk, int j) {
	if((spkey[i+1] | mk) ^ spkey[i+1]) return;
	if(key < (1<<j)) {
		if(VKchk[spkey[i+1] ^ mk] == VKchkn) return;
		VKchk[spkey[i+1] ^ mk] = VKchkn;
		VK.pb(spkey[i+1] ^ mk);
		return;
	}
	if(chk[j][mk] == chkn) return; chk[j][mk] = chkn;
	if((key | (1<<j)) ^ key) { f(VK, i, key, mk, j+1); return; }
	if(((i+j)&1) == (N&1)) {
		if(j && ((mk | (1<<(j-1))) ^ mk) && ((mk | (1<<j)) ^ mk)
				&& !((spkey[i+1] | (1<<(j-1))) ^ spkey[i+1])
				&& !((spkey[i+1] | (1<<j)) ^ spkey[i+1])) f(VK, i, key, mk | (1<<(j-1)) | (1<<j), j+1);
		if(((mk | (1<<j)) ^ mk) && ((mk | (1<<(j+1))) ^ mk)
				&& !((spkey[i+1] | (1<<j)) ^ spkey[i+1]) && !((spkey[i+1] | (1<<(j+1))) ^ spkey[i+1]))
			f(VK, i, key, mk | (1<<j) | (1<<(j+1)), j+1);
		if(!((key | (1<<(j+1))) ^ key) && ((mk | (1<<j)) ^ mk) && !((spkey[i+1] | (1<<j)) ^ spkey[i+1]))
			f(VK, i, key, mk | (1<<j), j+2);
	} else {
		if(!((key | (1<<(j+1))) ^ key) && ((mk | (1<<(j+1))) ^ mk) && !((spkey[i+1] | (1<<(j+1))) ^ spkey[i+1]))
			f(VK, i, key, mk | (1<<(j+1)), j+2);
	}
	if(!((key | (1<<(j+1))) ^ key) && !((key | (1<<(j+2))) ^ key)) f(VK, i, key, mk, j+3);
}
bool g(int i, int key) {
	if(i == 2*N+1) return !key;
	if(d[i][key]) return false; d[i][key] = true;
	if(!key) {
		if(g(i+1, spkey[i+1])) {
			whf[i][key] = spkey[i+1];
			return true;
		}
		return false;
	}
	vector<int> VK;
	chkn++; VKchkn++; clv(VK); f(VK, i, key, 0, 0);
	for(int v : VK) {
		if(g(i+1, v)) {
			whf[i][key] = v;
			return true;
		}
	}
	return false;
}
bool ff(int i, int key, int dk, int mk, int j) {
	if(key < (1<<j)) return true;
	if(chk[j][mk] == chkn) return false; chk[j][mk] = chkn;
	if((key | (1<<j)) ^ key) return ff(i, key, dk, mk, j+1);
	if(((i+j)&1) == (N&1)) {
		if(j && ((mk | (1<<(j-1))) ^ mk) && ((mk | (1<<j)) ^ mk)
				&& !((dk | (1<<(j-1))) ^ dk)
				&& !((dk | (1<<j)) ^ dk)) {
			Ansn++; Ans[i][j] = Ans[i+1][j-1] = Ans[i+1][j] = Ansn;
			if(ff(i, key, dk, mk | (1<<(j-1)) | (1<<j), j+1)) return true;
			Ansn--; Ans[i][j] = Ans[i+1][j-1] = Ans[i+1][j] = 0;
		}
		if(((mk | (1<<j)) ^ mk) && ((mk | (1<<(j+1))) ^ mk)
				&& !((dk | (1<<j)) ^ dk) && !((dk | (1<<(j+1))) ^ dk)) {
			Ansn++; Ans[i][j] = Ans[i+1][j] = Ans[i+1][j+1] = Ansn;
			if(ff(i, key, dk, mk | (1<<j) | (1<<(j+1)), j+1)) return true;
			Ansn--; Ans[i][j] = Ans[i+1][j] = Ans[i+1][j+1] = 0;
		}
		if(!((key | (1<<(j+1))) ^ key) && ((mk | (1<<j)) ^ mk) && !((dk | (1<<j)) ^ dk)) {
			Ansn++; Ans[i][j] = Ans[i][j+1] = Ans[i+1][j] = Ansn;
			if(ff(i, key, dk, mk | (1<<j), j+2)) return true;
			Ansn--; Ans[i][j] = Ans[i][j+1] = Ans[i+1][j] = 0;
		}
	} else {
		if(!((key | (1<<(j+1))) ^ key) && ((mk | (1<<(j+1))) ^ mk) && !((dk | (1<<(j+1))) ^ dk)) {
			Ansn++; Ans[i][j] = Ans[i][j+1] = Ans[i+1][j+1] = Ansn;
			if(ff(i, key, dk, mk | (1<<(j+1)), j+2)) return true;
			Ansn--; Ans[i][j] = Ans[i][j+1] = Ans[i+1][j+1] = 0;
		}
	}
	if(!((key | (1<<(j+1))) ^ key) && !((key | (1<<(j+2))) ^ key)) {
		Ansn++; Ans[i][j] = Ans[i][j+1] = Ans[i][j+2] = Ansn;
		if(ff(i, key, dk, mk, j+3)) return true;
		Ansn--; Ans[i][j] = Ans[i][j+1] = Ans[i][j+2] = 0;
	}
	return false;
}
bool chkgg[MAXN][MAXN];
vector<int> GV;
void gg(int y, int x) {
	if(chkgg[y][x]) return; chkgg[y][x] = true;
	for(int dir = 0; dir < 4; dir++) {
		const int ny = y+dy[dir], nx = x+dx[dir];
		if(ny <= 0 || nx < 0 || 2*N < ny || 4*N-1 <= nx) continue;
		if(Ans[ny][nx] == Ans[y][x]) { gg(ny, nx); continue; }
		if(!GA[ny][nx]) continue;
		GV.pb(GA[ny][nx]);
	}
}
bool chkfgg[MAXN][MAXN];
void fgg(int y, int x, int c) {
	chkfgg[y][x] = true; GA[y][x] = c;
	for(int dir = 0; dir < 4; dir++) {
		const int ny = y+dy[dir], nx = x+dx[dir];
		if(ny <= 0 || nx < 0 || 2*N < ny || 4*N-1 <= nx) continue;
		if(Ans[ny][nx] == Ans[y][x] && !chkfgg[ny][nx]) {
			fgg(ny, nx, c);
		}
	}
}
int main() {
	scanf("%d", &N);
	for(int i = 1; i <= 2*N; i++) scanf(" %s", str[i]);
	{
		int shit = 0;
		for(int i = 1; i <= 2*N; i++) for(int j = 0; j < 4*N-1; j++) shit += str[i][j] == '.';
		if(shit%3) { puts("nemoguce"); return 0; }
	}
	for(int i = 1; i < N; i++) { // N-i
		for(int j = 4*N-2; ~j; j--) str[i][j+N-i] = str[i][j];
		for(int j = 0; j < N-i; j++) str[i][j] = 0;
	}
	for(int i = N+2; i <= 2*N; i++) { // i-N-1
		for(int j = 4*N-2; ~j; j--) str[i][j+i-N-1] = str[i][j];
		for(int j = 0; j < i-N-1; j++) str[i][j] = 0;
	}
	for(int i = 1; i <= 2*N; i++) for(int j = 0; j <= 4*N-2; j++)
		if(!str[i][j]) str[i][j] = 'T';
	for(int i = 1; i <= 2*N; i++) {
		int &key = spkey[i];
		for(int j = 0; j < 4*N-1; j++) key += ('0' == str[i][j]) ? (1<<j) : 0;
	}
	//for(int i = 1; i <= 2*N; i++) puts(str[i]);
	if(!g(1, spkey[1])) { puts("nemoguce"); return 0; }
	whf[0][0] = spkey[1]; for(int i = 1, pk = 0; i <= 2*N; i++) {
		int key = whf[i-1][pk], down = spkey[i+1] ^ whf[i][key]; pk = key;
		//printf("KEY %2d : ", i); cout << bitset<19>(key) << " " << key << endl;
		//printf("DOW %2d : ", i); cout << bitset<19>(down) << " " << down << endl;
		chkn++; ff(i, key, down, 0, 0);
	}
	for(int i = 1; i <= 2*N; i++) {
		for(int j = 0; j < 4*N-1; j++) {
			if(chkfgg[i][j] || !Ans[i][j]) continue;
			clv(GV); gg(i, j); sorv(GV); univ(GV);
			int ret = -1;
			for(int k = 1; k <= 6; k++) {
				bool flag = false;
				for(int v : GV) if(v == k) { flag = true; break; }
				if(flag) continue;
				ret = k; break;
			}
			if(-1 == ret) while(1) printf("FUCK %d %d\n", i, j);
			fgg(i, j, ret);
		}
	}
	//for(int i = 1; i <= 2*N; puts(""), i++) for(int j = 0; j < 4*N-1; j++) printf("%2d ", Ans[i][j]);
	for(int i = 1; i <= N; i++) {
		for(int j = N-i; j <= 3*N+i-2; j++)
			putchar(GA[i][j] ? '0' + GA[i][j] : '.');
		putchar('\n');
	}
	for(int i = N+1; i <= 2*N; i++) {
		for(int j = N-(2*N+1-i); j <= 3*N+(2*N+1-i)-2; j++)
			putchar(GA[i][j] ? '0' + GA[i][j] : '.');
		putchar('\n');
	}
	return 0;
}

Compilation message

trapezi.cpp: In function 'int main()':
trapezi.cpp:158:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
trapezi.cpp:159:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= 2*N; i++) scanf(" %s", str[i]);
                                                    ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 411648 KB Output is correct
2 Correct 0 ms 411648 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 411648 KB Output is correct
2 Correct 0 ms 411648 KB Output is correct
3 Correct 0 ms 411648 KB Output is correct
4 Correct 0 ms 411648 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 411648 KB Output is correct
2 Correct 0 ms 411648 KB Output is correct
3 Correct 0 ms 411648 KB Output is correct
4 Correct 0 ms 411648 KB Output is correct
5 Correct 0 ms 411648 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 411648 KB Output is correct
2 Correct 0 ms 411648 KB Output is correct
3 Correct 0 ms 411648 KB Output is correct
4 Correct 0 ms 411648 KB Output is correct
5 Correct 0 ms 411648 KB Output is correct
6 Correct 0 ms 411648 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 411648 KB Output is correct
2 Correct 0 ms 411648 KB Output is correct
3 Correct 0 ms 411648 KB Output is correct
4 Correct 0 ms 411648 KB Output is correct
5 Correct 0 ms 411648 KB Output is correct
6 Correct 9 ms 411648 KB Output is correct
7 Correct 3 ms 411648 KB Output is correct
8 Correct 0 ms 411648 KB Output is correct
9 Correct 0 ms 411648 KB Output is correct
10 Correct 6 ms 411648 KB Output is correct