Submission #1171255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171255		thelegendary08	Prisoner Challenge (IOI22_prison)	C++17	10 / 100	3 ms	840 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vout(x) for(auto u : x)cout<<u<<' ';cout<<'\n';
using namespace std;
const vi divv = {3,3,3,3,3,2,2,1};
const vi ad = {1,4,7,10,13,16,19,20};
const vi chec = {0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,1,1,0};
vector<vi>v(21);
void solve(int l, int r, int layer, int dex){
	if(divv[layer] == 3){
		for(int j = ad[layer]; j<=ad[layer] + 2; j++){
			if(j > dex){
				for(int i = l; i<=r; i++){
					if(layer % 2 == 0){
						v[j][i] = -2;
					}
					else v[j][i] = -1;
				}
			}
			else if(j < dex){
				for(int i = l; i<=r; i++){
					if(layer % 2 == 0){
						v[j][i] = -1;
					}
					else v[j][i] = -2;
				}
			}
			else{
				if(divv[layer + 1] == 3){
					int a = l + (r - l + 1) / 3;
					int b = l + (r - l + 1) / 3 * 2;
					for(int i = l; i<=r; i++){
						if(i < a)v[j][i] = ad[layer + 1];
						else if(i < b)v[j][i] = ad[layer + 1] + 1;
						else v[j][i] = ad[layer + 1] + 2;
					}
					if(layer % 2 == 0){
						v[j][l] = -2;
						v[j][a-1] = -1;
						v[j][a] = -2;
						v[j][b-1] = -1;
						v[j][b] = -2;
						v[j][r] = -1;
					}
					else{
						v[j][l] = -1;
						v[j][a-1] = -2;
						v[j][a] = -1;
						v[j][b-1] = -2;
						v[j][b] = -1;
						v[j][r] = -2;
					}
					
					solve(l+1, a-2, layer + 1, ad[layer + 1]);
					solve(a+1, b-2, layer + 1, ad[layer + 1] + 1);
					solve(b+1, r-1, layer + 1, ad[layer + 1] + 2);
				}
				else{
					int mid = (l + r) / 2;
					for(int i = l; i<=r; i++){
						if(i <= mid)v[j][i] = ad[layer + 1];
						else v[j][i] = ad[layer + 1] + 1;
					}
					if(layer % 2 == 0){
						v[j][l] = -2;
						v[j][mid] = -1;
						v[j][mid + 1] = -2;
						v[j][r] = -1;
					}
					else{
						v[j][l] = -1;
						v[j][mid] = -2;
						v[j][mid + 1] = -1;
						v[j][r] = -2;
					}
					solve(l, mid, layer + 1, ad[layer + 1]);
					solve(mid + 1, r, layer + 1, ad[layer + 1] + 1);
				}
			}
		}
	}
	else if(divv[layer] == 2){
		for(int j = ad[layer]; j<=ad[layer] + 1; j++){
			if(j > dex){
				for(int i = l; i<=r; i++){
					if(layer % 2 == 0){
						v[j][i] = -2;
					}
					else v[j][i] = -1;
				}
			}
			else if(j < dex){
				for(int i = l; i<=r; i++){
					if(layer % 2 == 0){
						v[j][i] = -1;
					}
					else v[j][i] = -2;
				}
			}
			else{
				if(divv[layer + 1] == 1){
					for(int i = l; i<=r; i++){
						v[j][i] = ad[layer + 1];
					}
					if(layer % 2 == 0){
						v[j][l] = -2;
						v[j][r] = -1;
					}
					else{
						v[j][l] = -1;
						v[j][r] = -2;
					}
					solve(l + 1, r - 1, layer + 1, ad[layer + 1]);
				}
				else{
					int mid = (l + r) / 2;
					for(int i = l; i<=r; i++){
						if(i <= mid)v[j][i] = ad[layer + 1];
						else v[j][i] = ad[layer + 1] + 1;
					}
					if(layer % 2 == 0){
						v[j][l] = -2;
						v[j][mid] = -1;
						v[j][mid + 1] = -2;
						v[j][r] = -1;
					}
					else{
						v[j][l] = -1;
						v[j][mid] = -2;
						v[j][mid + 1] = -1;
						v[j][r] = -2;
					}
					solve(l, mid, layer + 1, ad[layer + 1]);
					solve(mid + 1, r, layer + 1, ad[layer + 1] + 1);
				}
			}
		}
	}
	else{
		if(l != r){
			if(layer % 2 == 0){
				v[dex][l] = -2;
				v[dex][r] = -1;
			}
			else{
				v[dex][l] = -1;
				v[dex][r] = -2;
			}
		}
	}
}
vi tern(int x){
	int cur = 1;
	vi ret;
	while(x > 0){
		ret.pb(x % (cur * 3) / cur);
		x -= (x % (cur * 3));
		cur *= 3;
	}
	while(ret.size() < 6)ret.pb(0);
	reverse(ret.begin(), ret.end());
	return ret;
}
std::vector<std::vector<int>> devise_strategy(int N) {
	if(N <= 729){
		vector<vi>v(19, vi(N+1));
		v[0][0] = 0;
		FOR(i, 1, N+1){
			vi cur = tern(i);
			v[0][i] = 1 + cur[0];
		}
		FOR(dig, 1, 7){
			if(dig % 2 == 1){
				v[dig * 3 - 2][0] = 1;
				v[dig * 3 - 1][0] = 1;
				v[dig * 3][0] = 1;
			}
			else{
				v[dig * 3 - 2][0] = 0;
				v[dig * 3 - 1][0] = 0;
				v[dig * 3][0] = 0;
			}
			FOR(i, 1, N+1){
				vi cur = tern(i);
				f0r(j, 3){
					if(cur[dig-1] < j){
						v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -2 : -1);
					}
					else if(cur[dig-1] > j){
						v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -1 : -2);
					}
					else{
						if(dig != 6)v[(dig - 1) * 3 + 1 + j][i] = dig * 3 + 1 + cur[dig];
						else v[(dig - 1) * 3 + 1 + j][i] = 1;
					}
				}
			}
		}
		/*
		f0r(i, 25){
			f0r(j, 11)cout<<v[i][j]<<' ';
			cout<<'\n';
		}
		*/
		return v;
	}
	else{
		f0r(i, 21)v[i].resize(N+1);
		f0r(i, 21)v[i][0] = chec[i];
		int a = N / 3;
		int b = N / 3 * 2;
		FOR(i, 1, N+1){
			if(i < a)v[0][i] = 1;
			else if(i < b)v[0][i] = 2;
			else v[0][i] = 3;	
		}
		v[0][1] = -1;
		v[0][N] = -2;
		
		solve(2, a-1, 0, 1);
		solve(a, b-1, 0, 2);
		solve(b, N-1, 0, 3);
		/*
		f0r(i, 21){
			f0r(j, N)cout<<v[i][j]<<' ';
			cout<<'\n';
		}
		*/
		f0r(i, 21){
			FOR(j, 1, N){
				if(v[i][j] == 0){
					if(v[(i + 2) / 3 * 3 - 3][j] == -2)v[i][j] = -1;
					else v[i][j] = -2;
				}
			}
		}
		return v;
	}
	
	
}

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