제출 #1239799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239799		MuhammadSaram	죄수들의 도전 (IOI22_prison)	C++20	0 / 100	4 ms	580 KiB

prison

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

using namespace std;

const int M = 1e5 + 1;

int id=1;
int ch[M][3], l[M], r[M], x[M], deg[M], dep[M];

vector<vector<int>> devise_strategy(int n)
{
	l[0]=1,r[0]=n;
	queue<int> q;
	q.push(0);
	while (!q.empty())
	{
		int u=q.front();q.pop();
		int len=r[u]-l[u]-1, y = (x[u]+2)/3*3;
		if (len>=3)
		{
			int e=l[u]+len/3+(len%3>0)+1, e1=e+len/3+(len%3>1);
			ch[u][0]=id++, ch[u][1]=id++, ch[u][2]=id++;
			deg[u]=3;
			x[ch[u][0]]=y+1, x[ch[u][1]]=y+2, x[ch[u][2]]=y+3;
			l[ch[u][0]]=l[u]+1, r[ch[u][0]]=e-1;
			l[ch[u][1]]=e, r[ch[u][1]]=e1-1;
			l[ch[u][2]]=e1, r[ch[u][2]]=r[u];
			q.push(ch[u][0]);
			q.push(ch[u][1]);
			q.push(ch[u][2]);
		}
		else if(len>=1)
		{
			ch[u][0]=id++;
			l[ch[u][0]]=r[ch[u][0]]=l[u]+1;
			x[ch[u][0]]=y+1;
			deg[u]=1;
			if (len>=2)
			{
				ch[u][1]=id++,deg[u]++;
				l[ch[u][1]]=r[ch[u][1]]=l[u]+2;
				x[ch[u][1]]=y+2;
			}
		}
	}
	vector<vector<int>> ans(21, vector<int>(n+1));
	for (int i=0;i<=20;i++)
	{
		int y=(i+2)/3*3;
		ans[i][0]=y%2;
		for (int v=1;v<=n;v++)
		{
			if (!i)
			{
				if (v==1) ans[i][v]=-1;
				else if(v==n) ans[i][v]=-2;
				else
				{
					for (int c=0;c<deg[0];c++)
						if (l[ch[0][c]]<=v)
						{
							ans[i][v]=x[ch[0][c]];
							break;
						}
				}
				continue;
			}
			int cur=0;
			bool pos=1;
			for (int j=0;j<y/3-1;j++)
			{
				if (v<l[ch[cur][0]] or v>r[ch[cur][deg[cur]-1]])
				{
					pos=0;
					break;
				}
				for (int c=0;c<deg[cur];c++)
					if (l[ch[cur][c]]<=v && v<=r[ch[cur][c]])
					{
						cur=ch[cur][c];
						break;
					}
			}
			if (!pos) continue;
			for (int c=0;c<deg[cur];c++)
				if (x[ch[cur][c]]==i)
				{
					if (l[ch[cur][c]]>=v)
						ans[i][v]=-1-ans[i][0];
					else if(v>=r[ch[cur][c]])
						ans[i][v]=-2+ans[i][0];
					else
					{
						cur=ch[cur][c];
						for (int c=0;c<deg[cur];c++)
							if (l[ch[cur][c]]<=v)
							{
								ans[i][v]=x[ch[cur][c]];
								break;
							}
					}
				}
		}
	}
	return ans;
}

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