Submission #824532

#	Time	Username	Problem	Language	Result	Execution time	Memory
824532		esomer	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	42 ms	1808 KiB

prison

#include <bits/stdc++.h>
#include "prison.h"

using namespace std;

typedef long long ll;

vector<vector<int>> ans(22);
vector<vector<int>> inds(8);
vector<vector<int>> decc;

int val(int n, int exp){
	return decc[n][exp];
}

void precalc(int n){
	vector<ll> pw(9);
	pw[0] = 1;
	int org = n;
	for(int i = 1; i <= 8; i++) pw[i] = pw[i-1] * 3;
	for(int i = 8; i >= 0; i--){
		int which;
		if(n >= pw[i] * 2) {n -= pw[i] * 2; which = 2;}
		else if(n >= pw[i]) {n -= pw[i]; which = 1;}
		else{
			which = 0;
		}
		decc[org][i] = which;
	}
}

int N;

void build(int ind, int exp, int should){
	if(exp == 0){
		for(int i = 1; i <= N; i++){
			int which = val(i, exp);
			if(i % 9 == 7){
				ans[ind][i] = -((1 - ans[ind][0]) + 1);
			}else if(i % 3 == 0){
				ans[ind][i] = -((1 - ans[ind][0]) + 1);
			}else{
				ans[ind][i] = -(ans[ind][0] + 1);
			}
		}
		return;
	}
	if(exp == 1){
		//Optimize 2 queries.
		for(int i : inds[exp - 1]){
			ans[i][0] = 1 - ans[ind][0];
		}
		for(int i = 1; i <= N; i++){
			int which = val(i, exp);
			if(inds[exp][0] == ind){
				if(i % 9 <= 3){
					ans[ind][i] = -(ans[ind][0] + 1);
				}else if(i % 9 == 8 || i % 9 == 7){
					ans[ind][i] = -((1 - ans[ind][0]) + 1);
				}else if(i % 9 == 4){
					ans[ind][i] = -(ans[ind][0] + 1);
				}else{
					ans[ind][i] = inds[exp-1][0];
				}
			}else{
				if(i % 9 > 3){
					ans[ind][i] = -((1 - ans[ind][0]) + 1);
				}else if(i % 9 == 0 || i % 9 == 1){
					ans[ind][i] = -(ans[ind][0] + 1);
				}else if(i % 9 == 3){
					ans[ind][i] = -((1 - ans[ind][0]) + 1);
				}else{
					ans[ind][i] = inds[exp-1][0];
				}
			}
		}
		build(inds[exp - 1][0], exp - 1, 1);
		return;
	}
	if(exp == 2){
		for(int i : inds[exp - 1]){
			ans[i][0] = 1 - ans[ind][0];
		}
		for(int i = 1; i <= N; i++){
			int which = val(i, exp);
			if(which != should){
				if(which < should) ans[ind][i] = -(ans[ind][0] + 1);
				else ans[ind][i] = -((1 - ans[ind][0]) + 1);
			}else{
				which = val(i, exp - 1);
				if(i % 9 == 0){
					ans[ind][i] = -(ans[ind][0] + 1);
				}else if(i % 9 == 8){
					ans[ind][i] = -((1 - ans[ind][0]) + 1);
				}else{
					if(i % 9 > 3) ans[ind][i] = inds[exp-1][0];
					else ans[ind][i] = inds[exp-1][1];
				}
			}
		}
		build(inds[exp-1][0], exp - 1, 0);
		build(inds[exp-1][1], exp - 1, 0);
		return;
	}
	for(int i : inds[exp - 1]){
		ans[i][0] = 1 - ans[ind][0];
	}
	for(int i = 1; i <= N; i++){
		int which = val(i, exp);
		if(which != should){
			if(which < should) ans[ind][i] = -(ans[ind][0] + 1);
			else ans[ind][i] = -((1 - ans[ind][0]) + 1);
		}else{
			which = val(i, exp - 1);
			ans[ind][i] = inds[exp-1][which];
		}
	}
	build(inds[exp - 1][0], exp - 1, 0);
	build(inds[exp - 1][1], exp - 1, 1);
	build(inds[exp - 1][2], exp - 1, 2);
}

vector<vector<int>> devise_strategy(int n) {
	N = n;
	for(int i = 0; i < 22; i++) ans[i].resize(N+1);
	decc.assign(N+1, vector<int>(9, 0));
	for(int i = 1; i <= N; i++){
		precalc(i);
	}
	ans[0][0] = 0;
	int curr = 1;
	for(int i = 7; i >= 2; i--){
		inds[i].push_back(curr); curr++;
		inds[i].push_back(curr); curr++;
		inds[i].push_back(curr); curr++;
	}
	inds[1].push_back(curr); curr++;
	inds[1].push_back(curr); curr++;
	inds[0].push_back(curr);
	build(0, 8, 0);
	return ans;
}

// static constexpr int kNumPrisoners = 500;

// static void invalid_strategy(std::string message) {
//   printf("%s\n", message.c_str());
//   exit(0);
// }

// int main() {
//   int N2;
//   assert(1 == scanf("%d", &N2));
//   // printf("here\n"); return 0;
//   std::vector<std::vector<int>> strategy = devise_strategy(N2);
//   // printf("here\n"); return 0;
//   if (strategy.size() == 0) {
//     invalid_strategy("s is an empty array");
//   }
//   int x = strategy.size() - 1;
//   for (int i = 0; i <= x; ++i) {
//     if (static_cast<int>(strategy[i].size()) != N2 + 1) {
//       invalid_strategy("s[i] contains incorrect length");
//     }
//     if (strategy[i][0] < 0 || strategy[i][0] > 1) {
//       invalid_strategy("First element of s[i] is non-binary"); 
//     }
//     for (int j = 1; j <= N2; ++j) {
//       if (strategy[i][j] < -2 || strategy[i][j] > x) {
//         invalid_strategy("s[i][j] contains incorrect value");
//       }
//     }
//   }
//   // printf("here\n"); return 0;

//   FILE *log_file = fopen("log.txt","w");

//   int A, B;
//   while (1 == scanf("%d", &A) && A != -1) {
//     assert(1 == scanf("%d", &B));
//     bool answer = false;
//     int whiteboard = 0;
//     for (int i = 0; i < kNumPrisoners && !answer; ++i) {
//       int check = strategy[whiteboard][0];
//       whiteboard = strategy[whiteboard][check == 0 ? A : B];
//       if (whiteboard < 0) {
//         answer = true;
//         printf("%c\n", "BA"[whiteboard + 2]);
//       } else {
//         if (i > 0) {
//           fprintf(log_file, " ");
//         }
//         fprintf(log_file, "%d", whiteboard);
//       }
//     }
//     if (!answer) {
//       printf("X\n");
//     }
//     fprintf(log_file, "\n");
//     fflush(log_file);
//   }
// }

Compilation message (stderr)

prison.cpp: In function 'void build(int, int, int)':
prison.cpp:37:8: warning: unused variable 'which' [-Wunused-variable]
   37 |    int which = val(i, exp);
      |        ^~~~~
prison.cpp:54:8: warning: unused variable 'which' [-Wunused-variable]
   54 |    int which = val(i, exp);
      |        ^~~~~

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