oj.uz

답안 #785306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
785306 2023-07-17T08:14:18 Z 이동현(#10024) Trapezi (COI17_trapezi) C++17
100 / 100
 492 ms 324 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

int n, posn;
int pos[1004][2];
int ans[14][24], in[14][24];
int wayx[2][9][2] = {{{0, 0}, {0, 1}, {0, 1}, {0, 0}, {-1, -1}, {-1, -1}, {0, 0}, {-1, 0}, {0, -1}}, {{0, 0}, {1, 1}, {1, 1}, {0, 0}, {0, -1}, {0, -1}, {0, 0}, {0, 1}, {1, 0}}};
int wayy[2][9][2] = {{{1, 2}, {1, 0}, {-1, -2}, {-1, -2}, {1, 0}, {1, 2}, {-1, 1}, {1, -1}, {1, 1}}, {{1, 2}, {-1, 0}, {-1, -2}, {-1, -2}, {-1, 0}, {1, 2}, {1, -1}, {-1, -1}, {-1, 1}}};
const int CN = (int)2200000;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    memset(ans, -1, sizeof(ans));

    cin >> n;
    // n = 5;
    for(int i = 0; i < n * 2; ++i){
        for(int j = 0; j < n * 2 + 1 + min(i, n * 2 - i - 1) * 2; ++j){
            char c;
            cin >> c;
            // c = '0';
            // if(i == 0 && j == 0) c = '.';
            if(c == '0'){
                pos[posn][0] = i;
                pos[posn++][1] = j + (max(0, (n - i) * 2 - 1));
                in[i][j + (max(0, (n - i) * 2 - 1))] = 1;
            }
        }
    }

    for(int i = 0; posn - 1 - i > i; ++i){
        swap(pos[i][0], pos[posn - 1 - i][0]);
        swap(pos[i][1], pos[posn - 1 - i][1]);
    }

    int chk[6];
    int ccnt[6];
    auto ok = [&](int x, int y){
        if(x < 0 || y < 0 || !in[x][y] || ans[x][y] != -1) return;
        memset(chk, 0, sizeof(chk));
        for(int i = 0; i < 6; i += 2){
            int md = y % 2;
            int nx = x + wayx[md][i][0], ny = y + wayy[md][i][0];
            if(nx >= 0 && ny >= 0 && ans[nx][ny] != -1) chk[ans[nx][ny]] = 1;
        }
        for(int i = 0; i < 6; ++i){
            ccnt[i] += !chk[i];
        }
    };

    int cnt = 0;
    auto dfs = [&](auto&&self, int x)->void{
        ++cnt;
        if(cnt > CN){
            cout << "nemoguce\n";
            exit(0);
        }

        while(x < posn && ans[pos[x][0]][pos[x][1]] != -1){
            ++x;
        }

        if(x == posn){
            for(int i = 0; i < n * 2; ++i){
                for(int j = 0; j < n * 2 + 1 + min(i, n * 2 - i - 1) * 2; ++j){
                    if(ans[i][j + (max(0, (n - i) * 2 - 1))] == -1) cout << '.';
                    else cout << ans[i][j + (max(0, (n - i) * 2 - 1))] + 1;
                }
                cout << '\n';
            }
            exit(0);
        }

        int md, nx, ny, nnx, nny;
        for(int i = 0; i < 9; ++i){
            md = pos[x][1] % 2;
            nx = pos[x][0] + wayx[md][i][0], ny = pos[x][1] + wayy[md][i][0];
            nnx = pos[x][0] + wayx[md][i][1], nny = pos[x][1] + wayy[md][i][1];
            memset(ccnt, 0, sizeof(ccnt));
            ok(pos[x][0], pos[x][1]);
            ok(nx, ny);
            ok(nnx, nny);
            int k1 = 0, k2 = 0;
            for(int j = 0; j < 6; ++j){
                if(ccnt[j] == 3){
                    ans[pos[x][0]][pos[x][1]] = ans[nx][ny] = ans[nnx][nny] = j;
                    self(self, x + 1);
                    ans[pos[x][0]][pos[x][1]] = ans[nx][ny] = ans[nnx][nny] = -1;
                }
            }
        }
    };

    dfs(dfs, 0);

    cout << "nemoguce\n";

    return 0;
}

Compilation message

trapezi.cpp: In instantiation of 'main()::<lambda(auto:23&&, int)> [with auto:23 = main()::<lambda(auto:23&&, int)>&]':
trapezi.cpp:99:15:   required from here
trapezi.cpp:88:17: warning: unused variable 'k1' [-Wunused-variable]
   88 |             int k1 = 0, k2 = 0;
      |                 ^~
trapezi.cpp:88:25: warning: unused variable 'k2' [-Wunused-variable]
   88 |             int k1 = 0, k2 = 0;
      |                         ^~

Subtask #1
6.0 / 6.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 18 ms 212 KB Output is correct
6 Correct 12 ms 324 KB Output is correct

Subtask #5
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 492 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 464 ms 300 KB Output is correct