oj.uz

Submission #1115011

# Submission time Handle Problem Language Result Execution time Memory
1115011 2024-11-19T22:04:37 Z MisterReaper L-triominoes (CEOI21_ltriominoes) C++17
28 / 100
 1834 ms 592 KB 
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

bool has(int m, int k) {
    return m >> k & 1;
}

struct matrix {
    constexpr static int n = 1 << 6;
    int mat[n][n];
    matrix() {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                mat[i][j] = 0;
            }
        }
    }
    matrix operator* (const matrix rhs) {
        matrix res;
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < n; ++k) {
                for (int j = 0; j < n; ++j) {
                    res.mat[i][j] |= mat[i][k] && rhs.mat[k][j];
                }
            }
        }
        return res;
    }
};

matrix init;

void work(int n) {
    auto dfs = [&](auto&& self, int s, int mask, int now, int nmask) -> void {
        if (s == n) {
            if (now == (1 << n) - 1 && nmask < (1 << n)) {
                #ifdef DEBUG
                    debug(s, std::bitset<5>(now));
                    std::cerr << std::bitset<5>(nmask) << '\n';
                    std::cerr << std::bitset<5>(mask) << '\n';
                    std::cerr << '\n';
                #endif
                init.mat[mask][nmask] = true;
            }
            return;
        }
        if (now >> s & 1) {
            self(self, s + 1, mask, now, nmask);
            return;
        }
        // X.
        // ..
        {
            if (!has(nmask, s) && !has(now, s + 1)) {
                self(self, s + 1, mask, now | (3 << s), nmask | (1 << s));
            }
        }
        // .X
        // ..
        {
            if (!has(nmask, s + 1) && !has(now, s + 1)) {
                self(self, s + 1, mask, now | (3 << s), nmask | (2 << s));
            }
        }
        // ..
        // .X
        {
            if (s != 0 && !has(nmask, s) && !has(nmask, s - 1)) {
                self(self, s + 1, mask, now | (1 << s), nmask | (3 << (s - 1)));
            }
        }
        // ..
        // X.
        {
            if (!has(nmask, s) && !has(nmask, s + 1)) {
                self(self, s + 1, mask, now | (1 << s), nmask | (3 << s));
            }
        }
    };
    // dfs(dfs, 0, 1, 1, 0);
    // exit(0);
    for (int m = 0; m < (1 << n); ++m) {
        dfs(dfs, 0, m, m, 0);
    }
}

matrix power(matrix a, int b) {
    matrix res;
    for (int i = 0; i < matrix::n; ++i) {
        res.mat[i][i] = true;
    }
    while (b) {
        if (b & 1) {
            res = res * a;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int W, H, K;
    std::cin >> W >> H >> K;

    std::vector<int> A(K), B(K);
    for (int i = 0; i < K; ++i) {
        std::cin >> A[i] >> B[i];
        --A[i], --B[i];
    }

    std::vector<int> ord(K);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) {
        return B[lhs] < B[rhs];
    });

    work(W);
    
    std::vector<std::pair<int, int>> ss;
    ss.emplace_back(0, 0);
    for (int i = 0, j = 0; i < K; i = j) {
        int mask = 0;
        while (j < K && B[ord[i]] == B[ord[j]]) {
            mask |= 1 << A[ord[j]];
            ++j;
        }
        ss.emplace_back(B[ord[i]], mask);
    }
    ss.emplace_back(H, (1 << W) - 1);

    debug(ss);

    std::vector<bool> dp(1 << W);
    dp[0] = true;

    for (int iss = 0; iss + 1 < ss.size(); ++iss) {
        int len = ss[iss + 1].first - ss[iss].first;
        int row_mask = ss[iss].second;
        std::vector<bool> new_dp(1 << W);

        debug("wtf power", len);
        matrix matx = power(init, len);
        debug("oh ok bro");
        #ifdef DEBUG
            std::cerr << "debug:\n";
            for (int i = 0; i < (1 << W); ++i) {
                if (dp[i]) {
                    if (i & row_mask) {
                        continue;
                    }
                    for (int j = 0; j < (1 << W); ++j) {
                        if (matx.mat[i | row_mask][j]) {
                            std::cerr << std::bitset<5>(i) << '\n';
                            std::cerr << std::bitset<5>(j) << '\n';
                            std::cerr << '\n';
                        }
                    }
                }
            }
            std::cerr << "i am here\n";
            for (int i = 0; i < (1 << W); ++i) {
                if (dp[i]) {
                    if (i & row_mask) {
                        continue;
                    } 
                    std::cerr << std::bitset<5>(i) << '\n';
                }
            }
        #endif

        for (int i = 0; i < (1 << W); ++i) {
            if (i & row_mask || !dp[i]) {
                continue;
            }
            for (int j = 0; j < (1 << W); ++j) {
                if (matx.mat[i | row_mask][j]) {
                    debug(std::bitset<5>(i), std::bitset<5>(j));
                }
                new_dp[j] = new_dp[j] | (dp[i] & matx.mat[i | row_mask][j]);
            }
        }

        dp.swap(new_dp);
        debug(dp);
    }

    std::cout << (dp[0] ? "YES" : "NO") << '\n';

    return 0;
}

