oj.uz

Submission #583886

# Submission time Handle Problem Language Result Execution time Memory
583886 2022-06-26T12:19:01 Z jhwest2 L-triominoes (CEOI21_ltriominoes) C++14
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;
            }
        }
    }

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

Compilation message

ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |         auto [f, s] = A[i]; --f;
      |              ^
ltrominoes.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for (auto [f, s] : V) {
      |               ^

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