Submission #825727

#	Time	Username	Problem	Language	Result	Execution time	Memory
825727		alvingogo	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1424 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

int n;
vector<vector<int> > ans;
vector<vector<int>> devise_strategy(int N) {
    const int g[]={2,6,14,30,92,278,836,2510,5022};
    int w=0;
    for(;;w++){
        if(g[w]>=N){
            n=g[w];
            break;
        }
    }
    w--;
    int ss=w;
    vector<int> pz(n+1);
    pz[0]=0;
    for(int i=1;i<=n;i++){
        int s=(i-1)%g[w+1];
        if(s==0){
            pz[i]=-1;
        }
        else if(s==n-1){
            pz[i]=-2;
        }
        else{
            pz[i]=(s-1)/g[w]+1;
        }
    }
    ans.push_back(pz);
    int q=1+(g[w+1]-2)/g[w],l=2;
    int fl=1;
    vector<int> vis(n+1);
    vis[1]=-1;
    vis[n]=1;
    for(w--;w>=-1;w--){
        int p=(g[w+2]-2)/g[w+1];
        vector<vector<int> > pp(p);
        for(int i=0;i<p;i++){
            pp[i].resize(n+1);
            pp[i][0]=fl;
        }
        for(int j=1;j<=n;j++){
            if(!vis[j]){
                for(int i=0;i<p;i++){
                    int j2=j;
                    for(int b=ss-1;b>=w;b--){
                        j2--;
                        j2%=g[b+2];
                    }
                    int s1=(j2-1)/g[w+1];
                    if(s1<i){
                        pp[i][j]=-1-fl;
                    }
                    else if(s1>i){
                        pp[i][j]=fl-2;
                    }
                    else{
                        int s2=(j2-1+g[w+1])%g[w+1];
                        if(s2==0){
                            pp[i][j]=-1-fl;
                            vis[j]=-1;
                        }
                        else if(s2==g[w+1]-1){
                            pp[i][j]=fl-2;
                            vis[j]=1;
                        }
                        else{
                            pp[i][j]=q+(s2-1)/g[w];
                        }
                    }
                }
            }
            else{
                for(int i=0;i<p;i++){
                    if(vis[j]==1){
                        pp[i][j]=fl-2;
                    }
                    else{
                        pp[i][j]=-1-fl;
                    }
                }
            }
        }
        for(auto h:pp){
            ans.push_back(h);
        }
        if(w<0){
            break;
        }
        int s=(g[w+1]-2)/g[w];
        q+=s;
        fl^=1;
        l++;
    }
    for(auto &h:ans){
        while(h.size()>(N+1)){
            h.pop_back();
        }
    }
    return ans;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:102:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |         while(h.size()>(N+1)){
      |               ~~~~~~~~^~~~~~

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