Compilation message

ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:147:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for (int iss = 0; iss + 1 < ss.size(); ++iss) {
      |                       ~~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 336 KB Output is correct
2 Correct 14 ms 544 KB Output is correct
3 Correct 10 ms 336 KB Output is correct
4 Correct 143 ms 336 KB Output is correct
5 Correct 125 ms 336 KB Output is correct
6 Correct 159 ms 336 KB Output is correct
7 Runtime error 7 ms 592 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 336 KB Output is correct
2 Correct 13 ms 508 KB Output is correct
3 Correct 10 ms 336 KB Output is correct
4 Correct 35 ms 336 KB Output is correct
5 Correct 24 ms 336 KB Output is correct
6 Correct 24 ms 336 KB Output is correct
7 Correct 11 ms 488 KB Output is correct
8 Correct 39 ms 336 KB Output is correct
9 Correct 101 ms 336 KB Output is correct
10 Correct 28 ms 336 KB Output is correct
11 Correct 367 ms 336 KB Output is correct
12 Correct 29 ms 336 KB Output is correct
13 Correct 25 ms 336 KB Output is correct
14 Correct 158 ms 336 KB Output is correct
15 Correct 72 ms 336 KB Output is correct
16 Correct 154 ms 336 KB Output is correct
17 Correct 1278 ms 508 KB Output is correct
18 Correct 54 ms 336 KB Output is correct
19 Correct 10 ms 336 KB Output is correct
20 Correct 1327 ms 336 KB Output is correct
21 Correct 11 ms 336 KB Output is correct
22 Correct 21 ms 532 KB Output is correct
23 Correct 35 ms 544 KB Output is correct
24 Correct 12 ms 336 KB Output is correct
25 Correct 111 ms 336 KB Output is correct
26 Correct 764 ms 524 KB Output is correct
27 Correct 33 ms 336 KB Output is correct
28 Correct 10 ms 532 KB Output is correct
29 Correct 14 ms 336 KB Output is correct
30 Correct 1687 ms 532 KB Output is correct
31 Correct 1571 ms 532 KB Output is correct
32 Correct 66 ms 336 KB Output is correct
33 Correct 1531 ms 532 KB Output is correct
34 Correct 1615 ms 532 KB Output is correct
35 Correct 1690 ms 532 KB Output is correct
36 Correct 530 ms 336 KB Output is correct
37 Correct 1634 ms 532 KB Output is correct
38 Correct 1204 ms 336 KB Output is correct
39 Correct 1018 ms 532 KB Output is correct
40 Correct 1216 ms 528 KB Output is correct
41 Correct 1004 ms 528 KB Output is correct
42 Correct 410 ms 528 KB Output is correct
43 Correct 562 ms 336 KB Output is correct
44 Correct 295 ms 336 KB Output is correct
45 Correct 592 ms 504 KB Output is correct
46 Correct 274 ms 336 KB Output is correct
47 Correct 358 ms 532 KB Output is correct
48 Correct 234 ms 584 KB Output is correct
49 Correct 298 ms 336 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 504 KB Output is correct
2 Correct 163 ms 336 KB Output is correct
3 Correct 1363 ms 528 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 9 ms 504 KB Output is correct
6 Correct 25 ms 336 KB Output is correct
7 Correct 5 ms 536 KB Output is correct
8 Correct 7 ms 336 KB Output is correct
9 Correct 30 ms 336 KB Output is correct
10 Correct 1715 ms 536 KB Output is correct
11 Correct 1834 ms 540 KB Output is correct
12 Correct 1718 ms 536 KB Output is correct
13 Correct 1625 ms 532 KB Output is correct
14 Correct 1475 ms 532 KB Output is correct
15 Correct 1605 ms 528 KB Output is correct
16 Correct 1115 ms 548 KB Output is correct
17 Correct 1460 ms 336 KB Output is correct
18 Correct 1437 ms 592 KB Output is correct
19 Correct 919 ms 336 KB Output is correct
20 Correct 423 ms 336 KB Output is correct
21 Correct 432 ms 336 KB Output is correct
22 Correct 367 ms 336 KB Output is correct
23 Correct 851 ms 336 KB Output is correct
24 Correct 1375 ms 528 KB Output is correct
25 Correct 1196 ms 528 KB Output is correct
26 Correct 1316 ms 528 KB Output is correct
27 Correct 1231 ms 536 KB Output is correct
28 Correct 412 ms 336 KB Output is correct
29 Correct 1050 ms 532 KB Output is correct
30 Correct 518 ms 336 KB Output is correct
31 Correct 1419 ms 536 KB Output is correct
32 Correct 1166 ms 336 KB Output is correct
33 Correct 1134 ms 528 KB Output is correct
34 Correct 189 ms 336 KB Output is correct
35 Correct 243 ms 336 KB Output is correct
36 Correct 332 ms 336 KB Output is correct
37 Correct 217 ms 336 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 336 KB Output is correct
2 Correct 14 ms 544 KB Output is correct
3 Correct 10 ms 336 KB Output is correct
4 Correct 143 ms 336 KB Output is correct
5 Correct 125 ms 336 KB Output is correct
6 Correct 159 ms 336 KB Output is correct
7 Runtime error 7 ms 592 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -