Submission #758747

#	Time	Username	Problem	Language	Result	Execution time	Memory
758747		amunduzbaev	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	8 ms	1108 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;
				if(b == 1) third = 2;
				{
					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;
						}
					}
				}
			}
			
		}
		
		a.push_back(b_);
		a.push_back(b_);
		a.push_back(b_);
	}
	//~ cout<<rng[a.size() - 1][0][0]<<" ";
	//~ cout<<rng[a.size() - 1][0][1]<<" ";
	//~ cout<<rng[a.size() - 1][0][2]<<" ";
	//~ cout<<rng[a.size() - 1][0][3]<<endl;
	assert(rng[a.size() - 1].empty());
	a.pop_back();
	for(int j=(int)a.size() - 2;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_);
		}
	}
	
	return a;
}

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