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

ltrominoes

/**
 ____ ____ ____ ____ ____
||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;
}

Subtask #1

0 / 10.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	-

Subtask #2

0 / 7.0

#	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	-

Subtask #3

0 / 11.0

#	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	-

Subtask #4

17.0 / 17.0

#	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

Subtask #5

35.0 / 35.0

#	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

Subtask #6

0 / 20.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	-