Submission #626098

#	Time	Username	Problem	Language	Result	Execution time	Memory
626098		errorgorn	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	20 ms	1048 KiB

prison

#include "prison.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
int n;
int p3[10];
 
vector<vector<signed>> devise_strategy(signed N){
	n=N;
 
	p3[2]=8;
	rep(x,3,10) p3[x]=p3[x-1]*3;
 
	vector<vector<signed> > res;
 
	rep(x,0,22){
		vector<signed> temp;
 
		if (x==0){
			temp.pub(0);
			rep(x,1,n+1) temp.pub(1+x/p3[7]%3);
		}
		else if (x==19){ //[1,2,3]
			temp.pub(1);
			rep(x,1,n+1){
				int res=x%8;
				if (res<=1) temp.pub(-2);
				else if (3<=res) temp.pub(-1);
				else temp.pub(21);
			}
		}
		else if (x==20){ //[4,5,6]
			temp.pub(1);
			rep(x,1,n+1){
				int res=x%8;
				if (res<=4) temp.pub(-2);
				else if (6<=res) temp.pub(-1);
				else temp.pub(21);
			}
		}
		else if (x==21){
			temp.pub(0);
			rep(x,1,n+1){
				int res=x%8;
				if (res==1 || res==4) temp.pub(-1);
				else if (res==3 || res==6) temp.pub(-2);
				else temp.pub(0);
			}
		}
		else{
			int layer=7-(x-1)/3;
			int residue=(x-1)%3;
			int nxt=(8-layer)*3+1;
 
			int layerp=layer%2;
			temp.pub(layerp);
 
			//cout<<x<<" "<<layer<<" "<<temp[0]<<endl;
			//cout<<p3[layer-1]<<" "<<p3[layer]<<endl;
 
			rep(x,1,n+1){
				int res2=x/p3[layer]%3;
 
				if (res2<residue) temp.pub(~(layerp));
				else if (res2>residue) temp.pub(~(layerp^1));
				else{
					if (layer==2){
						int res1=x%8;
						if (res1==0) temp.pub(~(layerp));
						else if (res1==7) temp.pub(~(layerp^1));
						else if (res1<=3) temp.pub(19);
						else temp.pub(20);
					}
					else{
						int res1=x/p3[layer-1]%3;
						temp.pub(nxt+res1);
					}
				}
			}
		}
 
		res.pub(temp);
	}
 
	return res;
}

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