oj.uz

Submission #1105099

# Submission time Handle Problem Language Result Execution time Memory
1105099 2024-10-25T11:12:48 Z fve5 Prisoner Challenge (IOI22_prison) C++17
100 / 100
 9 ms 1104 KB 
    #include <bits/stdc++.h>
    #include "prison.h"
    using namespace std;
     
    vector<vector<int>> devise_strategy(int N) {
        vector<vector<int>> ans;
     
        auto rec = [&](auto &&rec, int l, int r, int pl, int pr, bool fst, int st) -> void {
            if (ans.size() <= st)
                ans.resize(st + 1, vector<int>(N + 1));
            ans[st][0] = !fst;

            for (int i = pl; i <= l; i++)
                ans[st][i] = fst ? -1 : -2;
            for (int i = r - 1; i < pr; i++)
                ans[st][i] = fst ? -2 : -1;

            if (r - l <= 2)
                return;

            int rec_l = (st + 2) / 3 * 3 + 1;
            int rec_m = (st + 2) / 3 * 3 + 2;
            int rec_r = (st + 2) / 3 * 3 + 3;

            int len = (r - l - 2);
            int m1 = l + 1 + len / 3;
            int m2 = m1 + len / 3 + (len % 3 == 2);

            if (r - l <= 6) {
                m1 = (l + r) / 2;
                m2 = r - 1;
            }

            for (int i = l + 1; i < m1; i++)
                ans[st][i] = rec_l;
            for (int i = m1; i < m2; i++)
                ans[st][i] = rec_m;
            for (int i = m2; i < r - 1; i++)
                ans[st][i] = rec_r;

            rec(rec, l + 1, m1, l, r, !fst, rec_l);
            rec(rec, m1, m2, l, r, !fst, rec_m);
            if (r - l > 6)
                rec(rec, m2, r - 1, l, r, !fst, rec_r);
        };
     
        rec(rec, 1, N + 1, 1, N + 1, true, 0);

        return ans;
    }

Compilation message

prison.cpp: In instantiation of 'devise_strategy(int)::<lambda(auto:23&&, int, int, int, int, bool, int)> [with auto:23 = devise_strategy(int)::<lambda(auto:23&&, int, int, int, int, bool, int)>&]':
prison.cpp:47:45:   required from here
prison.cpp:9:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    9 |             if (ans.size() <= st)
      |                 ~~~~~~~~~~~^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 4 ms 688 KB Output is correct
5 Correct 7 ms 848 KB Output is correct
6 Correct 9 ms 1104 KB Output is correct
7 Correct 9 ms 1104 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 4 ms 592 KB Output is correct
12 Correct 7 ms 848 KB Output is correct