Submission #735311

#	Time	Username	Problem	Language	Result	Execution time	Memory
735311		GusterGoose27	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	12 ms	1492 KiB

prison

#include "prison.h"

using namespace std;

typedef pair<int, int> pii;

#include <bits/stdc++.h>

class range {
public:
	int l, r;
	int par;
	int id;
	range(int l, int r, int p, int i) : l(l), r(r), par(p), id(i) {}
	range() {}
};

const int n = 5102;
const int x = 21;
int strat[21][n+1];
bool parity[21];
vector<int> ranges[22];
vector<range> range_list;

void make_strat() {
	range_list.push_back(range(1, n, -1, 0));
	ranges[0].push_back(0);
	for (int i = 0; i <= 15; i++) {
		int nxt_start = 3*((i+2)/3)+1;
		parity[nxt_start] = parity[nxt_start+1] = parity[nxt_start+2] = !parity[i];
		for (int v: ranges[i]) {
			range r = range_list[v];
			int sz = (r.r-r.l)/3;
			range_list.push_back(range(r.l+1, r.l+sz, v, nxt_start));
			range_list.push_back(range(r.l+sz+1, r.l+2*sz, v, nxt_start+1));
			range_list.push_back(range(r.l+2*sz+1, r.l+3*sz, v, nxt_start+2));
			ranges[nxt_start].push_back(range_list.size()-3);
			ranges[nxt_start+1].push_back(range_list.size()-2);
			ranges[nxt_start+2].push_back(range_list.size()-1);
		}
	}
	for (int i = 16; i <= 18; i++) {
		int nxt_start = 3*((i+2)/3)+1;
		for (int v: ranges[i]) {
			range r = range_list[v];
			range_list.push_back(range(r.l+1, r.r-1, v, nxt_start));
			ranges[nxt_start].push_back(range_list.size()-1);
		}
	}
	parity[19] = !parity[18];
	parity[20] = parity[18];
	for (int v: ranges[19]) {
		range r = range_list[v];
		range_list.push_back(range(r.l+1, r.r-1, v, 20));
		ranges[20].push_back(range_list.size()-1);
	}
	// for (int v: ranges[20]) {
	// 	range r = range_list[v];
	// 	cout << r.l << ' ' << r.r << '\n';
	// }
	strat[0][0] = 0;
	strat[0][1] = -1;
	strat[0][n] = -2;
	for (int i = 1; i < 21; i++) {
		fill(strat[i], strat[i]+n+1, 0);
		strat[i][0] = parity[i];
		for (int v: ranges[i]) {
			range r = range_list[v];
			for (int j = range_list[r.par].l; j <= r.l; j++)
				strat[i][j] = -1-parity[i];
			for (int j = r.r; j <= range_list[r.par].r; j++)
				strat[i][j] = -2+parity[i];
			for (int j = r.l; j <= r.r; j++) strat[range_list[r.par].id][j] = i;
		}
	}
}

vector<vector<int>> devise_strategy(int N) {
	make_strat();
	vector<vector<int>> res(21, vector<int>(N+1));
	for (int i = 0; i < 21; i++) {
		for (int j = 0; j <= N; j++) res[i][j] = strat[i][j];
	}
	return res;
}

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