Submission #1056309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056309		dozer	Prisoner Challenge (IOI22_prison)	C++17	51.50 / 100	9 ms	1372 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define ll long long
#define LL node * 2
#define RR node * 2 + 1
#define MAXN 300005

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;

int find_bit(int num, int base, int bit){
	for(int i = 0; i < bit; i++) num /= base;
	return num % base;
}


void fill(vector<vector<int>> &a, int base, int bit, int n){
	if (bit < 0) return;
	int curr = a.size();
	vector<int> tmp(n + 1);
	tmp[0] = 0;
	int subs = 0;
	if (bit == 0) subs = 1;
	for (int i = 1; i <= n; i++){
		int to = find_bit(i, base, bit);
		if (bit == 0 && to == 0) tmp[i] = -1;
		else if (bit == 0 && to == base - 1) tmp[i] = -2;
		else tmp[i] = curr + to + 1 - subs;
	}

	a.pb(tmp);
	int l = 0, r = base;
	if (bit == 0) l++, r--;
	for (int i = l; i < r; i++){
		vector<int> tmp(n + 1, 0);
		tmp[0] = 1;
		for (int j = 1; j <= n; j++){
			int to = find_bit(j, base, bit);
			if (to < i) tmp[j] = -2;
			else if (to > i) tmp[j] = -1;
			else if (bit > 0) tmp[j] = curr + base + 1;
			else tmp[j] = -1;
		}
		a.pb(tmp);
	}

	fill(a, base, bit - 1, n);
}


vector<vector<int>> devise_strategy(int N) {
	vector<vector<int>> a;
	int bit = 0, mul = 1, base = 3;
	while(mul * base <= N) bit++, mul *= base;
	fill(a, base, bit, N);
	return a;
}


/*

static constexpr int kNumPrisoners = 500;

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

int main() {
	fileio();
	int N;
	assert(1 == scanf("%d", &N));

	std::vector<std::vector<int>> strategy = devise_strategy(N);
	if (strategy.size() == 0) {
	invalid_strategy("s is an empty array");
	}
	int x = strategy.size() - 1;
	cout<<x<<endl;
	for (int i = 0; i <= x; ++i) {
	if (static_cast<int>(strategy[i].size()) != N + 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 <= N; ++j) {
	  if (strategy[i][j] < -2 || strategy[i][j] > x) {
	    invalid_strategy("s[i][j] contains incorrect value");
	  }
	}
	}

	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: 5 / 5
• Subtask 3: 41.5 / 90