Submission #1077104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077104		allin27x	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	20 ms	860 KiB

prison

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


std::vector<std::vector<int>> devise_strategy(int N){
	vector ans(22, vector (N+1, 0));
	vector<vector<pair<int,int>>> rgs(22);
	rgs[0].push_back(make_pair(1,5000));
	vector<pair<int,int>> curr; curr.push_back(make_pair(1,5000));
	vector<pair<int,int>> nc;
	for (int i=0; i<7; i++) {
		for (auto [l,r]: curr) {
			l++; r--;
			rgs[3*i+1].push_back({l, (2*l+r)/3});
			nc.push_back({l, (2*l+r)/3});
		}
		for (auto [l,r]: curr) {
			l++; r--;
			rgs[3*i+2].push_back({(2*l+r)/3 + 1, (l+2*r)/3});
			nc.push_back({(2*l+r)/3 + 1, (l+2*r)/3});
		}
		for (auto [l,r]: curr) {
			l++; r--;
			rgs[3*i+3].push_back({(l+2*r)/3+1, r});
			nc.push_back({(l+2*r)/3+1, r});
		}
		curr = nc; nc.clear();
	}

	ans[0][0] = 0; ans[0][1] = -1; ans[0][N] = -2;
	for (int i=2; i<N; i++) {
		for (auto [l,r]: rgs[1]) {
			if (l<=i && i<=r) ans[0][i] = 1;
		}
		for (auto [l,r]: rgs[3]) {
			if (l<=i && i<=r) ans[0][i] = 3;
		}
		for (auto [l,r]: rgs[2]) {
			if (l<=i && i<=r) ans[0][i] = 2;
		}
	}
	for (int i=1; i<22; i++) {
		int pl = (i-1)/3 % 2;
		int bl = (i-1)/3; int first_pr = (i-1) % 3;
		ans[i][0] = !pl;
		int ll = rgs[bl*3 + 1][0].first; int rr = rgs[bl*3+3].back().second;
		for (int j=1; j<=N; j++) {
			int sec_pr = -1;
			for (auto [l,r]: rgs[bl*3 + 1]) {
				if (l<=j && j<=r) {
					sec_pr = 0;
				}
			}
			for (auto [l,r]: rgs[bl*3 + 2]) {
				if (l<=j && j<=r) {
					sec_pr = 1;
				}
			}
			for (auto [l,r]: rgs[bl*3 + 3]) {
				if (l<=j && j<=r) {
					sec_pr = 2;
				}
			}
			if (sec_pr == -1) {
				if (j <= ll) ans[i][j] = -1 -!pl;
				if (j >= rr) ans[i][j] = -1 - pl;
			} else {
				if (first_pr == sec_pr) {
					ans[i][j] = bl*3 + 4 + sec_pr;
					if (ans[i][j] >= 22) ans[i][j] = -1;
				}
				if (first_pr < sec_pr) ans[i][j] = -1 -pl;
				if (first_pr > sec_pr) ans[i][j] = -1 - !pl;
			}
		}
	}

	return ans;
}

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