Submission #1056384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056384		DorostWef	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	7 ms	2392 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;
vector <vector <int>> v;

int g (bool x, bool w) {
	if (!x) {
		return (w ? -2 : -1);
	}
	return (w ? -1 : -2);
}

void solve (int n, vector <int> a, vector <int> f, bool x) {
	if (n == 5000) {
		v.push_back({});
		v.back().push_back(0);
		int mid = (n - 1) / 2;
		vector <int> na, nf;
		for (int i = 0; i < (int)a.size(); i++) {
			if (a[i] <= 1) {
				v.back().push_back(-1);
				nf.push_back(0);
				na.push_back(-1);
			} else if (a[i] >= n) {
				v.back().push_back(-2);
				nf.push_back(1);
				na.push_back(5001);
			} else if (a[i] <= mid + 1) {
				v.back().push_back(1);
				nf.push_back(0);
				na.push_back(a[i] - 1);
			} else {
				v.back().push_back(2);
				nf.push_back(1);
				na.push_back((a[i] - 2) % mid + 1);
			}
		}
		solve (mid, na, nf, !x);
	} else if (n == 1) {
		v.push_back({});
		v.back().push_back(x);
		for (int i = 0; i < (int)a.size(); i++) {
			if (f[i] == 0) {
				v.back().push_back(g(x, 0));
			} else {
				v.back().push_back(g(x, 1));
			}
		}
		//cout << 'x' << endl;
	} else {
		vector <int> na, nf;
		int mid = (n - 1) / 2;
		for (int i = 0; i < (int)a.size(); i++) {
			if (a[i] <= 1) {
				nf.push_back(0);
				na.push_back(-1);
			} else if (a[i] >= n) {
				nf.push_back(1);
				na.push_back(5001);
			} else if (a[i] <= mid + 1) {
				nf.push_back(0);
				na.push_back(a[i] - 1);
			} else {
				nf.push_back(1);
				na.push_back((a[i] - 2) % mid + 1);
			}
		}
		for (int k = 0; k < 2; k++) {
			v.push_back({});
			v.back().push_back(x);
			for (int i = 0; i < (int)a.size(); i++) {
				int w = 2;
				if (n == 3)
					w = 1;
				if (((k == 1) && (f[i] == 0))) {
					v.back().push_back(g(x, 0));
				} else if (((k == 0) && (f[i] == 1))) {
					v.back().push_back(g(x, 1));
				} else if (a[i] <= 1) {
					v.back().push_back(g(x, 0));
				} else if (a[i] >= n) {
					v.back().push_back(g(x, 1));
				} else if (a[i] <= mid + 1) {
					v.back().push_back((int)v.size() + 1 - k);
				} else {
					v.back().push_back((int)v.size() + w - k);
				}
			}
		}
		solve (mid, na, nf, !x);
	}
}

std::vector<std::vector<int>> devise_strategy(int N) {
	vector <int> a, f;
	for (int i = 1; i <= 5000; i++) {
		a.push_back(i);
		f.push_back(0);
	}
	solve (5000, a, f, 0);
	vector <vector <int>> vv;
	for (int i = 0; i < (int)v.size(); i++) {
		vv.push_back({});
		for (int j = 0; j <= N; j++) {
			vv[i].push_back(v[i][j]);
		}
	}
	return vv;
}

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