Submission #632494

#	Time	Username	Problem	Language	Result	Execution time	Memory
632494		Red_Inside	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1364 KiB

prison

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

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=1e5+100,LOG=20,mod=998244353;
int block = 106, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
//#define int ll
const int inf=2e9;
#define y1 yy
#define prev pre
#define pii pair <int, int>

int n;

pii getlr(int i, int iter)
{
	int l = 1;
	int r = 5000;
	forn(1, it, iter)
	{
		l++;
		r--;
		int m1 = l + (r - l + 1) / 3;
		int m2 = m1 + (r - l + 1) / 3 + ((r - l + 1) % 3 == 2);
		if(l <= i && i < m1) r = m1-1;
		else if(m1 <= i && i < m2)
		{
			l = m1;
			r = m2 - 1;
		}
		else l = m2;
		
//		cout << l << " " << r << " " << r - l + 1 << endl;
	}
	return {l, r};
}

pii getm(pii i)
{
	int m1 = i.f + (i.s - i.f + 1) / 3;
	int m2 = m1 + (i.s - i.f + 1) / 3 + ((i.s - i.f + 1) % 3 == 2);
	return {m1, m2};
}

vector <vector <int> > devise_strategy(int N) 
{
	getlr(4789, 6);
	n = 5000;
	vector <vector <int> > ans;
	int x = 20;
	ans.assign(x + 1, {});
	forn(0, i, x)
	{
		ans[i].assign(n + 1, 0);
	}
	ans[0][0] = 0;
	ans[0][1] = -1;
	ans[0][n] = -2;
	forn(2, i, n - 1)
	{
		pii lr = getm({2, 4999});
		if(i < lr.f)
			ans[0][i] = 1;
		else if(lr.f <= i && i < lr.s)
			ans[0][i] = 2;
		else
			ans[0][i] = 3;
	}
	forn(1, i, x)
	{
		ans[i][0] = ((i - 1) / 3 + 1) % 2;
	}
	forn(1, i, 18)
	{
		forn(1, j, n)
		{
			pii lr = getlr(j, (i - 1) / 3);
//			if(i == 8 && j == 4788) cout << i << " " << lr.f << " " << lr.s << endl;
			lr.f++;
			lr.s--;
			pii m = getm(lr);
			int num1 = (i - 1) % 3 + 1;
			if(j <= lr.f) 
			{
				ans[i][j] = -((ans[i][0] + 1));
				continue;
			}
			if(j >= lr.s)
			{
				ans[i][j] = -((ans[i][0] ^ 1) + 1);
				continue;
			}
			int num2;
			if(j < m.f) num2 = 1;
			else if(m.f <= j && j < m.s) num2 = 2;
			else num2 = 3;
			if(num2 < num1) ans[i][j] = -((ans[i][0]) + 1);
			else if(num2 > num1) ans[i][j] = -((ans[i][0] ^ 1) + 1);
			else
			{
				pii otr = getlr(j, (i - 1) / 3 + 1);
				if(j == otr.f)
				{
					ans[i][j] = -((ans[i][0]) + 1);
					continue;
				}
				if(j == otr.s)
				{
					ans[i][j] = -((ans[i][0] ^ 1) + 1);
					continue;
				}
				otr.f++;
				otr.s--;
				if(i >= 16)
				{
					int mid = (otr.f + otr.s) / 2;
					if(j <= mid)
						ans[i][j] = 19;
					else
						ans[i][j] = 20;
					continue;
				}
//				if(i == 8 && j == 4788) cout << "dfakljsdfl " << otr.f << " " << otr.s << " " << otr.s-otr.f+1 << endl;
				m = getm(otr);
				if(j < m.f) ans[i][j] = ((i - 1) / 3 + 1) * 3 + 1;
				else if(m.f <= j && j < m.s) ans[i][j] = ((i-1)/3+1)*3+2;
				else ans[i][j] = ((i-1)/3+1)*3+3;
//				if(i == 8 && j == 4788) cout << "dfakljsdfl " <<((i-1)/3*3+1)*3+3 << " " << ans[i][j] << endl;
			}
		}
	}
	forn(1, j, n)
	{
		pii otr = getlr(j, 6);
		if(j <= otr.f)
		{
			ans[19][j] = -(ans[19][0] + 1);
			ans[20][j] = -(ans[20][0] + 1);
			continue;
		}
		if(j >= otr.s)
		{
			ans[19][j] = -((ans[19][0] ^ 1) + 1);
			ans[20][j] = -((ans[20][0] ^ 1) + 1);
			continue;
		}
		otr.f++;
		otr.s--;
		int mid = (otr.f + otr.s) / 2;
		if(j > mid) ans[19][j] = -((ans[19][0] ^ 1) + 1);
		else
		if(j == otr.f) ans[19][j] = -(ans[19][0] + 1);
		else ans[19][j] = -((ans[19][0] ^ 1) + 1);
		if(j <= mid) ans[20][j] = -(ans[20][0] + 1);
		else
		if(j == otr.s) ans[20][j] = -((ans[20][0] ^ 1) + 1);
		else ans[20][j] = -(ans[20][0] + 1);
	}
	vector <vector <int> > res;
	res.assign(x + 1, {});
	forn(0, i, x)
	{
		res[i].assign(N + 1, 0);
		forn(0, j, N)
		{
			res[i][j] = ans[i][j];
		}
	}
	return res;
}

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