Submission #626785

#	Time	Username	Problem	Language	Result	Execution time	Memory
626785		coloboxx	Prisoner Challenge (IOI22_prison)	C++17	10 / 100	6 ms	596 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
#define show(x) cerr << (#x) << " = " << x << '\n'

using namespace std;

int val(int x, int bit) {
	if (bit < 0)
		return 0;

	while (bit--)
		x /= 3;
	return x % 3;
}

vector<vector<int>> devise_strategy(int N) {
	vector<vector<int>> s(25, vector<int>(N + 1));

	s[0][0] = 0;
	for (int j = 1; j <= N; ++j)
		s[0][j] = 8 * (val(j, 7) + 1);

	for (int i = 1; i <= 24; ++i) {
		int u = 0, pw = 0;
		while (i - (pw + 8) > 0)
			++u, pw += 8;

		int bit = i - pw - 1;
		s[i][0] = (bit + 1) & 1;

		//show(i), show(bit);

		for (int j = 1; j <= N; ++j) {
			int v = val(j, bit);
			if (u != v)
				s[i][j] = -2 + (u > v ? s[i][0] ^ 1 : s[i][0]);
			else {
				s[i][j] = val(j, bit - 1) * 8 + bit; 
			}
		}
	}

	/*for (auto it : s) {
		for (auto it2 : it)
			cout << it2 << ' ';
		cout << '\n';
	}*/

	return s;
}

//3
//1 2
//1 3
//2 1
//2 3
//3 1
//3 2
//-1

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