oj.uz

Submission #735311

# Submission time Handle Problem Language Result Execution time Memory
735311 2023-05-04T00:43:18 Z GusterGoose27 Prisoner Challenge (IOI22_prison) C++17
100 / 100
 12 ms 1492 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 820 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 852 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 2 ms 820 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 2 ms 820 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 852 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 5 ms 1076 KB Output is correct
5 Correct 10 ms 1364 KB Output is correct
6 Correct 11 ms 1476 KB Output is correct
7 Correct 11 ms 1492 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 5 ms 980 KB Output is correct
12 Correct 12 ms 1364 KB Output is correct