Submission #1022070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022070		pawned	Prisoner Challenge (IOI22_prison)	C++17	10 / 100	16 ms	1628 KiB

prison

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "prison.h"

int CT = 12;	// CHANGE TO 13 AFTER

vector<vi> devise_strategy(int N) {
	int MAX = N;
	// crop ans from MAX + 1 at the end
	vi sz;	// size is 13
	int curr = MAX;
	while (curr > 1) {
		curr = (curr + 1) / 2;
		sz.pb(curr);
	}
	vector<vi> ans;

	for (int i = 0; i < CT; i++) {
		vector<vi> vec(3, vi(MAX + 1, 0));
		vi cuts;
		for (int j = 0; j <= (1 << (i + 1)); j++) {
			cuts.pb(MAX * j / (1 << (i + 1)));
		}
/*		cout<<"cuts: ";
		for (int x : cuts)
			cout<<x<<" ";
		cout<<endl;*/
		int S = cuts.size();	// pow of 2 plus 1
		// number 3 * i
		vec[0][0] = 0;
		for (int j = 0; j < S - 1; j += 2) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[0][k] = 3 * i + 1;
			}
		}
		for (int j = 1; j < S - 1; j += 2) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[0][k] = 3 * i + 2;
			}
		}
		// number 3 * i + 1
		vec[1][0] = 1;
		for (int j = 0; j < S - 1; j += 2) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[1][k] = 3 * i + 3;
			}
		}
		for (int j = 1; j < S - 1; j += 2) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[1][k] = -1;
			}
		}
		// number 3 * i + 2
		vec[2][0] = 1;
		for (int j = 0; j < S - 1; j += 2) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[2][k] = -2;
			}
		}
		for (int j = 1; j < S - 1; j += 2) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[2][k] = 3 * i + 3;
			}
		}
		for (vi v : vec)
			ans.pb(v);
	}
	for (int i = 3 * CT - 3; i < 3 * CT; i++) {
		for (int j = 0; j <= MAX; j++) {
			if (ans[i][j] == 3 * CT)
				ans[i][j] = -1;
		}
	}
/*	cout<<"ANSWER: "<<endl;
	for (vi v : ans) {
		for (int x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	return ans;
}

// can make same for N = 5000, just truncate

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