Submission #666935

#	Time	Username	Problem	Language	Result	Execution time	Memory
666935		flappybird	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	15 ms	1236 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define MX 5000
#define MAX 5000

vector<int> tree[MAX];
int cnt = 1;
int dep[MAX];
vector<int> cnum = { 3, 3, 3, 3, 3, 3, 2 };
int dv[MAX] = { 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7 };
int pl[MAX] = { 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1 };
int ind[MAX] = { 0, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1 };
int vloc[MAX];
pii range[MAX];

int make_tree(int l, int r, int x = 1, int d = 0) {
	dep[x] = d;
	range[x] = { l, r };
	if (r - l <= 1) return x;
	int intv = (r - l - 1 + cnum[d] - 1) / cnum[d];
	for (int i = 0; i < cnum[d]; i++) {
		tree[x].push_back(make_tree(l + i * intv + 1, l + i * intv + intv, ++cnt, d + 1));
		vloc[tree[x].back()] = i;
	}
	return x;
}

bool chk(pii p, int x) {
	return p.first <= x && x <= p.second;
}

int find_vertex(int x, int d, int loc = 1) {
	if (d == dep[loc]) return loc;
	if (x == range[loc].first) return -1;
	if (x == range[loc].second) return -2;
	for (auto v : tree[loc]) if (chk(range[v], x)) return find_vertex(x, d, v);
}

int calc(int b, int x) {
	if (!b) {
		int d = b / 3 + 1;
		int v = find_vertex(x, 1);
		if (v == -1) return -(pl[b] + 1);
		if (v == -2) return -(2 - pl[b]);
		return vloc[v] + 1;
	}
	else if (b >= 19) {
		int d = b / 3 + 1;
		int v = find_vertex(x, d);
		if (v == -1) return -(pl[b] + 1);
		if (v == -2) return -(2 - pl[b]);
		if (vloc[v] == b - 19) {
			if (range[v].first == x) return -(pl[b] + 1);
			else return -(2 - pl[b]);
		}
		else {
			if (vloc[v] < b - 19) return -(pl[b] + 1);
			else return -(2 - pl[b]);
		}
	}
	else {
		int d = (b - 1) / 3 + 1;
		int rloc = ind[b];
		int v = find_vertex(x, d);
		if (v == -1) return -(pl[b] + 1);
		if (v == -2) return -(2 - pl[b]);
		if (vloc[v] == rloc) {
			int nv = find_vertex(x, d + 1);
			if (nv == -1) return -(pl[b] + 1);
			if (nv == -2) return -(2 - pl[b]);
			return d * 3 + 1 + vloc[nv];
		}
		else {
			if (vloc[v] < rloc) return -(pl[b] + 1);
			else return -(2 - pl[b]);
		}
	}
}

std::vector<std::vector<int>> devise_strategy(int N) {
	make_tree(1, MX);
	vector<vector<int>> ans(21, vector<int>(N + 1));
	int i, j;
	for (i = 0; i <= 20; i++) ans[i][0] = pl[i];
	for (i = 0; i <= 20; i++) for (j = 1; j <= N; j++) ans[i][j] = calc(i, j);
	return ans;
}

Compilation message (stderr)

prison.cpp: In function 'int calc(int, int)':
prison.cpp:43:7: warning: unused variable 'd' [-Wunused-variable]
   43 |   int d = b / 3 + 1;
      |       ^
prison.cpp: In function 'int find_vertex(int, int, int)':
prison.cpp:39:1: warning: control reaches end of non-void function [-Wreturn-type]
   39 | }
      | ^

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