| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 26296 |
2017-06-29T05:55:25 Z |
윤교준(#1105) |
Trapezi (COI17_trapezi) |
C++11 |
|
0 ms |
231428 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];
bool isf[MAXN][MAXN];
int spkey[MAXN];
int whf[MAXN];
int N;
int VKchk[MAXK], VKchkn;
vector<int> VK;
void f(int i, int key, int mk, int j) {
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(i, key, mk, j+1); return; }
if((i <= N && ((i+j)&1)) || (N < i && !((i+j)&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(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(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(i, key, mk | (1<<j), j+2);
if(!((key | (1<<(j+1))) ^ key) && ((mk | (1<<(j+1))) ^ mk) && !((spkey[i+1] | (1<<(j+1))) ^ spkey[i+1]))
f(i, key, mk | (1<<(j+1)), j+2);
}
if(!((key | (1<<(j+1))) ^ key) && !((key | (1<<(j+2))) ^ key)) f(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] = spkey[i+1];
return true;
}
return false;
}
chkn++; VKchkn++; clv(VK); f(i, key, 0, 0);
for(int v : VK) {
if(g(i+1, v)) {
whf[i] = 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 <= N && ((i+j)&1)) || (N < i && !((i+j)&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;
}
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;
}
if(!g(1, spkey[1])) { puts("nemoguce"); return 0; }
whf[0] = spkey[1]; for(int i = 1; i <= 2*N; i++) {
int key = whf[i-1], down = spkey[i+1] ^ whf[i];
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(isf[i][j] || !Ans[i][j] || GA[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 <= N; i++) {
for(int j = N-i; j <= 3*N+i-2; j++)
putchar(GA[i][j] ? '0' + 7 - 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' + 7 - GA[i][j] : '.');
putchar('\n');
}
return 0;
}
Compilation message
trapezi.cpp: In function 'int main()':
trapezi.cpp:156:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
trapezi.cpp:157: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]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
231428 KB |
Output is correct |
| 2 |
Correct |
0 ms |
231428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
231428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
231428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
231428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
231428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
