Submission #626807

#	Time	Username	Problem	Language	Result	Execution time	Memory
626807		coloboxx	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	12 ms	1108 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));

	int conv[2] = { -2, -1 };

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

	/*for (int i = 7; i >= 0; --i)
		cout << val(2187, i);
	cout << '\n';
	for (int i = 7; i >= 0; --i)
		cout << val(2181, i);
	cout << '\n';*/

	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;

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

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

	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: 55 / 90