Submission #626241

#	Time	Username	Problem	Language	Result	Execution time	Memory
626241		oolimry	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	16 ms	1620 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint,lint> ii;

int level[21] = {0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,8};

int levelToW[11][5005];

vector<vector<int> > ans;

void recurse(int s, int e, int L, int w){
	//cerr << s << " " << e << " " << L << " " << w << endl;
	assert(level[w] == L);
	for(int i = s;i <= e;i++){
		levelToW[L][i] = w;
	}
	
	int inspect = (level[w]%2) + 1;
	
	ans[w][s] = -inspect;
	ans[w][e] = -(3-inspect);
	if(e == 4999) show2(w, inspect);
	
	
	if(s >= e-1) return;
	
	s++; e--;
	
	if(w >= 16){
		int nextw = max(19,w+1);
		recurse(s,e,L+1,nextw);
		ans[nextw][s-1] = -(3-inspect);
		ans[nextw][e+1] = -inspect;
		for(int i = s;i <= e;i++) ans[w][i] = max(19,w+1);
		return;
	}
	
	int len = e-s+1;
	len = (len+2)/3;
	
	int neww = ((w-1)/3+1)*3+1;
	if(w == 0) neww = 1;
	
	int m1 = s+len;
	int m2 = s+2*len;

	recurse(s,m1-1, L+1,neww);
	recurse(m1,m2-1, L+1, neww+1);
	recurse(m2,e, L+1, neww+2);
	
	for(int j = 0;j < 3;j++){
		ans[neww+j][s-1] = -(3-inspect);
		ans[neww+j][e+1] = -inspect;
	}
}


std::vector<std::vector<int>> devise_strategy(int N) {
	for(int i = 0;i < 21;i++){
		ans.push_back({});
		ans.back().resize(5001);
		fill(all(ans.back()), -4);
	}
	recurse(1,5000,0,0);
	
	for(int w = 0;w < 21;w++){
		ans[w][0] = level[w]%2;
		int inspect = ans[w][0] + 1;
		
		for(int i = 1;i <= N;i++){
			if(ans[w][i] != -4) continue;
			
			int L = level[w];
			int cur = levelToW[L][i];
			
			if(w==0 and i == 4) show(levelToW[L+1][i]);
			
			if(cur < w) ans[w][i] = -inspect;
			else if(cur > w) ans[w][i] = -(3-inspect);
			else ans[w][i] = levelToW[L+1][i];
		}
		while(sz(ans[w]) > N+1) ans[w].pop_back();
	}
	
	return ans;
}

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