제출 #986520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986520		Pyqe	죄수들의 도전 (IOI22_prison)	C++17	100 / 100	9 ms	1388 KiB

prison

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

using namespace std;

const long long mm=9,dva[mm]={1,3,3,3,3,3,3,2,0};
long long peu[mm],od[5069],pc[mm][5069],z=0;

void dnc(long long cdh,long long lb,long long rb)
{
	long long i;
	
	for(i=cdh;i<mm;i++)
	{
		pc[i][lb]=-1;
		pc[i][rb]=-2;
	}
	lb++;
	rb--;
	if(lb<=rb)
	{
		long long j,md[dva[cdh]+1];
		
		for(i=0;i<=dva[cdh];i++)
		{
			md[i]=lb-1+(rb-lb+1)*i/dva[cdh];
		}
		for(i=0;i<dva[cdh];i++)
		{
			for(j=md[i]+1;j<=md[i+1];j++)
			{
				pc[cdh][j]=peu[cdh]+i;
			}
			dnc(cdh+1,md[i]+1,md[i+1]);
		}
	}
}

vector<vector<int>> devise_strategy(int n)
{
	long long i,j,k,w,e;
	vector<vector<int>> cvv;
	
	for(i=0;i<mm;i++)
	{
		peu[i]=z;
		for(j=0;j<dva[i];j++)
		{
			od[z]=i;
			z++;
		}
	}
	z--;
	dnc(1,1,n);
	for(i=0;i<=z;i++)
	{
		vector<int> cv;
		
		k=od[i];
		e=k%2;
		cv.push_back(e);
		for(j=1;j<=n;j++)
		{
			w=pc[k][j];
			if(w<0)
			{
				cv.push_back(w^e);
			}
			else if(w<i)
			{
				cv.push_back(-1^e);
			}
			else if(w>i)
			{
				cv.push_back(-2^e);
			}
			else
			{
				w=pc[k+1][j];
				if(w<0)
				{
					cv.push_back(w^e);
				}
				else
				{
					cv.push_back(w);
				}
			}
		}
		cvv.push_back(cv);
	}
	return cvv;
}

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