Submission #1022091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022091		pawned	Prisoner Challenge (IOI22_prison)	C++17	48.50 / 100	11 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 = 8;	// 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;
	int base = 1;
	for (int i = 0; i < CT; i++) {
		vector<vi> vec(4, vi(MAX + 1, 0));
		base *= 3;
		vi cuts;
		for (int j = 0; j <= base; j++) {
			cuts.pb(MAX * j / base);
		}
/*		cout<<"cuts: ";
		for (int x : cuts)
			cout<<x<<" ";
		cout<<endl;*/
		int S = cuts.size();	// pow of 3 plus 1
		// number 3 * i
		vec[0][0] = 0;
		for (int j = 0; j < S - 1; j += 3) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[0][k] = 4 * i + 1;
			}
		}
		for (int j = 1; j < S - 1; j += 3) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[0][k] = 4 * i + 2;
			}
		}
		for (int j = 2; j < S - 1; j += 3) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[0][k] = 4 * i + 3;
			}
		}
		// number 3 * i + 1
		vec[1][0] = 1;
		for (int j = 0; j < S - 1; j += 3) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[1][k] = 4 * i + 4;
			}
		}
		for (int j = 1; j < S - 1; j += 3) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[1][k] = -1;
			}
		}
		for (int j = 2; j < S - 1; j += 3) {
			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 += 3) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[2][k] = -2;
			}
		}
		for (int j = 1; j < S - 1; j += 3) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[2][k] = 4 * i + 4;
			}
		}
		for (int j = 2; j < S - 1; j += 3) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[2][k] = -1;
			}
		}
		// number 3 * i + 3
		vec[3][0] = 1;
		for (int j = 0; j < S - 1; j += 3) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[3][k] = -2;
			}
		}
		for (int j = 1; j < S - 1; j += 3) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[3][k] = -2;
			}
		}
		for (int j = 2; j < S - 1; j += 3) {
			for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
				vec[3][k] = 4 * i + 4;
			}
		}
		for (vi v : vec)
			ans.pb(v);
	}
	for (int i = 4 * CT - 4; i < 4 * CT; i++) {
		for (int j = 0; j <= MAX; j++) {
			if (ans[i][j] == 4 * CT)
				ans[i][j] = -1;
		}
	}
/*	cout<<"ANSWER: "<<endl;
	for (vi v : ans) {
		for (int x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	return ans;
}

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