Submission #676296

#	Time	Username	Problem	Language	Result	Execution time	Memory
676296		MilosMilutinovic	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	1 ms	296 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
const int M=27;
int seq[]={3,3,3,3,3,3,3,3,3};
int sum[]={0,3,6,9,12,15,18,21,24,27};
int f[M];
vector<vector<int>> ans;
int get_bit(int x,int i){i=7-i;while(i--)x/=3;return x%3;}
void Solve(int l,int r,int x){
	//printf("l=%d r=%d x=%d\n",l,r,x);
	ans[x][l]=(f[x]%2==0?-1:-2);
	ans[x][r]=(f[x]%2==0?-2:-1);
	if(l+1>=r)return;
	map<int,vector<int>> mp;
	for(int i=l+1;i<r;i++){
		int b=get_bit(i,f[i]-1);
		if(x==0){
			ans[x][i]=b+1;
			continue;
		}
		int p=x-sum[f[i]-1]-1;
		int q=get_bit(i,f[i]-2);
		if(p<q){
			ans[x][i]=(f[x]%2==0?-1:-2);
			continue;
		}
		if(p>q){
			ans[x][i]=(f[x]%2==0?-2:-1);
			continue;
		}
		ans[x][i]=(sum[f[x]-1]+1+b);
		mp[ans[x][i]].push_back(i);
	}
	for(auto&p:mp){
		int mn=1e9,mx=-1e9;
		for(int x:p.second)mn=min(mn,x),mx=max(mx,x);
		if(mn<=mx)Solve(mn,mx,p.first);
	}
}
vector<vector<int>> devise_strategy(int N){
	ans.resize(M);
	for(int i=0;i<M;i++)ans[i].resize(N+1);
	int ptr=0;
	ans[0][0]=0;
	for(int i=1;i<M;i++){
		while(sum[ptr]<i)ptr++;
		f[i]=ptr;
	}
	Solve(1,N,0);
	return ans;
}

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