Submission #689680

#	Time	Username	Problem	Language	Result	Execution time	Memory
689680		lohacho	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	17 ms	1108 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>
using namespace std;

std::vector<std::vector<int>> devise_strategy(int N) {
    vector<vector<int>> ans(25, vector<int>(N + 1));
    ans[0][0] = 0;
    int sz = 1;
    while(sz * 2 < N){
        sz *= 2;
    }

    for(int i = 1; i <= sz; ++i){
        ans[0][i] = 1;
    }
    for(int i = sz + 1; i <= N; ++i){
        ans[0][i] = 2;
    }

    if(sz == 1){
        ans[0][1] = -1;
        ans[0][2] = -2;
    }

    for(int i = 1; i < (int)ans.size(); ++i){
        if(sz == 1){
            break;
        }

        int know = (i - 1) / 2 % 2;
        ans[i][0] = 1 - know;

        for(int j = 1; j <= N; ++j){
            if(i % 2 == (j - 1) / sz % 2){
                ans[i][j] = -1 - (know ^ ((j - 1) / sz % 2) ^ 1);
            }
            else{
                if(sz == 2){
                    ans[i][j] = -1 - (know ^ (j % 2));
                }
                else{
                    if((j - 1) % sz < sz / 2){
                        ans[i][j] = (i + 1) / 2 * 2 + 1;
                    }
                    else{
                        ans[i][j] = (i + 1) / 2 * 2 + 2;
                    }
                }
            }
        }

        if(i % 2 == 0){
            sz /= 2;
        }
    }

    // for(int i = 0; i < (int)ans.size(); ++i){
    //     for(int j = 0; j < (int)ans[i].size(); ++j){
    //         cout << ans[i][j] << ' ';
    //     }
    //     cout << endl;
    // }

    return ans;
}

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