Submission #681716

#	Time	Username	Problem	Language	Result	Execution time	Memory
681716		MilosMilutinovic	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	12 ms	1184 KiB

prison

#include "prison.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int K = 39;
int seq[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
int sum[] = {0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39};
int p[40];
vector<vector<int>> ans;

int get_bit(int x, int k) {
	for (int i = 9; i > k; i--) x /= seq[i];
	return x % seq[k];
}

set<int> setik;

void build(int l, int r, int x) {
//	if (setik.find(x) != setik.end()) assert(false);
//	setik.insert(x);
	if (l > r) return;
//	printf("SEG %d %d  = %d\n", l, r, x);
	int his_bag = (p[x] % 2 == 1 ? 1 : 2);
	int my_bag = (his_bag ^ 1 ^ 2);
	ans[x][l] = -my_bag;
	ans[x][r] = -his_bag;
	vector<int> pp[seq[p[x]]];
	for (int i = l + 1; i < r; i++)
		pp[get_bit(i, p[x])].push_back(i);
	if (x == 0) {
		for (int k = 0; k < seq[p[x]]; k++) {
			if (pp[k].empty()) continue;
			int L = pp[k][0], R = L;
			for (int j : pp[k]) {
				L = min(L, j);
				R = max(R, j);
				ans[x][j] = k + 1;
			}
			build(l, r, k + 1);
		}
	} else {
		int L = 1e9, R = -1;
		for (int i = l + 1; i < r; i++) {
			int my_bit = get_bit(i, p[x] - 1);
			int his_bit = x - sum[p[x] - 1] - 1;
			if (my_bit != his_bit) {
				ans[x][i] = (my_bit < his_bit ? -my_bag : -his_bag);
			} else {
				L = min(L, i);
				R = max(R, i);
			}
		}
		for (int j = L; j <= R; j++)
			ans[x][j] = sum[p[x]] + get_bit(j, p[x]) + 1;
		for (int i = 0; i < seq[p[x]]; i++) {
			build(L, R, sum[p[x]] + i + 1);
		}
	}
}

vector<vector<int>> devise_strategy(int n) {
	ans.resize(K);
	for (int i = 0; i < K; i++)
		ans[i].resize(n + 1);
	for (int i = 1; i <= K; i++) {
		p[i] = p[i - 1];
		while(sum[p[i]] < i) p[i]++;
	}
	for (int i = 0; i < K; i++)
		ans[i][0] = (p[i] & 1);
	build(1, n, 0);
//	for (int i = 0; i < K; i++) {
//		for (int j = 0; j <= n; j++) {
//			printf("%d ", ans[i][j]);
//		}
//		printf("\n \n");
//	}
	return ans;
}

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