Submission #825306

#	Time	Username	Problem	Language	Result	Execution time	Memory
825306		esomer	Prisoner Challenge (IOI22_prison)	C++17	5 / 100	14 ms	20140 KiB

prison

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

using namespace std;

typedef long long ll;

int N;
vector<vector<int>> ans;
vector<int> dp, which;

void build(int ind, int l, int r) {
	int total = r - l + 1; total -= 2;
	if(total <= 0){
		// cout << "ind " << ind << " total " << total << " l " << l << " r " << r << endl;
		for(int i = 1; i <= N; i++){
			if(i < l){
				ans[ind][i] = -(ans[ind][0] + 1);
			}else if(i > r){
				ans[ind][i] = -((1 - ans[ind][0]) + 1);
			}else if(i == l){
				ans[ind][l] = -(ans[ind][0] + 1);
			}else if(i == r) {
				ans[ind][r] = -((1 - ans[ind][0]) + 1);
			}
		// cout << "ind "<< ind << " i " << i << " " << ans[ind][i] << endl;
		}
		return;
	}
	int x = which[total];
	vector<int> sizes(x, total / x);
	for(int i = 0; i < total % x; i++){
		sizes[i]++;
	}
	// cout << "ind " << ind << " x " << x << " total " << total << endl;
	int curr = 0;
	int cind = 0;
	for(int i = 1; i <= N; i++){
		if(i < l){
			ans[ind][i] = -(ans[ind][0] + 1);
		}else if(i > r){
			ans[ind][i] = -((1 - ans[ind][0]) + 1);
		}else if(i == l){
			ans[ind][l] = -(ans[ind][0] + 1);
		}else if(i == r) {
			ans[ind][r] = -((1 - ans[ind][0]) + 1);
		}else{
			curr++;
			ans[ind][i] = (int)ans.size();
			if(curr >= sizes[cind]){
				ans.push_back({}); ans[(int)ans.size() - 1].resize(N+1);
				ans[(int)ans.size() - 1][0] = 1 - ans[ind][0];
				build((int)ans.size() - 1, i - curr + 1, i);
				curr = 0; cind++;
			}
		}
		// cout << "ind "<< ind << " i " << i << " " << ans[ind][i] << endl;
	}
}

void calc_dp(){
	dp.assign(N+1, 1e9);
	which.assign(N+1, 1);
	for(int i = 0; i <= N; i++){
		int real = i - 2;
		if(real <= 0) dp[i] = 0;
		else{
			for(int x = 1; x <= 20; x++){
				int cll = real / x;
				if(real % x != 0) cll++;
				int needed = x + dp[cll]; 
				if(needed < dp[i]){
					which[i] = x;
					dp[i] = needed;
				}
			}
		}
	}
}

vector<vector<int>> devise_strategy(int n) {
	N = n;
	calc_dp();
	ans.push_back({}); ans[0].resize(N+1);
	ans[0][0] = 0;
	build(0, 1, N);
	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);
//   }
// }

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