Submission #885931

#	Time	Username	Problem	Language	Result	Execution time	Memory
885931		thinknoexit	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	10 ms	1116 KiB

prison

#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
using ll = long long;

vector<vector<int>> devise_strategy(int n) {
    vector<vector<int>> ans(25, vector<int>(n + 1));
    ans[0][0] = 0;
    for (int i = 1;i <= n;i++) {
        if ((i >> 12) & 1) ans[0][i] = 1;
        else ans[0][i] = 13;
    }
    for (int i = 1;i <= 11;i++) {
        ans[i][0] = ans[i + 12][0] = i & 1;
        int b = 13 - i;
        for (int j = 1;j <= n;j++) {
            if ((j >> b) & 1) {
                if (ans[i][0]) ans[i + 12][j] = -1;
                else ans[i + 12][j] = -2;
                if ((j >> (b - 1)) & 1) {
                    ans[i][j] = i + 1;
                }
                else {
                    ans[i][j] = 12 + i + 1;
                }
            }
            else {
                if (ans[i][0]) ans[i][j] = -2;
                else ans[i][j] = -1;
                if ((j >> (b - 1)) & 1) {
                    ans[i + 12][j] = i + 1;
                }
                else {
                    ans[i + 12][j] = 12 + i + 1;
                }
            }
        }
    }
    ans[12][0] = ans[24][0] = 0;
    for (int j = 1;j <= n;j++) {
        if ((j >> 1) & 1) {
            ans[24][j] = -2;
            if (j & 1) {
                ans[12][j] = -2;
            }
            else {
                ans[12][j] = -1;
            }
        }
        else {
            ans[12][j] = -1;
            if (j & 1) {
                ans[24][j] = -2;
            }
            else {
                ans[24][j] = -1;
            }
        }

    }
    return ans;
}

// int main() {
//     int n = 5000, a, b;
//     vector<vector<int>> adj = devise_strategy(n);
//     for (int i = 1;i <= 5000;i++) {
//         for (int j = 1;j <= 5000;j++) {
//             if (i == j) continue;
//             int now = 0;
//             int cnt = 0;
//             while (now >= 0 && cnt <= 500) {
//                 if (adj[now][0] == 0) {
//                     now = adj[now][i];
//                 }
//                 else {
//                     now = adj[now][j];
//                 }
//                 cnt++;
//             }
//             if (i < j && now == -2) {
//                 cout << i << ' ' << j << '\n';
//             }
//             else if (i > j && now == -1) {
//                 cout << i << ' ' << j << '\n';
//             }
//         }
//     }
//     // int i = a, j = b;
//     // int now = 0;
//     // int cnt = 0;
//     // while (now >= 0 && cnt <= 500) {
//     //     cout << now << ' ';
//     //     if (adj[now][0] == 0) {
//     //         now = adj[now][i];
//     //     }
//     //     else {
//     //         now = adj[now][j];
//     //     }
//     //     cnt++;
//     // }
//     // cout << now << ' ';
// }

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