Submission #1321239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321239		mirasm	Prisoner Challenge (IOI22_prison)	C++20	53 / 100	8 ms	1336 KiB

prison

#include "prison.h"

#include<bits/stdc++.h>


using namespace std;



vector<vector<int>> devise_strategy (int n) {
        vector<vector<int>> ans(29, vector<int>(n + 1));

        ans[0][0] = 0;
        for (int i = 1; i <= n; i++) {
                if (i >> 12 & 1) ans[0][i] = 2;
                else ans[0][i] = 1;
        }
        vector<int> b(29);
        b[1] = 12;
        b[2] = 12;
        for (int v = 1; v < 29; v += 2) {
                int bit = b[v];
                if (bit % 2) {
                        ans[v][0] = 0;
                        ans[v + 1][0] = 0;
                }
                else {
                        ans[v][0] = 1;
                        ans[v + 1][0] = 1;
                }

                for (int i = 1; i <= n; i++) {
                        if (i >> bit & 1) {
                                ans[v][i] = (bit % 2 ? -2 : -1);
                                if (bit) {
                                        if (i >> (bit - 1) & 1) {
                                                ans[v + 1][i] = (13 - bit) * 2 + 2;
                                        }
                                        else  {
                                                ans[v + 1][i] = (13 - bit) * 2 + 1;
                                        }
                                }
                                else {
                                        ans[v + 1][i] = -1;
                                }
                        }
                        else {
                                ans[v + 1][i] = (bit % 2 ? -1 : -2);
                                if (bit) {
                                        if (i >> (bit - 1) & 1) 
                                                ans[v][i] = (13 - bit) * 2 + 2;
                                        else ans[v][i] = (13 - bit) * 2 + 1;
                                }
                                else {
                                        ans[v][i] = -1;
                                }
                        }
                        if (bit) {
                                b[(13 - bit) * 2 + 1] = b[(13 - bit) * 2 + 1] = bit - 1;
                        }
                }
                // cout << v << " : ";
                // for (auto e : ans[v]) {
                //         cout << e << ' ';
                // }
                // cout << endl;

                // cout << v + 1 << " : ";
                // for (auto e : ans[v + 1]) {
                //         cout << e << ' ';
                // }
                // cout << endl;

        }
        return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 43 / 90