제출 #629656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
629656		Red_Inside	죄수들의 도전 (IOI22_prison)	C++17	10 / 100	15 ms	912 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 = 3;
	int r = n - 2;
	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) {
	//19 20 21
	vector <vector <int> > ans;
	n = N;
	int x = 20;
	ans.assign(x + 1, {});
	forn(0, i, x) ans[i].assign(n + 1, 0);
	ans[0][0] = 0;
	forn(1, j, n)
	{
		if(j == 1) 
		{
			ans[0][j] = -(ans[0][j] + 1);
			continue;
		}
		if(j == n) 
		{
			ans[0][j] = -((ans[0][j] ^ 1) + 1);
			continue;
		}
		int m1 = 3 + (n - 4) / 3;
		int m2 = m1 + (n - 4) / 3 + ((n - 4) % 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, 18)
	{
		if((i - 1) / 3 % 2 == 0)
			ans[i][0] = 1;
		else
			ans[i][0] = 0;
	}
	forn(1, i, 18)
	{
		forn(1, j, n)
		{
			if(j == 1)
			{
				ans[i][j] = -(ans[i][0] + 1);
				continue;
			}
			if(j == n)
			{
				ans[i][j] = -((ans[i][0] ^ 1) + 1);
				continue;
			}
			if(i >= 4 && j == 2)
			{
				ans[i][j] = -(ans[i][0] + 1);
				continue;
			}
			if(i >= 4 && j == n - 1)
			{
				ans[i][j] = -((ans[i][0] ^ 1) + 1);
				continue;
			}
//			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 >= 8 || (i - 1) / 3 * 3 + 3 <= 15)
				{
///					if(i == 17) cout << otr.f << " " << otr.s << "\n";
					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] = min(x, (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;
					}
					if(otr.s - otr.f + 1 >= 4)
					{
						//11 12 13 14 15 16 17
						if(j <= (otr.f + otr.s) / 2)
						{
							ans[i][j] = 19;
						}
						else
						{
							ans[i][j] = 20;
						}
					}
					else
					{
						if(otr.s - otr.f + 1 == 3)
						{
							ans[i][j] = 19;
						}
					}
				}
			}
		}
	}
	ans[19][0] = (ans[18][0] ^ 1);
	ans[20][0] = ans[19][0];
	forn(1, j, n)
	{
		pii otr = getlr(j, 6);
		if(otr.s - otr.f + 1 >= 4)
		{
			int l = otr.f + 1;
			int r = (otr.f + otr.s) / 2;
			if(j <= l) ans[19][j] = -(ans[19][0] + 1);
			if(j >= r) ans[19][j] = -((ans[19][0] ^ 1) + 1);
			l = (otr.f + otr.s) / 2 + 1;
			r = otr.s - 1;
			if(j <= l) ans[20][j] = -(ans[20][0] + 1);
			if(j >= r) ans[20][j] = -((ans[20][0] ^ 1) + 1);
		}
		else
		{
			if(j == otr.f)
				ans[19][j] = -(ans[19][0] + 1);
			if(j == otr.s)
				ans[19][j] = -((ans[19][0] ^ 1) + 1);
		}
	}
	return ans;
}
 

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