Submission #429325

#	Time	Username	Problem	Language	Result	Execution time	Memory
429325		Pyqe	Monster Game (JOI21_monster)	C++17	100 / 100	153 ms	444 KiB

monster

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

using namespace std;

const long long d=11;
long long pst[1069],tmp[1069],sq[1069],zs=0;

void rk(long long lh,long long rh)
{
	if(lh==rh)
	{
		pst[lh]=lh;
	}
	else
	{
		long long i,md=(lh+rh)/2,p[2];
		
		rk(lh,md);
		rk(md+1,rh);
		p[0]=lh;
		p[1]=md+1;
		for(i=lh;i<=rh;i++)
		{
			if(p[1]>rh||(p[0]<=md&&Query(pst[p[1]],pst[p[0]])))
			{
				tmp[i]=pst[p[0]];
				p[0]++;
			}
			else
			{
				tmp[i]=pst[p[1]];
				p[1]++;
			}
		}
		for(i=lh;i<=rh;i++)
		{
			pst[i]=tmp[i];
		}
	}
}

vector<int> Solve(int n)
{
	long long i,j,c=0,l=1,p;
	vector<int> v;
	
	rk(0,n-1);
	for(i=2;i<=min(min(d*2-1,l+d),(long long)n-1);i++)
	{
		if(Query(pst[0],pst[i]))
		{
			c++;
			l=i;
		}
	}
	if(c>1)
	{
		p=c;
	}
	else
	{
		if(l>2)
		{
			if(Query(pst[1],pst[3]))
			{
				p=0;
			}
			else
			{
				p=1;
			}
		}
		else
		{
			for(i=l+1;i<=min(l+d,(long long)n-1);i++)
			{
				if(Query(pst[l],pst[i]))
				{
					break;
				}
			}
			if(i>min(l+d,(long long)n-1))
			{
				p=0;
			}
			else
			{
				p=1;
			}
		}
	}
	l=-1;
	for(i=p;i<n;i++)
	{
		if(i>p)
		{
			if(Query(pst[l+1],pst[i]))
			{
				l=p;
				p=i;
			}
		}
		if(i==p)
		{
			for(j=p;j>l;j--)
			{
				sq[pst[j]]=zs;
				zs++;
			}
		}
	}
	for(i=0;i<n;i++)
	{
		v.push_back(sq[i]);
	}
	return v;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 75 / 75