Submission #626910

#	Time	Username	Problem	Language	Result	Execution time	Memory
626910		TheLostCookie	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	29 ms	1088 KiB

prison

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

typedef vector<int> vi;
typedef pair<int,int> ii;

#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
#define ROF(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(v) begin(v),end(v)
#define pb push_back

//offline dp results
//{5000, 1666, 832, 277, 92, 30, 14, 6, 2}
//{0, 3, 5, 8, 11, 14, 16, 18, 20}
std::vector<std::vector<int>> devise_strategy(int N) {
	vi layers{0, 3, 5, 8, 11, 14, 16, 18, 20};
	vi splitIntoTwo{1,2,3,12,13,14,15,16,17,18};
	vi splitIntoThree{0,4,5,6,7,8,9,10,11};
	vector<bool> checkLeft(21);
	vector<vector<ii>> intervals(21);
	vector<vector<ii>> parInterval(21); //interval of the previous step. indexed the same way as intervals;
	intervals[0].pb({1,5000});
	parInterval[0].pb({1,5000});
	checkLeft[0] = true;
	FOR(i,0,19) {
		for(auto [l,r]: intervals[i]) {
			int d = r-l;

			int t = *next(lower_bound(all(layers),i));

			if(binary_search(all(splitIntoTwo),i)) {
				int mid = l + d/2; 
				intervals[t-1].pb({l+1,mid});
				intervals[t].pb({mid+1,r-1});
				parInterval[t-1].pb({l,r});
				parInterval[t].pb({l,r});
				checkLeft[t-1] = checkLeft[t] = !checkLeft[i];
			}
			if(binary_search(all(splitIntoThree),i)) {
				int mid0 = l + (d+1)/3, mid1 = l + 2*((d+1)/3);
				intervals[t-2].pb({l+1,mid0});
				intervals[t-1].pb({mid0+1,mid1});
				intervals[t].pb({mid1+1,r-1});
				parInterval[t-2].pb({l,r});
				parInterval[t-1].pb({l,r});
				parInterval[t].pb({l,r});
				checkLeft[t-2] = checkLeft[t-1] = checkLeft[t] = !checkLeft[i];
			}
		}
	}

	vector<vi> strat(21,vi(N+1));
	FOR(i,0,21) {
		strat[i][0] = (checkLeft[i]?0:1);
		FOR(j,1,N+1) {
			int l = 0, r = N+1;
			FOR(k,0,int(intervals[i].size())) {
				if(parInterval[i][k].first <= j && j <= parInterval[i][k].second) {
					l = intervals[i][k].first;
					r = intervals[i][k].second;
					break;
				}
			}
			if(j <= l) strat[i][j] = (checkLeft[i]?-1:-2);
			else if(j >= r) strat[i][j] = (checkLeft[i]?-2:-1);
			else if(binary_search(all(splitIntoTwo),i)) {
				int t = *next(lower_bound(all(layers),i));
				FOR(k,0,2) for(auto [f,s]: intervals[t-k]) if(f <= j && j <= s) strat[i][j] = t-k;
			} else if(binary_search(all(splitIntoThree),i)) {
				int t = *next(lower_bound(all(layers),i));
				FOR(k,0,3) for(auto [f,s]: intervals[t-k]) if(f <= j && j <= s) strat[i][j] = t-k;
			} else {
				strat[i][j] = 0; //never used
			}
			assert(strat[i][j] >= -2 && strat[i][j] <= 20);
		}
	}
	return strat;
}

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