Submission #640339

#	Time	Username	Problem	Language	Result	Execution time	Memory
640339		jamezzz	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	11 ms	1748 KiB

prison

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

#define fi first
#define se second
#define pf printf
#define pb push_back
typedef vector<int> vi;
typedef pair<int,int> ii;

int n,dp[25],best[25];
int vis[25][6000];
vector<int> split,start;
vector<vi> s;

void dnc(int num,int stage,int tosee,int l,int r){
	if(vis[num][l])return;
	//pf("dnc: %d %d %d %d %d ",num,stage,tosee,l,r);
	vis[num][l]=1;
	int sz=(r-l-1)/split[stage];
	vector<ii> rng;
	for(int i=0;i<split[stage];++i){
		rng.pb({l+1+i*sz,l+(i+1)*sz});
		//pf("(%d %d) ",l+1+i*sz,l+(i+1)*sz);
	}
	//pf("\n");
	if(num==0){
		s[num][0]=0;//identify A
		for(int i=l;i<=r;++i){
			if(n<i)break;
			if(i==l)s[num][i]=-1;//A smaller
			else if(i==r)s[num][i]=-2;//B smaller
			else{
				for(int j=0;j<split[stage];++j){
					auto[nl,nr]=rng[j];
					if(nl<=i&&i<=nr){
						s[num][i]=start[stage]+j;
						dnc(start[stage]+j,0,1,l,r);
					}
				}
			}
		}
	}
	else{
		if(tosee==0)s[num][0]=0;//identify A
		else s[num][0]=1;//identify B
		for(int i=l;i<=r;++i){
			if(n<i)break;
			if(i==l)s[num][i]=(tosee==0)?-1:-2;//if we see A, A smaller else B smaller
			else if(i==r)s[num][i]=(tosee==0)?-2:-1;//if we see A, B smaller else A smaller
			else{
				int pv=num-start[stage];
				for(int j=0;j<split[stage];++j){
					auto[nl,nr]=rng[j];
					if(nl<=i&&i<=nr){
						if(pv<j)s[num][i]=(tosee==0)?-2:-1;//if we see A, then B smaller else A smaller
						else if(j<pv)s[num][i]=(tosee==0)?-1:-2;//if we see A, then A smaller else B smaller
						else{
							if(i==nl)s[num][i]=(tosee==0)?-1:-2;//if we see A, then A smaller else B smaller
							else if(i==nr)s[num][i]=(tosee==0)?-2:-1;//if we see A, then B smaller else A smaller
							else{
								vector<ii> nrng;
								int sz2=(nr-nl-1)/split[stage+1];
								for(int k=0;k<split[stage+1];++k){
									int nnl=nl+1+k*sz2,nnr=nl+(k+1)*sz2;
									if(nnl<=i&&i<=nnr){
										s[num][i]=start[stage+1]+k;
										dnc(start[stage+1]+k,stage+1,1-tosee,nl,nr);
									}
								}
							}
						}
					}
				}
			}
		}
	}
}

vector<vi> devise_strategy(int N){
	n=N;
	dp[0]=2;
	for(int i=1;i<=20;++i){
		for(int k=1;k<=i;++k){
			if(dp[i-k]*k+2>dp[i]){
				dp[i]=dp[i-k]*k+2;
				best[i]=k;
			}
		}
	}
	int cur=20;
	start.pb(1);
	while(cur){
		split.pb(best[cur]);
		start.pb(start.back()+best[cur]);
		cur-=best[cur];
	}
	//for(int i:split)pf("%d ",i);pf("\n");
	//for(int i:start)pf("%d ",i);pf("\n");
	s.resize(21);
	for(int i=0;i<=20;++i){
		s[i].resize(n+1);
	}
	dnc(0,0,0,1,dp[20]);
	//for(int i=0;i<=20;++i){
		//pf("%d: ",i);
		//for(int j=0;j<10;++j)pf("%d ",s[i][j]);
		//pf("\n");
	//}
	return s;
}

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