Submission #1022894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022894		vjudge1	Prisoner Challenge (IOI22_prison)	C++17	30 / 100	39 ms	2388 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

#define ll long long
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define lb lower_bound
#define ub upper_bound

const int MAX=2e5+10;

int getBit(int x,int b){
    vector<int> a;
    while(x){
        a.pb(x%3);
        x/=3;
    }
    while(sz(a)<=b)a.pb(0);
    return a[b];
}

vector<vector<int>> devise_strategy(int N) {
    vector<vector<int>> ans;
    int c=60;
    int B=9;
    ans.resize(c);
    // for(int i=0;i<=B;i++){
    //     cout<<getBit(2,i)<<" ";
    // }
    // cout<<"\n";
    for(int i=0;i<c;i++){
        ans[i].resize(N+1);
        for(int j=0;j<=N;j++){
            if(j==0){
                if(i%4==0)ans[i][j]=0;
                else ans[i][j]=1;
                continue;
            }
            if(i%4==0){
                int cntBits=i/4;
                if(cntBits>B){
                    ans[i][j]=-1;
                    continue;
                }
                int f=getBit(j,B-cntBits);
                f++;
                ans[i][j]=cntBits*4+f;
                // cout<<i<<" "<<j<<" "<<ans[i][j]<<"\n";
            }
            else{
                int cntBits=i/4;
                if(cntBits>B){
                    ans[i][j]=-1;
                    continue;
                }
                int f=getBit(j,B-cntBits);
                if(f+1==i%4){
                    ans[i][j]=(cntBits+1)*4;
                    // cout<<i<<" "<<j<<" "<<ans[i][j]<<"\n";
                }
                else{
                    if(f+1<i%4)ans[i][j]=-2;
                    else ans[i][j]=-1;
                }
            }

        }
    }
    return ans;
}

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