oj.uz

Submission #583890

# Submission time Handle Problem Language Result Execution time Memory
583890 2022-06-26T12:33:43 Z jhwest2 L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
using namespace std;

const int M = 1 << 10;
int n, m, k;
bool dp[13][4];
vector<pair<int, int>> A, V;
bitset<M> G[M];

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> m >> n >> k;
    for (int i = 0; i < k; i++) {
        int x, y; cin >> y >> x;
        A.emplace_back(x, y);
    }
    if (n > 10) {
        cout << "YES\n"; return 0;
    }
    sort(A.begin(), A.end(), [&](auto i, auto j) {
        return i.second < j.second;
        });
    for (int i = 0; i < k; i++) {
        auto [f, s] = A[i]; --f;
        if (V.empty() || V.back().second != s) {
            V.emplace_back(1 << f, s);
        }
        else V.back().first |= (1 << f);
    }
    if (V.empty() || V.back().second != m) {
        V.emplace_back(0, m);
    }
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < (1 << n); j++) {
            if ((n - __builtin_popcount(i) + __builtin_popcount(j)) % 3 != 0) {
                continue;
            }
            int m = (i & 1) + (~j & 1) * 2; dp[0][m] = 1;
            for (int k = 1; k < n; k++) {
                int m = (i >> k & 1) + (~j >> k & 1) * 2;
                if (m == 0) {
                    dp[k][0] = dp[k - 1][3];
                    dp[k][1] = dp[k][2] = dp[k - 1][0];
                    dp[k][3] = (dp[k - 1][1] | dp[k - 1][2]);
                }
                if (m == 1) {
                    dp[k][1] = dp[k - 1][3];
                    dp[k][3] = dp[k - 1][0];
                }
                if (m == 2) {
                    dp[k][2] = dp[k - 1][3];
                    dp[k][3] = dp[k - 1][0];
                }
                if (m == 3) {
                    dp[k][3] = dp[k - 1][3];
                }
            }
            G[i][j] = dp[n - 1][3];
            for (int i = 0; i < n; i++) for (int j = 0; j < 4; j++) {
                dp[i][j] = 0;
            }
        }
    }

   /*  for (int i = 0; i < 8; i++) {
        vector<vector<int>> D(8, vector<int>(12, -1));
        queue<pair<int, int>> Q;
        Q.emplace(i, 0); D[i][0] = 0;
        while (!Q.empty()) {
            auto [x, m] = Q.front(); Q.pop();
            for (int i = 0; i < 8; i++) if (G[x][i]) {
                if (D[i][(m + 1) % 12] == -1) {
                    D[i][(m + 1) % 12] = D[x][m] + 1;
                    Q.emplace(i, (m + 1) % 12);
                }
            }
        }
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 12; j++) {
                cout << D[i][j] << ' ';
            }
            cout << '\n';
        }
        cout << '\n';
    } */

    int p = 0; bitset<M> B = 0, dp = 0, ep = 0;
    dp[(1 << n) - 1] = 1;
    for (auto [f, s] : V) {
        int ff = f ^ ((1 << n) - 1);
        for (int i = ff; ; i = (i - 1) & ff) {
            B[i] = 1;
            if (i == 0) break;
        }
        int it = s - p; /* min((s - p) % 6 + 18, s - p); */
        while (it--) {
            for (int i = 0; i < (1 << n); i++) if (dp[i]) {
                ep |= G[i];
            }
            dp = ep; ep = 0;
        }
        dp &= B;
        for (int i = 0; i < (1 << n); i++) if (dp[i]) {
            ep[i | f] = 1;
        }
        dp = ep; ep = 0; B = 0;
        p = s;

        // cout << dp << '\n';
    }
    cout << (dp[(1 << n) - 1] ? "YES" : "NO");
}

Subtask #1
0 / 10.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
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 11.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
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.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
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -