Submission #799212

#	Time	Username	Problem	Language	Result	Execution time	Memory
799212		MadokaMagicaFan	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1004 KiB

prison

#include "bits/stdc++.h"
#include "prison.h"

using namespace std;
using ll = long long;
#define sz(v)	((int)v.size())
#define pb	push_back

vector<array<int, 6>> nd;

int dfs(int x) {
	int s = nd[x][1] - nd[x][0] + 1;

	nd[x][5] = 0;
	if (s <= 2) return 0;

	s -= 2;

	int e = s / 3;
	int e1, e2, e3;
	if (!e) {
		nd[x][2] = sz(nd);
		nd.pb({nd[x][0]+1, nd[x][1] - 1, 0, 0, 0});
		nd[x][5] = 1;
		return 1;
	}

	if (s < 5) {
		nd[x][2] = sz(nd);
		nd[x][3] = sz(nd)+1;
		nd[x][5] = 2;
		nd.pb({nd[x][0]+1, nd[x][0]+2, 0, 0, 0, 0});
		nd.pb({nd[x][0]+3, nd[x][1]-1, 0, 0, 0, 0});
		return 2;
	}

	e1 = e2 = e3 = e;
	if (s % 3) ++e1;
	if (s % 3 == 2) ++e2;

	nd[x][2] = sz(nd);
	nd[x][3] = sz(nd)+1;
	nd[x][4] = sz(nd)+2;

	int v1, v2, v3;
	nd.pb({nd[x][0]+1, nd[x][0]+e1, 0, 0, 0});
	nd.pb({nd[x][0]+1+e1, nd[x][0]+e1+e2, 0, 0, 0});
	nd.pb({nd[x][0]+1+e1+e2, nd[x][0]+e1+e3, 0, 0, 0});

	v1 = dfs(nd[x][2]);
	v2 = dfs(nd[x][3]);
	v3 = dfs(nd[x][4]);
	nd[x][5] = 3;

	return 3 + max({v1, v2, v3});

}

int dfs1(int x, int v, int d) {
	if (d <= nd[x][5]) return x;
	d -= nd[x][5];
	assert(v != nd[x][0]);
	assert(v != nd[x][1]);

	if (nd[nd[x][2]][1] >= v) return dfs1(nd[x][2], v, d);
	if (nd[nd[x][3]][1] >= v) return dfs1(nd[x][3], v, d);
	if (nd[nd[x][4]][1] >= v) return dfs1(nd[x][4], v, d);

	assert(0);
}

int s[] = {1700, 566, 188, 62, 20, 6, 2};

int query(int x, int y) {
	/* Get if it's either A or B */
	int u = 0; int z = x;

	int l = 1, cb = 0;
	while (z) {
		u = 1-u;
		if (z < 4)
			break;
		z -= 3;
	}

	if (y == 0) {
		return u;
	}

	z = x;
	if (z == 0) {
		if (y == 1)
			return -1;

		if (y < 2 + s[cb])
			return 1;
		if (y < 2 + 2*s[cb])
			return 2;
		return 3;
	}


	while (z) {
		if (y == l)
			return - 1 - u;
		if (y == l + 1 + 3 * s[cb])
			return u - 2;

		if (cb == 6 && y == l + 1 + 2 * s[cb])
			return u - 2;

		if (z < 4)
			break;
		z -= 3;

		++l;
		while (y >= l + s[cb])
			l += s[cb];
		++cb;
	}

	// if (l == 6 && x == 16) cout << cb << ' ' << u << ' ' << x << ' ' << y << ' ' << z <<endl;

	if (y < l + 1 + (z-1) * s[cb])
		return -1-u;
	if (y >= l + 1 + z * s[cb])
		return u-2;

	++l;
	while (y >= l + s[cb])
		l += s[cb];
	++cb;

	// if (l == 7) cout << cb << ' ' << u << ' ' << x << ' ' << y <<endl;

	if (cb == 7)
		if (y == l)
			return -1-u;
		else
			return u-2;

	if (cb == 6) {
		if (y == l)
			return -1-u;
		else if (y == l + 5)
			return u-2;

		if (y < l + 3) return 19;
		else return 20;
	}

	if (y == l)
		return - 1 - u;
	if (y == l + 1 + 3 * s[cb])
		return u - 2;


	if (y < l + s[cb] + 1) return cb*3 + 1;
	if (y < l + 2*s[cb] + 1) return cb*3 + 2;
	return cb * 3 + 3;
}

vector<vector<int>> devise_strategy(int n) {
	int x = 20;
	// nd.pb({1, 5102, 0, 0, 0});
	// dfs(0);
	vector<vector<int>> ans(x+1);
	for (int i = 0; i <= x; ++i) {
		ans[i].assign(n+1, 0);
		for (int j = 0; j <= n; ++j) {
			ans[i][j] = query(i, j);
		}
	}

	return ans;
}

#ifdef ONPC
/*
int main()
{
	int n;
	cin >> n;

	vector<vector<int>> a = devise_strategy(n);

	for (auto x : a) {
		for (auto u : x) {
			cout << u << ' ';
		}
		cout << endl;
	}
}
*/
#endif

Compilation message (stderr)

prison.cpp: In function 'int query(int, int)':
prison.cpp:136:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  136 |  if (cb == 7)
      |     ^

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