Submission #826760

#	Time	Username	Problem	Language	Result	Execution time	Memory
826760		arnold518	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	1584 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int P[]={0, 2, 3, 3, 3, 3, 2, 2, 2};
int Q[]={0, 2, 5, 8, 11, 14, 16, 18, 20};
int A[21][5023];
int B[10][5023];

void f(int pos, int l, int r)
{
	B[pos][l]=-1; B[pos][r]=-2;
	if(l+2>r) return;
	int p=(r-l-1)/P[pos];
	for(int i=l+1; i<r; i++)
	{
		B[pos][i]=(i-l-1)/p+Q[pos-1]+1;
	}
	for(int i=l+1; i<r; i+=p) f(pos+1, i, i+p-1);
}

vector<vector<int>> devise_strategy(int N)
{
	f(1, 1, 5022);
	A[0][0]=0;
	A[0][1]=-1; A[0][5022]=-2;
	for(int i=2; i<=5021; i++) A[0][i]=B[1][i];
	for(int i=1; i<=8; i++)
	{
		for(int j=Q[i-1]+1; j<=Q[i]; j++)
		{
			int t=A[j][0]=i%2;
			for(int k=1; k<=5022; k++)
			{
				if(B[i][k]==-1)
				{
					if(t) A[j][k]=-2;
					else A[j][k]=-1;
				}
				else if(B[i][k]==-2)
				{
					if(t) A[j][k]=-1;
					else A[j][k]=-2;
				}
				else if(B[i][k]<j)
				{
					if(t) A[j][k]=-2;
					else A[j][k]=-1;
				}
				else if(B[i][k]>j)
				{
					if(t) A[j][k]=-1;
					else A[j][k]=-2;
				}
				else
				{
					if(B[i+1][k]==-1)
					{
						if(t) A[j][k]=-2;
						else A[j][k]=-1;
					}
					else if(B[i+1][k]==-2)
					{
						if(t) A[j][k]=-1;
						else A[j][k]=-2;
					}
					else A[j][k]=B[i+1][k];
				}
			}
		}
	}

	vector<vector<int>> ans=vector<vector<int>>(21, vector<int>(N+1));
	for(int i=0; i<=20; i++) for(int j=0; j<=N; j++) ans[i][j]=A[i][j];
	return ans;
}

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