Submission #828338

#	Time	Username	Problem	Language	Result	Execution time	Memory
828338		ttamx	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	0 ms	272 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

const int N=5005;

int n;
vector<vector<int>> s;
int mx;

int calc(int l,int r,int pos){
	int sz=(r-l+3)/3;
	return (pos-l)/sz;
}

pair<int,int> get(int l,int r,int num){
	int sz=(r-l+3)/3;
	int nl=l+sz*num;
	int nr=l+sz*(num+1)-1;
	return {max(l,min(nl,r)),max(l,min(nr,r))};
}

void solve(array<int,2> l,array<int,2> r,int id,int cur,int d){
	if(l[cur]>=r[cur])return;
	set<tuple<array<int,2>,array<int,2>,int,int,int>> st;
	for(int x=0;x<3;x++){
		s[id][0]=cur;
		for(int j=l[cur];j<=r[cur];j++){
			int val=calc(l[cur],r[cur],j);
			if(val==x){
				auto [nl,nr]=get(l[cur],r[cur],x);
				if(j==nl){
					s[id][j]=-cur-1;
				}else if(j==nr){
					s[id][j]=cur-2;
				}else{
					int val2=calc(nl+1,nr-1,j);
					s[id][j]=d+3+val2;
					array<int,2> tl={nl,nl},tr={nr,nr};
					tl[cur]++;
					tr[cur]--;
					st.emplace(tl,tr,d+3+val2,cur^1,d+3);
				}
			}else if(val>x){
				s[id][j]=cur-2;
			}else{
				s[id][j]=-cur-1;
			}
		}
		id++;
	}
	mx=max(mx,id);
	for(auto [a,b,c,d,e]:st)solve(a,b,c,d,e);
}

vector<vector<int>> devise_strategy(int _n){
	n=_n;
	vector<int> pw(8);
	pw[0]=1;
	for(int i=1;i<9;i++)pw[i]=pw[i-1]*3;
	s=vector<vector<int>>(100,vector<int>(n+1));
	s[0][0]=0;
	for(int j=1;j<=n;j++){
		int val=calc(1,n,j);
		s[0][j]=val+1;
	}
	solve({1,1},{n,n},1,1,1);
	s.resize(mx);
	s.pop_back();
	s.pop_back();
	return s;
}

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