Submission #629628

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

prison

#include "prison.h"
#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 sortv(vv) sort(vv.begin(), vv.end())
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
 
using namespace std;
const int maxn=500+10,LOG=17, mod=1e9+7;
int block = 320, 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=1e9+10;
#define y1 yy
#define prev pre
#define pii pair <int, int>

int n;

pii getlr(int x, int iter)
{
	int l = 1;
	int r = n;
	forn(1, i, iter)
	{
		int m1 = l + (r - l + 1) / 3;
		int m2 = m1 + (r - l + 1) / 3 + ((r - l + 1) % 3 == 2);
		if(x < m1)
		{
			r = m1 - 1;
		}
		else if(x >= m1 && x < m2)
		{
			l = m1;
			r = m2 - 1;
		}
		else
		{
			l = m2;
		}
	}
	return {l, r};
}

vector<vector<int> > devise_strategy(int N) {
	vector <vector <int> > ans;
	n = N;
	int x = 22;
	ans.assign(x + 1, {});
	forn(0, i, x) ans[i].assign(n + 1, 0);
	ans[0][0] = 0;
	forn(1, j, n)
	{
		int m1 = 1 + n / 3;
		int m2 = m1 + n / 3 + (n % 3 == 2);
		if(j < m1)
			ans[0][j] = 1;
		else if(j >= m1 && j < m2)
			ans[0][j] = 2;
		else
			ans[0][j] = 3;
	}
	forn(1, i, x)
	{
		if((i - 1) / 3 % 2 == 0)
			ans[i][0] = 1;
		else
			ans[i][0] = 0;
	}
	forn(1, j, n)
	{
		pii otr = getlr(j, 7);
		if(otr.s - otr.f + 1 == 3)
		{
			if(j < otr.f)
				ans[x][j] = -(ans[x][j] + 1);
			else if(j == otr.s) ans[x][j] = -((ans[x][j] ^ 1) + 1);
		}
	}
	forn(1, i, x - 1)
	{
		forn(1, j, n)
		{
//			cout << i << " " << j << endl;
			pii otr = getlr(j, (i - 1) / 3);
			int part2 = (i - 1) % 3 + 1;
			int part1;
			int m1 = otr.f + (otr.s - otr.f + 1) / 3;
			int m2 = m1 + (otr.s - otr.f + 1) / 3 + ((otr.s - otr.f + 1) % 3 == 2);
			if(j < m1)
			{
				part1 = 1;
			}
			else if(m1 <= j && j < m2)
			{
				part1 = 2;
			}
			else
			{
				part1 = 3;
			}
			if(part1 < part2) ans[i][j] = -(ans[i][0] + 1);
			else if(part1 > part2) ans[i][j] = -((ans[i][0] ^ 1) + 1);
			else if(part1 == part2)
			{
				otr = getlr(j, (i - 1) / 3 + 1);
				if(otr.s - otr.f + 1 >= 3)
				{
					if(otr.s - otr.f + 1 == 3 && (i - 1) / 3 * 3 + 3 == 21)
					{
						if(otr.f == j)
						{
							ans[i][j] = -(ans[i][0] + 1);
							continue;
						}
						if(otr.s == j)
						{
							ans[i][j] = -((ans[i][0] ^ 1) + 1);
							continue;
						}
						ans[i][j] = x;
						continue;
					}
					m1 = otr.f + (otr.s - otr.f + 1) / 3;
					m2 = m1 + (otr.s - otr.f + 1) / 3 + ((otr.s - otr.f + 1) % 3 == 2);
					if(j < m1) ans[i][j] = (i - 1) / 3 * 3 + 3 + 1;
					else if(m1 <= j && j < m2) ans[i][j] = (i - 1) / 3 * 3 + 3 + 2;
					else ans[i][j] = (i - 1) / 3 * 3 + 3 + 3;
				}
				else
				{
					if(otr.f == j) 
					{
						ans[i][j] = -(ans[i][0] + 1);
						continue;
					}
					if(otr.s == j)
					{
						ans[i][j] = -((ans[i][0] ^ 1) + 1);
						continue;
					}
				}
			}
		}
	}
	return ans;
}

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