oj.uz

답안 #785242

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
785242 2023-07-17T07:32:56 Z 반딧불(#10021) Trapezi (COI17_trapezi) C++17
63 / 100
 51 ms 65672 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

/// ��Ʈ DP�� �Ѵ�.
/// ��Ʈ ���´� ����� ĭ�� ���� ��Ʈ�� �ΰ�, �ָ� �ִ� ĭ�� ���� ��Ʈ�� �д�.

int n;
int arr[150]; /// �� ĭ�� �ʱ� ����

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);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 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

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 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

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 4 ms 7636 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 4 ms 7140 KB Output is correct
6 Correct 3 ms 1972 KB Output is correct

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 65672 KB Output isn't correct
2 Halted 0 ms 0 KB -