| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 785360 |
2023-07-17T08:43:22 Z |
박상훈(#10022) |
Trapezi (COI17_trapezi) |
C++17 |
|
500 ms |
596 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char bufs[101];
int a[101][101], ans[101][101], cntC;
int buf[101], up[101][101], L[101], R[101], n;
vector<pair<int, int>> adj[101][101];
int ok(int x, int y){
if (x<1 || x>n*2) return 0;
if (y<L[x] || y>R[x]) return 0;
return 1;
}
void init(int n){
for (int i=1;i<=n;i++){
L[i] = n+1-i;
R[i] = L[i] + (n-1+i) * 2;
for (int j=L[i];j<=R[i];j+=2) up[i][j] = 1;
}
for (int i=n+1;i<=n*2;i++){
L[i] = L[n*2+1-i];
R[i] = R[n*2+1-i];
for (int j=L[i]+1;j<=R[i];j+=2) up[i][j] = 1;
}
for (int i=1;i<=n*2;i++){
for (int j=L[i];j<=R[i];j++){
if (up[i][j]){
// printf(" up %d %d\n", i, j);
if (ok(i, j-1)) adj[i][j].emplace_back(i, j-1);
if (ok(i, j+1)) adj[i][j].emplace_back(i, j+1);
if (ok(i+1, j)) adj[i][j].emplace_back(i+1, j);
}
else{
if (ok(i-1, j)) adj[i][j].emplace_back(i-1, j);
if (ok(i, j-1)) adj[i][j].emplace_back(i, j-1);
if (ok(i, j+1)) adj[i][j].emplace_back(i, j+1);
}
}
}
}
void input(int n){
for (int i=1;i<=n*2;i++){
scanf("%s", bufs);
for (int j=0;j<=R[i]-L[i];j++) a[i][j+L[i]] = bufs[j];
}
}
void output(int n){
for (int i=1;i<=n*2;i++){
for (int j=L[i];j<=R[i];j++){
if (ans[i][j]) printf("%c", '0' + ans[i][j]);
else printf("%c", (char)a[i][j]);
}
printf("\n");
}
exit(0);
}
void color(int n){
for (int z=1;z<=cntC;z++){
fill(buf+1, buf+7, 0);
for (int i=1;i<=n*2;i++){
for (int j=L[i];j<=R[i];j++) if (a[i][j]==z + '0'){
for (auto &[x, y]:adj[i][j]) if (ans[x][y]!=0) buf[ans[x][y]] = 1;
}
}
int col = -1;
for (int i=1;i<=6;i++) if (!buf[i]) col = i;
assert(col!=-1);
for (int i=1;i<=n*2;i++){
for (int j=L[i];j<=R[i];j++) if (a[i][j]==z + '0'){
ans[i][j] = col;
}
}
}
}
void dfs();
inline int push(int x1, int y1, int x2, int y2, int x3, int y3, bool flag){
if (x2 < 1 || x2 > n*2) return 0;
if (x3 < 1 || x3 > n*2) return 0;
if (y2 < L[x2] || y2 > R[x2]) return 0;
if (y3 < L[x3] || y3 > R[x3]) return 0;
if (a[x2][y2]!='0' || a[x3][y3]!='0') return 0;
// fill(buf+1, buf+7, 0);
// for (auto &[x, y]:adj[x1][y1]) if (a[x][y]!='0' && a[x][y]!='.') buf[a[x][y]-'0'] = 1;
// for (auto &[x, y]:adj[x2][y2]) if (a[x][y]!='0' && a[x][y]!='.') buf[a[x][y]-'0'] = 1;
// for (auto &[x, y]:adj[x3][y3]) if (a[x][y]!='0' && a[x][y]!='.') buf[a[x][y]-'0'] = 1;
// int col = -1;
// for (int i=1;i<=6;i++) if (!buf[i]) {col = i; break;}
// if (col==-1) return;
if (flag){
a[x1][y1] = a[x2][y2] = a[x3][y3] = (++cntC) + '0';
dfs();
--cntC;
a[x1][y1] = a[x2][y2] = a[x3][y3] = '0';
}
return 1;
}
int count(int x, int y, bool flag = false){
int ret = 0;
if (up[x][y]){
ret += push(x, y, x, y-2, x, y-1, flag);
ret += push(x, y, x, y-1, x, y+1, flag);
ret += push(x, y, x, y+1, x, y+2, flag);
ret += push(x, y, x-1, y+1, x, y+1, flag);
ret += push(x, y, x, y+1, x+1, y, flag);
ret += push(x, y, x+1, y, x+1, y-1, flag);
ret += push(x, y, x-1, y-1, x, y-1, flag);
ret += push(x, y, x, y-1, x+1, y, flag);
ret += push(x, y, x+1, y, x+1, y+1, flag);
}
else{
ret += push(x, y, x, y-2, x, y-1, flag);
ret += push(x, y, x, y-1, x, y+1, flag);
ret += push(x, y, x, y+1, x, y+2, flag);
ret += push(x, y, x-1, y+1, x-1, y, flag);
ret += push(x, y, x-1, y, x, y-1, flag);
ret += push(x, y, x, y-1, x+1, y-1, flag);
ret += push(x, y, x-1, y-1, x-1, y, flag);
ret += push(x, y, x-1, y, x, y+1, flag);
ret += push(x, y, x, y+1, x+1, y+1, flag);
}
return ret;
}
int fail;
void dfs(){
if (fail > 1000000){
printf("nemoguce\n");
exit(0);
}
int mn = 69, ii = -1, jj = -1;
for (int i=1;i<=n*2;i++){
for (int j=L[i];j<=R[i];j++) if (a[i][j]=='0'){
int tmp = count(i, j);
if (tmp < mn){
mn = tmp;
ii = i, jj = j;
}
}
}
// printf("ok mn = %d / %d %d\n", mn, ii, jj);
if (mn==69){
color(n);
output(n);
}
if (mn==0){
fail++;
return;
}
count(ii, jj, 1);
// if (y > R[x]) {dfs(x+1, L[x+1]); return;}
// if (x==n*2 && y==R[x]){
// if (a[x][y]!='0'){
// color(n);
// output(n);
// }
// return;
// }
// if (a[x][y]!='0'){
// dfs(x, y+1);
// return;
// }
// if (up[x][y]){
// push(x, y, x, y+1, x, y+2);
// push(x, y, x+1, y, x+1, y-1);
// push(x, y, x+1, y, x+1, y+1);
// push(x, y, x, y+1, x+1, y);
// }
// else{
// push(x, y, x, y+1, x, y+2);
// push(x, y, x, y+1, x+1, y+1);
// }
}
int main(){
scanf("%d", &n);
init(n);
input(n);
dfs();
printf("nemoguce\n");
}
Compilation message
trapezi.cpp: In function 'void input(int)':
trapezi.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%s", bufs);
| ~~~~~^~~~~~~~~~~~
trapezi.cpp: In function 'int main()':
trapezi.cpp:210:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
210 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
0 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
0 ms |
468 KB |
Output is correct |
| 5 |
Correct |
0 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
0 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Execution timed out |
1076 ms |
468 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
