Submission #830338

#	Time	Username	Problem	Language	Result	Execution time	Memory
830338		7mody	Prisoner Challenge (IOI22_prison)	C++17	56 / 100	16 ms	1108 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
 
vector<vector<int>> devise_strategy(int n) {
    vector<vector<int>> ans(27,vector<int>(n+1));
    for(int i=1;i<=n;i++){
        int curr=1;
        curr+=(i>>12)&1;
        ans[0][i]=curr;
    }
    int move=11;
    for(int i=1; i <=26;i++){
        int curr=((i+1)/2)*2 + 1;
        int bag=(curr/2)%2;
        ans[i][0]=bag;
        for(int j=1; j <=n;j++){
            curr=((i+1)/2)*2 + 1;
            if(i%2){
                if(((j>>(move+1))&1)){
                    if(bag) ans[i][j]=-1;
                    else ans[i][j]=-2;
                } else{
                    curr+=((j>>move)&1);
                    ans[i][j]=min(curr,26);
                }
            } else{
                if(((j>>(move+1))&1) == 0){
                    if(bag) ans[i][j]=-2;
                    else ans[i][j]=-1;
                } else{
                    curr+=((j>>move)&1);
                    ans[i][j]=min(curr,26);
                }
            }
        }
        if(i%2==0) move--;
        // cout << move << ' ';
    }
    return ans;
}
 
// void solve(){
//     int n; cin >> n;
//     int counter=0;
//     vector<vector<int>> arr=devise_strategy(n);
//     // for(auto c : arr){
//     //     cout << counter << "       ";
//     //     for(auto i : c) cout << i << ' ';
//     //     cout << endl;
//     //     counter++;
//     // }
//     int curr=0;
//     int a=1000,b=1024;
//     while(true){
//         if(arr[curr][0]==0) curr=arr[curr][a];
//         else curr=arr[curr][b];
//         if(curr<0){
//             cout << curr << endl;
//             break;
//         }
//         // cout << curr << ' ';
//     }
// }
 
// int main(){
//     ios::sync_with_stdio(false);cout.tie();cin.tie();
//     int t=1;
//     // cin >> t;
//     while(t--){
//         solve();
//     }
// }

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