oj.uz

Submission #785298

# Submission time Handle Problem Language Result Execution time Memory
785298 2023-07-17T08:08:48 Z 이동현(#10024) Trapezi (COI17_trapezi) C++17
23 / 100
 470 ms 340 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)3e5;

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

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

    cin >> n;
    // n = 3;
    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]);
    }

    auto ok = [&](int x, int y)->vector<int>{
        if(x < 0 || y < 0 || !in[x][y] || ans[x][y] != -1) return {};
        vector<int> chk(6);
        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;
        }
        vector<int> rv;
        for(int i = 0; i < 6; ++i){
            if(!chk[i]){
                rv.push_back(i);
            }
        }
        return rv;
    };

    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);
        }

        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];
            vector<int> col = ok(pos[x][0], pos[x][1]);
            vector<int> ncol = ok(nx, ny);
            vector<int> nncol = ok(nnx, nny);
            int k1 = 0, k2 = 0;
            for(int j = 0; j < (int)col.size(); ++j){
                while(k1 < (int)ncol.size() && ncol[k1] < col[j]) ++k1;
                while(k2 < (int)nncol.size() && nncol[k2] < col[j]) ++k2;
                if(k1 == (int)ncol.size() || k2 == (int)nncol.size()) break;
                if(col[j] == ncol[k1] && col[j] == nncol[k2]){
                    ans[pos[x][0]][pos[x][1]] = ans[nx][ny] = ans[nnx][nny] = col[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;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 18.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 340 KB Output is correct
2 Correct 55 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 367 ms 312 KB Output is correct
5 Incorrect 470 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -