답안 #590797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
590797	2022-07-06T11:19:33 Z	alextodoran	L-triominoes (CEOI21_ltriominoes)	C++17	52 / 100	930 ms	108568 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 = 12;

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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	732 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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2260 KB	Output is correct
2	Correct	1 ms	668 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	1 ms	724 KB	Output is correct
5	Correct	244 ms	54372 KB	Output is correct
6	Correct	85 ms	27532 KB	Output is correct
7	Correct	27 ms	13972 KB	Output is correct
8	Correct	4 ms	3924 KB	Output is correct
9	Correct	1 ms	740 KB	Output is correct
10	Correct	1 ms	1440 KB	Output is correct
11	Correct	1 ms	980 KB	Output is correct
12	Correct	1 ms	596 KB	Output is correct
13	Correct	1 ms	596 KB	Output is correct
14	Correct	1 ms	596 KB	Output is correct
15	Correct	1 ms	724 KB	Output is correct
16	Incorrect	1 ms	664 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	676 KB	Output is correct
2	Correct	1 ms	596 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	0 ms	596 KB	Output is correct
6	Correct	0 ms	596 KB	Output is correct
7	Incorrect	1 ms	724 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	852 KB	Output is correct
2	Correct	1 ms	852 KB	Output is correct
3	Correct	1 ms	1052 KB	Output is correct
4	Correct	1 ms	980 KB	Output is correct
5	Correct	1 ms	1364 KB	Output is correct
6	Correct	1 ms	980 KB	Output is correct
7	Correct	1 ms	980 KB	Output is correct
8	Correct	1 ms	980 KB	Output is correct
9	Correct	1 ms	980 KB	Output is correct
10	Correct	1 ms	852 KB	Output is correct
11	Correct	1 ms	980 KB	Output is correct
12	Correct	2 ms	1492 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	980 KB	Output is correct
16	Correct	2 ms	1492 KB	Output is correct
17	Correct	1 ms	980 KB	Output is correct
18	Correct	1 ms	980 KB	Output is correct
19	Correct	1 ms	1492 KB	Output is correct
20	Correct	1 ms	1492 KB	Output is correct
21	Correct	1 ms	1056 KB	Output is correct
22	Correct	1 ms	1432 KB	Output is correct
23	Correct	1 ms	852 KB	Output is correct
24	Correct	2 ms	980 KB	Output is correct
25	Correct	2 ms	1492 KB	Output is correct
26	Correct	2 ms	852 KB	Output is correct
27	Correct	1 ms	980 KB	Output is correct
28	Correct	1 ms	1052 KB	Output is correct
29	Correct	1 ms	980 KB	Output is correct
30	Correct	2 ms	1052 KB	Output is correct
31	Correct	1 ms	980 KB	Output is correct
32	Correct	2 ms	1492 KB	Output is correct
33	Correct	1 ms	1492 KB	Output is correct
34	Correct	1 ms	1440 KB	Output is correct
35	Correct	1 ms	1364 KB	Output is correct
36	Correct	1 ms	980 KB	Output is correct
37	Correct	2 ms	1492 KB	Output is correct

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2200 KB	Output is correct
2	Correct	3 ms	2260 KB	Output is correct
3	Correct	7 ms	3924 KB	Output is correct
4	Correct	257 ms	54420 KB	Output is correct
5	Correct	82 ms	27472 KB	Output is correct
6	Correct	84 ms	27484 KB	Output is correct
7	Correct	28 ms	13968 KB	Output is correct
8	Correct	29 ms	13976 KB	Output is correct
9	Correct	28 ms	14016 KB	Output is correct
10	Correct	30 ms	14036 KB	Output is correct
11	Correct	254 ms	54336 KB	Output is correct
12	Correct	77 ms	27364 KB	Output is correct
13	Correct	10 ms	7252 KB	Output is correct
14	Correct	241 ms	54392 KB	Output is correct
15	Correct	3 ms	2260 KB	Output is correct
16	Correct	3 ms	2260 KB	Output is correct
17	Correct	28 ms	14028 KB	Output is correct
18	Correct	6 ms	4052 KB	Output is correct
19	Correct	11 ms	7280 KB	Output is correct
20	Correct	255 ms	54380 KB	Output is correct
21	Correct	109 ms	27408 KB	Output is correct
22	Correct	4 ms	2260 KB	Output is correct
23	Correct	15 ms	7380 KB	Output is correct
24	Correct	930 ms	108392 KB	Output is correct
25	Correct	290 ms	54452 KB	Output is correct
26	Correct	909 ms	108420 KB	Output is correct
27	Correct	854 ms	108416 KB	Output is correct
28	Correct	821 ms	108480 KB	Output is correct
29	Correct	827 ms	108492 KB	Output is correct
30	Correct	839 ms	108384 KB	Output is correct
31	Correct	842 ms	108308 KB	Output is correct
32	Correct	792 ms	108344 KB	Output is correct
33	Correct	271 ms	54408 KB	Output is correct
34	Correct	834 ms	108436 KB	Output is correct
35	Correct	831 ms	108320 KB	Output is correct
36	Correct	834 ms	108416 KB	Output is correct
37	Correct	253 ms	54328 KB	Output is correct
38	Correct	248 ms	54452 KB	Output is correct
39	Correct	87 ms	27388 KB	Output is correct
40	Correct	857 ms	108568 KB	Output is correct
41	Correct	88 ms	27500 KB	Output is correct
42	Correct	864 ms	108392 KB	Output is correct
43	Correct	834 ms	108400 KB	Output is correct
44	Correct	833 ms	108428 KB	Output is correct
45	Correct	830 ms	108336 KB	Output is correct
46	Correct	294 ms	54448 KB	Output is correct
47	Correct	830 ms	108424 KB	Output is correct
48	Correct	855 ms	108380 KB	Output is correct
49	Correct	906 ms	108408 KB	Output is correct
50	Correct	99 ms	27480 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	732 KB	Output is correct
2	Incorrect	1 ms	724 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

답안 #590797

Compilation message

Subtask #1 0 / 10.0

Subtask #2 0 / 7.0

Subtask #3 0 / 11.0

Subtask #4 17.0 / 17.0

Subtask #5 35.0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
0 / 10.0

Subtask #2
0 / 7.0

Subtask #3
0 / 11.0

Subtask #4
17.0 / 17.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0