| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 785248 |
2023-07-17T07:37:30 Z |
반딧불(#10021) |
Trapezi (COI17_trapezi) |
C++17 |
|
74 ms |
114508 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/// ��Ʈ DP�� �Ѵ�.
/// ��Ʈ ���´� ����� ĭ�� ���� ��Ʈ�� �ΰ�, �ָ� �ִ� ĭ�� ���� ��Ʈ�� �д�.
int n;
int arr[152]; /// �� ĭ�� �ʱ� ����
void init();
void solve();
int main(){
scanf("%d", &n);
init();
solve();
}
int L;
map<pair<int, int>, int> idx;
int X[152], Y[152];
int bitcount[152]; /// �� ������ ��� �ٳ�� �� ��Ʈ�� ����
int choice[152][4]; /// �� ������ ������ �� �ִ� ������, �Ұ����� ��� -1
int choiceNum[152][4][2]; /// �� ������ ������ �� �ִ� ������, �Ұ����� ��� -1
int bonus[152]; /// DP�� ó�� ���� �� �߰��Ǵ� ���� ����Ѵ�.
int findIdx(int x, int y){
if(idx.find(make_pair(x, y)) == idx.end()) return -1;
return idx[make_pair(x, y)];
}
void tryChoice(int i, int j, int x1, int y1, int x2, int y2){
int x = X[i], y = Y[i];
int a = findIdx(x+x1, y+y1);
int b = findIdx(x+x2, y+y2);
if(a==-1 || b==-1) choice[i][j] = -1;
else choice[i][j] = (1<<(a-i-1)) + (1<<(b-i-1)), choiceNum[i][j][0] = a, choiceNum[i][j][1] = b;
}
void init(){
/// ĭ�� ����� �д�
for(int i=0; i<n+n; i++){
int s = i<n ? n+i : n*3-i-1;
for(int j=-s; j<=s; j++){
L++;
X[L] = i, Y[L] = j;
idx[make_pair(i, j)] = L;
}
}
for(int i=1; i<=L; i++){
char c;
scanf(" %c", &c);
if(c == '.') arr[i] = -1;
else arr[i] = 0;
}
/// choice�� ��
for(int i=1; i<=L; i++){
tryChoice(i, 0, 0, 1, 0, 2);
if((X[i]+Y[i]+n+1)%2){ /// ^ ���
tryChoice(i, 1, 1, 0, 1, -1);
tryChoice(i, 2, 1, 0, 1, 1);
tryChoice(i, 3, 1, 0, 0, 1);
}
else{ /// v ���
tryChoice(i, 1, 0, 1, 1, 1);
choice[i][2] = choice[i][3] = -1;
}
}
/// bitcount�� ��.
for(int i=1; i<=L; i++){
int j = i;
while(j+1<=L && make_pair(X[j+1], Y[j+1]) <= make_pair(X[i]+1, Y[i]+1)) j++;
bitcount[i] = j-i;
}
/// bonus�� ��.
int prv = 0;
for(int i=1; i<=L; i++){
for(int s=prv+1; s<=bitcount[i]+i; s++){
bonus[i] += (arr[s] == -1) << (s-i);
}
prv = bitcount[i] + i;
}
}
char track[152][1<<20]; /// �������� DP�� ���ÿ� �����Ѵ�. (150 MB) 0: �Ұ���, -1: �ʱ� ����, 1, 2, 3, 4: ����, 5: �ƹ��͵� �� ��
int trackJ[152][1<<20];
int getColor(int x, int y){
int tmp = findIdx(x, y);
if(tmp == -1) return 0;
return tmp;
}
void color(int a, int b, int c){
int able = 126;
able &= ~(1<<arr[getColor(X[a], Y[a]+1)]);
able &= ~(1<<arr[getColor(X[a], Y[a]-1)]);
able &= ~(1<<arr[getColor(X[a]+((X[a]+Y[a]+n+1)%2 ? 1 : -1), Y[a])]);
able &= ~(1<<arr[getColor(X[b], Y[b]+1)]);
able &= ~(1<<arr[getColor(X[b], Y[b]-1)]);
able &= ~(1<<arr[getColor(X[b]+((X[b]+Y[b]+n+1)%2 ? 1 : -1), Y[b])]);
able &= ~(1<<arr[getColor(X[c], Y[c]+1)]);
able &= ~(1<<arr[getColor(X[c], Y[c]-1)]);
able &= ~(1<<arr[getColor(X[c]+((X[c]+Y[c]+n+1)%2 ? 1 : -1), Y[c])]);
for(int i=1; i<=6; i++) if((able>>i)&1){
arr[a] = arr[b] = arr[c] = i;
return;
}
exit(-1);
}
void solve(){
track[0][0] = -1;
for(int i=1; i<=L; i++){
int LIM = (1<<bitcount[i-1]);
for(int j=0; j<LIM; j++){
if(!track[i-1][j]) continue;
int tj = j|bonus[i];
// printf("%d %d: %d\n", i-1, j, track[i-1][j]);
if(tj&1){ /// �̹� ĭ�� �� ����
track[i][tj>>1] = 5;
trackJ[i][tj>>1] = j;
continue;
}
for(int c=0; c<4; c++){
if(choice[i][c] == -1 || ((tj>>1) & choice[i][c])) continue;
track[i][(tj>>1)|choice[i][c]] = c+1;
trackJ[i][(tj>>1)|choice[i][c]] = j;
}
}
}
if(track[L][0] == 0){
puts("nemoguce");
exit(0);
}
int x = L, y = 0;
while(x){
int p = track[x][y];
if(p<0) break;
if(1<=p && p<=4){ /// �ƹ��͵� �� ��. �̹� x�� ĭ�� �� �� �־���
color(x, choiceNum[x][p-1][0], choiceNum[x][p-1][1]);
}
y = trackJ[x][y];
x--;
}
for(int i=1; i<=L; i++){
printf("%c", arr[i] > 0 ? ('0' + arr[i]) : '.');
if(X[i] != X[i+1]) puts("");
}
}
Compilation message
trapezi.cpp: In function 'int main()':
trapezi.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
trapezi.cpp: In function 'void init()':
trapezi.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 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 |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5332 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
596 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7124 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
114508 KB |
Output is correct |
| 2 |
Correct |
65 ms |
95932 KB |
Output is correct |
| 3 |
Correct |
25 ms |
2872 KB |
Output is correct |
| 4 |
Correct |
24 ms |
560 KB |
Output is correct |
| 5 |
Correct |
49 ms |
61012 KB |
Output is correct |
| 6 |
Correct |
50 ms |
62924 KB |
Output is correct |
| 7 |
Correct |
47 ms |
59620 KB |
Output is correct |
| 8 |
Correct |
37 ms |
31156 KB |
Output is correct |
| 9 |
Correct |
43 ms |
25612 KB |
Output is correct |
| 10 |
Correct |
32 ms |
13908 KB |
Output is correct |
