oj.uz

Submission #785259

# Submission time Handle Problem Language Result Execution time Memory
785259 2023-07-17T07:42:09 Z 이동현(#10024) Trapezi (COI17_trapezi) C++17
6 / 100
 1 ms 212 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}}};
int waycol[2][9] = {{3, 4, 5, 3, 4, 5, 0, 2, 1}, {0, 1, 2, 0, 1, 2, 3, 4, 5}};

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

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

    cin >> n;
    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;
            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;
            }
        }
    }

    auto ok = [&](int x, int y, int v)->bool{
        if(x < 0 || y < 0 || !in[x][y] || ans[x][y] != -1) return false;
        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] == v) return false;
        }
        return true;
    };

    int cnt = 0;
    auto dfs = [&](auto&&self, int x)->void{
        ++cnt;
        if(cnt > (int)5e7){
            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);
        }

        for(int i = 0; i < 9; ++i){
            int md = pos[x][1] % 2;
            int nx = pos[x][0] + wayx[md][i][0], ny = pos[x][1] + wayy[md][i][0];
            int nnx = pos[x][0] + wayx[md][i][1], nny = pos[x][1] + wayy[md][i][1];
            int ncol = waycol[md][i];
            if(ok(nx, ny, ncol) && ok(nnx, nny, ncol)){
                // cout << pos[x][0] << ' ' << pos[x][1] << ' ' << nx << ' ' << ny << ' ' << nnx << ' ' << nny << endl;
                ans[pos[x][0]][pos[x][1]] = ans[nx][ny] = ans[nnx][nny] = ncol;
                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;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -