| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 785479 |
2023-07-17T09:27:05 Z |
이성호(#10023) |
Trapezi (COI17_trapezi) |
C++17 |
|
500 ms |
1048576 KB |
#include <iostream>
#include <cassert>
using namespace std;
int N;
char color[801];
bool blocked[2000];
pair<bool, int> dp[201][1<<20];
int digit[800];
int res[801];
int main()
{
scanf("%d", &N);
for (int i = 0; i < 2 * N; i++) {
if (i < N) scanf("%s", color + 4 * N * i + 2 * N - 2 * i - 1);
else scanf("%s", 4 * N * i + color);
}
for (int i = 0; i < 8 * N * N; i++) blocked[i] = color[i] != '0';
dp[8*N*N][0] = make_pair(true, -1);
int row = 4*N;
for (int i = 8*N*N - 1; i >= 0; i--) {
for (int j = 0; j < 1 << row; j++) {
if (j & 1) {
int nxt = j >> 1;
if (blocked[i+row]) nxt |= 1 << row - 1;
dp[i][j].first = dp[i+1][nxt].first;
dp[i][j].second = 0;
continue;
}
if (blocked[i]) {
dp[i][j].first = false;
continue;
}
if (i % row < row - 2 && !(j & 2) && !(j & 4)) {
int nxt = (j >> 1) | 3;
if (blocked[i+row]) nxt |= 1 << row - 1;
if (dp[i+1][nxt].first) { //type 1
dp[i][j].first = true;
dp[i][j].second = 1;
continue;
}
}
if (i % 2 == 0) {
if (!(j & 2) && !blocked[i+row] && dp[i+1][(j>>1)|1|(1<<row-1)].first) { //type 2
dp[i][j].first = true;
dp[i][j].second = 2;
continue;
}
}
else {
if (i % row < row - 1 && !(j & 2) && !(j & 1 << row - 1)) { //type 2
int nxt = (j>>1)|1|(1<<row-2);
if (blocked[i+row]) nxt |= 1 << row - 1;
if (dp[i+1][nxt].first) {
dp[i][j].first = true;
dp[i][j].second = 2;
continue;
}
}
if (!(j & 1 << row - 1) && !blocked[i+row] && dp[i+1][(j>>1)|(1<<row-2)|(1<<row-1)].first) { //type 3
dp[i][j].first = true;
dp[i][j].second = 3;
continue;
}
if (i % row >= 3 && !(j & 1 << row - 1) && !(j & 1 << row - 2)) { //type 4
int nxt = (j>>1)|(1<<row-3)|(1<<row-2);
if (blocked[i+row]) nxt |= 1 << row - 1;
if (dp[i+1][nxt].first) {
dp[i][j].first = true;
dp[i][j].second = 4;
continue;
}
}
}
}
}
int bit = 0;
for (int i = 4 * N - 1; i >= 0; i--) {
bit <<= 1;
bit += blocked[i];
}
//type 1: i, i+1, i+2
//type 2: i�� ¦��) i, i+1, i+row
// i�� Ȧ��) i, i+1, i+row-1
//type 3: i, i+row-1, i+row
//type 4: i, i+row-2, i+row-1
if (!dp[0][bit].first) {
cout << "nemoguce\n";
return 0;
}
else {
int cur = bit;
for (int i = 0; i < 8 * N * N; i++) {
int pv = dp[i][cur].second;
if (pv == 0) {
cur >>= 1;
if (blocked[i+row]) cur |= 1 << row - 1;
}
else {
int nxt[3] = {};
if (pv == 1) nxt[0] = i, nxt[1] = i+1, nxt[2] = i+2;
else if (pv == 2) nxt[0] = i, nxt[1] = i+1, nxt[2] = i+row-i%2;
else if (pv == 3) nxt[0] = i, nxt[1] = i+row-1, nxt[2] = i+row;
else nxt[0] = i, nxt[1] = i+row-2, nxt[2] = i+row-1;
bool visited[7] = {};
for (int p:nxt) {
if (p % row >= 1) visited[res[p-1]] = true;
if (p % row <= row - 2) visited[res[p+1]] = true;
if (p % 2 == 0 && p / row > 0) visited[res[p-row+1]] = true;
else if (p % 2 == 1 && p / row < 2*N-1) visited[res[p+row-1]] = true;
}
int dc = -1;
for (int k = 1; k <= 6; k++) {
if (!visited[k]) {
dc = k;
break;
}
}
assert(dc != -1);
for (int p:nxt) res[p] = dc;
for (int p:nxt) cur |= 1 << p - i;
cur >>= 1;
if (blocked[i+row]) cur |= 1 << row - 1;
}
}
}
for (int i = 0; i < 2 * N; i++) {
if (i < N) {
int st = 4 * N * i + 2 * N - 2 * i - 1;
for (int j = st; j < 4 * N * (i+1); j++) {
if (res[j] == 0) cout << '.';
else cout << res[j];
}
}
else {
int cc = 6 * N - 1 - 2 * i;
for (int j = 4 * N * i; j < 4 * N * i + cc; j++) {
if (res[j] == 0) cout << '.';
else cout << res[j];
}
}
cout << '\n';
}
return 0;
}
Compilation message
trapezi.cpp: In function 'int main()':
trapezi.cpp:24:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
24 | if (blocked[i+row]) nxt |= 1 << row - 1;
| ~~~~^~~
trapezi.cpp:35:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
35 | if (blocked[i+row]) nxt |= 1 << row - 1;
| ~~~~^~~
trapezi.cpp:43:76: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
43 | if (!(j & 2) && !blocked[i+row] && dp[i+1][(j>>1)|1|(1<<row-1)].first) { //type 2
| ~~~^~
trapezi.cpp:50:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
50 | if (i % row < row - 1 && !(j & 2) && !(j & 1 << row - 1)) { //type 2
| ~~~~^~~
trapezi.cpp:51:47: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
51 | int nxt = (j>>1)|1|(1<<row-2);
| ~~~^~
trapezi.cpp:52:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
52 | if (blocked[i+row]) nxt |= 1 << row - 1;
| ~~~~^~~
trapezi.cpp:59:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
59 | if (!(j & 1 << row - 1) && !blocked[i+row] && dp[i+1][(j>>1)|(1<<row-2)|(1<<row-1)].first) { //type 3
| ~~~~^~~
trapezi.cpp:59:85: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
59 | if (!(j & 1 << row - 1) && !blocked[i+row] && dp[i+1][(j>>1)|(1<<row-2)|(1<<row-1)].first) { //type 3
| ~~~^~
trapezi.cpp:59:96: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
59 | if (!(j & 1 << row - 1) && !blocked[i+row] && dp[i+1][(j>>1)|(1<<row-2)|(1<<row-1)].first) { //type 3
| ~~~^~
trapezi.cpp:64:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
64 | if (i % row >= 3 && !(j & 1 << row - 1) && !(j & 1 << row - 2)) { //type 4
| ~~~~^~~
trapezi.cpp:64:75: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
64 | if (i % row >= 3 && !(j & 1 << row - 1) && !(j & 1 << row - 2)) { //type 4
| ~~~~^~~
trapezi.cpp:65:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
65 | int nxt = (j>>1)|(1<<row-3)|(1<<row-2);
| ~~~^~
trapezi.cpp:65:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
65 | int nxt = (j>>1)|(1<<row-3)|(1<<row-2);
| ~~~^~
trapezi.cpp:66:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
66 | if (blocked[i+row]) nxt |= 1 << row - 1;
| ~~~~^~~
trapezi.cpp:97:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
97 | if (blocked[i+row]) cur |= 1 << row - 1;
| ~~~~^~~
trapezi.cpp:121:47: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
121 | for (int p:nxt) cur |= 1 << p - i;
| ~~^~~
trapezi.cpp:123:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
123 | if (blocked[i+row]) cur |= 1 << row - 1;
| ~~~~^~~
trapezi.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
trapezi.cpp:14:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | if (i < N) scanf("%s", color + 4 * N * i + 2 * N - 2 * i - 1);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezi.cpp:15:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | else scanf("%s", 4 * N * i + color);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
67340 KB |
Output is correct |
| 2 |
Correct |
41 ms |
67376 KB |
Output is correct |
| 3 |
Correct |
36 ms |
67256 KB |
Output is correct |
| 4 |
Correct |
35 ms |
67332 KB |
Output is correct |
| 5 |
Correct |
41 ms |
67304 KB |
Output is correct |
| 6 |
Correct |
39 ms |
67328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
644 ms |
1048576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
