Submission #986363

#	Time	Username	Problem	Language	Result	Execution time	Memory
986363		Pyqe	Gondola (IOI14_gondola)	C++17	100 / 100	54 ms	9488 KiB

gondola

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

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long d=-1,pwk,dv=1e9+9;
map<long long,bool> vtd;
pair<long long,long long> as[100069];

long long pw(long long x,long long y)
{
	if(!y)
	{
		return 1;
	}
	pwk=pw(x,y/2);
	pwk=pwk*pwk%dv;
	if(y%2)
	{
		pwk=pwk*x%dv;
	}
	return pwk;
}

int valid(int n,int a[])
{
	long long i,k;
	
	for(i=0;i<n;i++)
	{
		if(vtd[a[i]])
		{
			return 0;
		}
		vtd[a[i]]=1;
		if(a[i]<=n)
		{
			k=(a[i]+n-i-1)%n+1;
			if(d+1&&k!=d)
			{
				return 0;
			}
			d=k;
		}
	}
	return 1;
}

int replacement(int n,int a[],int sq[])
{
	long long i,k=n,l,zs=0;
	
	valid(n,a);
	d+=2*(d==-1);
	for(i=0;i<n;i++)
	{
		as[i]={a[i],i};
	}
	sort(as,as+n);
	for(i=0;i<n;i++)
	{
		if(as[i].fr>n)
		{
			for(;k<as[i].fr;k++)
			{
				l=k;
				if(k==n||(i&&k==as[i-1].fr))
				{
					l=(d+as[i].sc-1)%n+1;
				}
				sq[zs]=l;
				zs++;
			}
		}
	}
	return zs;
}

int countReplacement(int n,int a[])
{
	long long i,l=n,z=1;
	
	if(!valid(n,a))
	{
		return 0;
	}
	if(d==-1)
	{
		z=z*n%dv;
	}
	sort(a,a+n);
	for(i=0;i<n;i++)
	{
		if(a[i]>n)
		{
			z=z*pw(n-i,a[i]-l-1)%dv;
			l=a[i];
		}
	}
	return z;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10