Submission #758723

#	Time	Username	Problem	Language	Result	Execution time	Memory
758723		amunduzbaev	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	9 ms	1100 KiB

prison

#include "prison.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll

vector<vector<ii>> devise_strategy(ii n) {
	vector<vector<ii>> a(1, vector<ii>(n + 1));
	vector<vector<ar<int, 4>>> rng(100);
	
	a[0][0] = 1;
	int l = 1, r = n;
	a[0][l] = -2, a[0][r] = -1;
	l++, r--;
	int third = (r - l + 3) / 3;
	rng[a.size()].push_back({l - 1, r + 1, l, l + third - 1});
	for(int i=l;i<l+third;i++){
		a[0][i] = a.size();
	}
	rng[a.size() + 1].push_back({l - 1, r + 1, l + third, l + 2 * third - 1});
	for(int i=l+third;i<l+2*third;i++){
		a[0][i] = a.size() + 1;
	}
	rng[a.size() + 2].push_back({l - 1, r + 1, l + 2 * third, r});
	for(int i=l+2*third;i<=r;i++){
		a[0][i] = a.size() + 2;
	}
	vector<int> b_(n + 1, 0);
	a.push_back(b_);
	a.push_back(b_);
	a.push_back(b_);
	
	for(int b=6;b>0;b--){
		for(int j=(int)a.size() - 3;j<(int)a.size();j++){
			a[j][0] = b & 1;
			for(auto [l, r, l_, r_] : rng[j]){
				for(int k=l;k<=l_;k++){
					if(a[j][0]){
						a[j][k] = -2;
					} else {
						a[j][k] = -1;
					}
				}
				for(int k=r_;k<=r;k++){
					if(a[j][0]){
						a[j][k] = -1;
					} else {
						a[j][k] = -2;
					}
				}
				
				l_++, r_--;
				int third = (r_ - l_ + 3) / 3;
				{
					int _l = l_, _r = min(r_, l_ + third - 1);
					if(_l <= _r){
						rng[a.size()].push_back({l_ - 1, r_ + 1, _l, _r});
						for(int k=_l;k<=_r;k++){
							a[j][k] = a.size();
						}
					}
				}
				{
					int _l = l_ + third, _r = min(r_, l_ + 2 * third - 1);
					if(_l <= _r){
						rng[a.size() + 1].push_back({l_ - 1, r_ + 1, _l, _r});
						for(int k=_l;k<=_r;k++){
							a[j][k] = a.size() + 1;
						}
					}
				}
				{
					int _l = l_ + 2 * third, _r = r_;
					if(_l <= _r){
						rng[a.size() + 2].push_back({l_ - 1, r_ + 1, _l, _r});
						for(int k=_l;k<=_r;k++){
							a[j][k] = a.size() + 2;
						}
					}
				}
			}
			
			//~ int prev = (j - 1) % 3;
			//~ a[j][0] = b&1;
			//~ for(int i=1;i<=n;i++){
				//~ int cur = get(i, b + 1);
				//~ if(cur < prev){
					//~ if(b&1) a[j][i] = -2;
					//~ else a[j][i] = -1;
				//~ }
				
				//~ if(prev < cur){
					//~ if(b&1) a[j][i] = -1;
					//~ else a[j][i] = -2;
				//~ }
				
				//~ if(prev == cur){
					//~ a[j][i] = a.size() + get(i, b);
				//~ }
			//~ }
		}
		
		a.push_back(b_);
		a.push_back(b_);
		a.push_back(b_);
	}
	
	for(int j=(int)a.size() - 3;j<(int)a.size();j++){
		a[j][0] = 0;
		for(auto [l, r, l_, r_] : rng[j]){
			for(int k=l;k<=l_;k++){
				a[j][k] = -1;
			}
			for(int k=r_;k<=r;k++){
				a[j][k] = -2;
			}
			
			l_++, r_--;
			assert(l_ > r_);
			//~ int third = (r_ - l_ + 3) / 3;
			//~ rng[a.size()].push_back({l_ - 1, r_ + 1, l_, l_ + third - 1});
			//~ for(int k=l_;k<l_ + third;k++){
				//~ a[j][k] = a.size();
			//~ }
			//~ rng[a.size() + 1].push_back({l_ - 1, r_ + 1, l_ + third, l_ + 2 * third - 1});
			//~ for(int k=l_+third;k<l_ + 2 * third;k++){
				//~ a[j][k] = a.size() + 1;
			//~ }
			//~ rng[a.size() + 2].push_back({l_ - 1, r_ + 1, l_ + 2 * third, r_});
			//~ for(int k=l_ + 2 * third;k<=r_;k++){
				//~ a[j][k] = a.size() + 2;
			//~ }
		}
		
		//~ int prev = (j - 1) % 3;
		//~ a[j][0] = 0;
		//~ for(int i=1;i<=n;i++){
			//~ int cur = get(i, 1);
			//~ if(cur < prev){
				//~ a[j][i] = -1;
			//~ } 
			//~ if(prev < cur){
				//~ a[j][i] = -2;
			//~ } 
			//~ if(prev == cur){
				//~ int nxt = get(i, 0);
				//~ if(nxt == 0){
					//~ a[j][i] = -1;
				//~ } if(nxt == 2){
					//~ a[j][i] = -2;
				//~ } if(nxt == 1){
					//~ a[j][i] = a.size();
				//~ }
			//~ }
		//~ }
	}
	
	//~ a.push_back(b_);
	//~ a.back()[0] = 1;
	//~ for(int i=1;i<=n;i++){
		//~ int cur = get(i, 0);
		//~ if(cur == 0){
			//~ a.back()[i] = -2;
		//~ } if(cur == 2){
			//~ a.back()[i] = -1;
		//~ }
		
	//~ }
	
	return a;
}

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