Submission #1215935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215935		bangan	Prisoner Challenge (IOI22_prison)	C++20	72 / 100	8 ms	1096 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

const int X = 23;

void debug(vector<vector<int>> s) {
	int N = s[0].size() - 1;
	cout << "\t";
	for (int i=0; i<=N; i++) cout << i << "\t";
	cout << "\n";
	for (int i=0; i<=X; i++) {
		cout << i << "\t";
		for (int j=0; j<=N; j++) cout << s[i][j] << "\t";
		cout << "\n";
	}
}

int kth(int x, int k) {
	k = 9-k;
	while (k--) x/=2;
	return x%2;
}

int big(int x) {
	int rep = 10;
	while (rep--) x/=2;
	return x;
	// return x>>9;
}

std::vector<std::vector<int>> devise_strategy(int N) {
	// cout << big(5000) << endl;
	vector s(X+1, vector<int>(N+1));
	s[0][0] = 0;
	for (int i=19; i<=X; i++) s[i][0] = 1;
	for (int i=1; i<=18; i++) {
		int b = i-1;
		b = (b - b%2) / 2;
		s[i][0] = b%2;
	}
	for (int i=1; i<=N; i++) s[0][i] = 19 + big(i);
	for (int i=19; i<=X; i++) for (int j=1; j<=N; j++) {
		if (i-19 < big(j)) s[i][j] = -1;
		else if (i-19 == big(j)) s[i][j] = kth(j, 0) + 1;
		else if (i-19 > big(j)) s[i][j] = -2;
	}
	for (int i=1; i<=18; i++) for (int j=1; j<=N; j++) {
		int b = i-1;
		int r = b%2;
		b = (b-r) / 2;
		if (r < kth(j, b)) s[i][j] = -(1-s[i][0]+1);
		else if (r == kth(j, b)) s[i][j] = 2*(b+1) + kth(j, b+1) + 1;
		else if (r > kth(j, b)) s[i][j] = -(s[i][0]+1);
		if (b == 8 && r == kth(j, b)) {
			if (kth(j, b+1) == 0) s[i][j] = -(s[i][0]+1);
			else s[i][j] = -(1-s[i][0]+1);
		} 
	}
	return s;
}

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