Submission #590800

# Submission time Handle Problem Language Result Execution time Memory
590800 2022-07-06T11:23:12 Z alextodoran L-triominoes (CEOI21_ltriominoes) C++17
52 / 100
1136 ms 133120 KB
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int W_MAX = 13;
const int K_MAX = 250;
const int D_MAX = 15;

int W, H, K;
map <int, vector <int>> rows;

bool adj[1 << W_MAX][1 << W_MAX];
vector <int> out[1 << W_MAX];

bool check (int u, int v) {
    int carry = 0;
    for (int y = 0; y < W; y++) {
        int cnt = ((u >> y) & 1) + !((v >> y) & 1) - carry;
        if (cnt < 0) {
            return false;
        } else if (cnt == 0) {
            carry = 0;
        } else if (cnt == 1) {
            carry = 2;
        } else {
            carry = 1;
        }
    }
    return (carry == 0);
}

bitset <(1 << W_MAX)> path[D_MAX + 1][1 << W_MAX];

void build () {
    for (int u = 0; u < (1 << W); u++) {
        path[0][u][u] = true;
    }
    for (int d = 1; d <= D_MAX; d++) {
        for (int u = 0; u < (1 << W); u++) {
            for (int v : out[u]) {
                path[d][u] |= path[d - 1][v];
            }
        }
    }
}

bitset <(1 << W_MAX)> reach;
bitset <(1 << W_MAX)> newReach;

void advance (int k) {
    if (k > D_MAX) {
        k -= (k - D_MAX + 2) / 3 * 3;
    }
    for (int u = 0; u < (1 << W); u++) {
        if (reach[u] == true) {
            newReach |= path[k][u];
        }
    }
    swap(reach, newReach); newReach.reset();
}

bool solve () {
    reach[(1 << W) - 1] = true;
    int x = 0;
    for (pair <int, vector <int>> row : rows) {
        advance(row.first - x); x = row.first;
        int b = 0;
        for (int y : row.second) {
            b |= (1 << y);
        }
        for (int u = b; u < (1 << W); u = ((u + 1) | b)) {
            newReach[u ^ b] = reach[u];
        }
        swap(reach, newReach); newReach.reset();
    }
    advance((H - 1) - x);
    return reach[0];
}

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

    cin >> W >> H >> K;
    for (int i = 0; i < K; i++) {
        int x, y;
        cin >> y >> x;
        x--; y--;
        rows[x].push_back(y);
    }

    for (int u = 0; u < (1 << W); u++) {
        for (int v = 0; v < (1 << W); v++) {
            if (check(u, v) == true) {
                out[u].push_back(v);
            }
        }
    }
    build();

    cout << (solve() == true ? "YES" : "NO") << "\n";

    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 0 ms 724 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 280 ms 66692 KB Output is correct
6 Correct 88 ms 33616 KB Output is correct
7 Correct 33 ms 17140 KB Output is correct
8 Correct 5 ms 4820 KB Output is correct
9 Incorrect 1 ms 724 KB Output isn't correct
10 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 668 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 792 KB Output is correct
17 Correct 1 ms 724 KB Output is correct
18 Incorrect 1 ms 724 KB Output isn't correct
19 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 1108 KB Output is correct
12 Correct 2 ms 1620 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 1 ms 1108 KB Output is correct
16 Correct 2 ms 1620 KB Output is correct
17 Correct 1 ms 1108 KB Output is correct
18 Correct 1 ms 1108 KB Output is correct
19 Correct 2 ms 1620 KB Output is correct
20 Correct 2 ms 1620 KB Output is correct
21 Correct 1 ms 1108 KB Output is correct
22 Correct 2 ms 1620 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 1 ms 1108 KB Output is correct
25 Correct 2 ms 1620 KB Output is correct
26 Correct 1 ms 852 KB Output is correct
27 Correct 1 ms 1108 KB Output is correct
28 Correct 1 ms 1108 KB Output is correct
29 Correct 1 ms 1108 KB Output is correct
30 Correct 1 ms 1108 KB Output is correct
31 Correct 1 ms 1108 KB Output is correct
32 Correct 1 ms 1620 KB Output is correct
33 Correct 2 ms 1620 KB Output is correct
34 Correct 2 ms 1620 KB Output is correct
35 Correct 2 ms 1620 KB Output is correct
36 Correct 1 ms 1108 KB Output is correct
37 Correct 2 ms 1620 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 9 ms 4784 KB Output is correct
4 Correct 334 ms 66748 KB Output is correct
5 Correct 103 ms 33596 KB Output is correct
6 Correct 105 ms 33656 KB Output is correct
7 Correct 33 ms 17088 KB Output is correct
8 Correct 38 ms 17088 KB Output is correct
9 Correct 32 ms 17108 KB Output is correct
10 Correct 32 ms 17068 KB Output is correct
11 Correct 315 ms 66640 KB Output is correct
12 Correct 96 ms 33528 KB Output is correct
13 Correct 12 ms 8876 KB Output is correct
14 Correct 292 ms 66724 KB Output is correct
15 Correct 3 ms 2608 KB Output is correct
16 Correct 3 ms 2644 KB Output is correct
17 Correct 36 ms 17120 KB Output is correct
18 Correct 8 ms 4820 KB Output is correct
19 Correct 15 ms 8856 KB Output is correct
20 Correct 302 ms 66776 KB Output is correct
21 Correct 111 ms 33612 KB Output is correct
22 Correct 3 ms 2644 KB Output is correct
23 Correct 15 ms 8924 KB Output is correct
24 Correct 949 ms 133120 KB Output is correct
25 Correct 319 ms 66696 KB Output is correct
26 Correct 952 ms 133012 KB Output is correct
27 Correct 955 ms 133028 KB Output is correct
28 Correct 921 ms 132928 KB Output is correct
29 Correct 930 ms 132952 KB Output is correct
30 Correct 949 ms 132928 KB Output is correct
31 Correct 867 ms 133028 KB Output is correct
32 Correct 909 ms 132952 KB Output is correct
33 Correct 340 ms 66780 KB Output is correct
34 Correct 1036 ms 133028 KB Output is correct
35 Correct 964 ms 133028 KB Output is correct
36 Correct 995 ms 133024 KB Output is correct
37 Correct 347 ms 66720 KB Output is correct
38 Correct 288 ms 66756 KB Output is correct
39 Correct 108 ms 33576 KB Output is correct
40 Correct 1034 ms 132952 KB Output is correct
41 Correct 105 ms 33608 KB Output is correct
42 Correct 1136 ms 132912 KB Output is correct
43 Correct 1068 ms 133084 KB Output is correct
44 Correct 1082 ms 133012 KB Output is correct
45 Correct 1026 ms 132992 KB Output is correct
46 Correct 299 ms 66764 KB Output is correct
47 Correct 1020 ms 133000 KB Output is correct
48 Correct 1063 ms 132956 KB Output is correct
49 Correct 1076 ms 132952 KB Output is correct
50 Correct 111 ms 33560 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -