Submission #1105099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105099		fve5	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	1104 KiB

prison

    #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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 90 / 90