Submission #834862

#	Time	Username	Problem	Language	Result	Execution time	Memory
834862		gagik_2007	Prisoner Challenge (IOI22_prison)	C++17	48.50 / 100	14 ms	1364 KiB

prison

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=5007;
ll n,m,k;
ll pw[N];
int ind=0;

void comp_result(vector<vector<int>>&ans, int cur){
    // cur = (k+1)*step+rem
    // rem=0 -> A
    // rem!=0 -> B, A_(rem-1)
    int mnac=cur%(k+1);
    if(mnac==0){
        ans[cur][0]=0;
    }
    else{
        ans[cur][0]=1;
        // mnac-1 -> the group of the bag A
    }
    int tmp=cur;
    cur/=(k+1); // the current step (k^(ind-cur))
                // ind-cur>=1 (don't need more), => cur<=ind-1 => num<=(k+1)*(ind-1)
    for(int i=1;i<=n;i++){
        int vl=i;
        vl%=pw[ind-cur+1];
        vl/=pw[ind-cur];
        if(mnac!=0){
            if(vl<mnac-1){
                ans[tmp][i]=-2;
            }
            else if(vl>mnac-1){
                ans[tmp][i]=-1;
            }
            else{
                ans[tmp][i]=(k+1)*(cur+1);
            }
        }
        else{
            int res=(k+1)*cur+vl+1;
            ans[tmp][i]=res;
        }
        // cout<<ans[tmp][i]<<" ";
        if(ans[tmp][i]==(k+1)*(ind+1))ans[tmp][i]=0;
        // if(ans[tmp][i]>(k+1)*(ind+1))cout<<tmp<<" "<<i<<": "<<ans[tmp][i]<<endl;
    }
    // cout<<endl;
}

vector<vector<int>> devise_strategy(int NN) {
    n=NN;
    k=3;
    pw[0]=1;
    while(pw[ind]<=n){
        ind++;
        pw[ind]=pw[ind-1]*k;
    }
    ind--;
    // cout<<ind<<endl;
    vector<vector<int>>ans((k+1)*(ind+1),vector<int>(n+1,0));
    for(int i=0;i<(k+1)*(ind+1);i++){
        comp_result(ans,i);
    }
    return ans;
}

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