Submission #626442

#	Time	Username	Problem	Language	Result	Execution time	Memory
626442		Kaitokid	Prisoner Challenge (IOI22_prison)	C++17	41 / 100	29 ms	1560 KiB

prison

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int> > devise_strategy(int N)
{
    int u=0;
    int d=N;
    while(d>1){u++;d/=2;}
    vector<vector<int> > s(3*u+1,vector<int>(N+1,0));
    for(int i=1;i<=u;i++)
    {
        s[i][0]=1;
        for(int j=1;j<=N;j++)
            if(j&(1<<i))s[i][j]=-1;
        else s[i][j]=2*u+i;
    }
    for(int i=1;i<=u;i++)
    {
        s[i+u][0]=1;
         for(int j=1;j<=N;j++)
            if(!(j&(1<<i)))s[i+u][j]=-2;
        else s[i+u][j]=2*u+i;
    }
    for(int i=2;i<=u;i++)
    {
        s[2*u+i][0]=0;
        for(int j=1;j<=N;j++)
            if(j&(1<<(i-1)))s[2*u+i][j]=u+i-1;
         else s[2*u+i][j]=i-1;
    }
    s[2*u+1][0]=0;
    for(int j=1;j<=N;j++)
        if((j&1))s[2*u+1][j]=-2;
    else s[2*u+1][j]=-1;
    s[0][0]=0;
    for(int j=1;j<=N;j++)
        if(j&(1<<u))s[0][j]=2*u;
     else s[0][j]=u;
     return s;
}

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