Submission #1062405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062405		pravcoder	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	8 ms	1508 KiB

prison

#include "prison.h"

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef pair<int, int> pi;

#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rept(i, a, b) for (int i = (a); i < (b); i++) 

std::vector<std::vector<int>> devise_strategy(int N) {
	if (N == 2) {
		v2i s;
		s.pb({ 0, -1, -2 });
		return s;
	}
	vi empty(N + 1);
	v2i s(23, empty);
	v2i base3;
	base3.pb({ 0 });
	base3[0].resize(8);
	vi n3;
	for (int i = 1; i <= N; i++) {
		// calculate all base 3 representations
		n3.clear();
		n3 = base3[i - 1];
		/*cout << i << ":";
		for (auto digit : n3) {
			cout << " " << digit;
		}
		cout << "\n";*/
		int j = 7;
		while (j >= 0) {
			if (n3[j] == 2) {
				n3[j] = 0;
				j--;

			}
			else {
				n3[j]++;
				j = -1;
			}
			
		}
		/*for (auto digit : n3) {
			cout << " " << digit;
		}
		cout << "\n";*/
		base3.pb(n3);
		//cout << base3.size();
	}
	//cout << "base 3 initialised\n";
	//adding the initial decision
	s[0][0] = 0;
	rept(i, 1, N + 1) {
		s[0][i] = base3[i][0] + 1;
	}
	rep(d, 7) {
		rep(x, 3) {
			int j = 3*d + x + 1;
			s[j][0] = (d+1) % 2;
			rept(i, 1, N+1) {
				if (base3[i][d] < x) s[j][i] = (d % 2) - 2;
				else if (base3[i][d] > x) s[j][i] = ((d + 1) % 2) - 2;
				else {
					if (d < 6) {
						s[j][i] = 3 * (d + 1) + base3[i][d + 1] + 1;
					}
					else {
						if (base3[i][d + 1] == 0) {
							s[j][i] = (d % 2) - 2;
						}
						else if (base3[i][d + 1] == 2) {
							s[j][i] = ((d + 1) % 2) - 2;
						}
						else {
							s[j][i] = 22;
						}
					}
				}
			}
		}
	}
	s[22][0] = 0;
	rept(i, 1, N+1) {
		if (base3[i][7] == 0) s[22][i] = -1;
		else s[22][i] = -2;
	}
	return s;
}

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