Submission #39142

#	Time	Username	Problem	Language	Result	Execution time	Memory
39142		faustaadp	Gondola (IOI14_gondola)	C++14	100 / 100	76 ms	48924 KiB

gondola

#include "gondola.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
ll i,a[1010101],sat,tt,mi,ma,c[1010101],e[1010101],f[1010101],hs,b[1010101],hl,mo=1000000009;
unordered_map<ll,ll> am;
vector<ll> v;
int valid(int n, int inputSeq[])
{
	for(i=0;i<n;i++)
		if(am[inputSeq[i]]==0)
			am[inputSeq[i]]++;
		else
			return 0;
	//cout<<"sd";
	mi=10e17;
	for(i=0;i<n;i++)
		if(inputSeq[i]<mi)
		{
			mi=inputSeq[i];
			sat=i;
			tt=mi-1;
		}
	for(i=sat;i<2*n;i++)
	{
		tt++;
		if(tt>n)
			tt-=n;
		if(inputSeq[i%n]<=n)
			if(inputSeq[i%n]!=tt)
			{
			//	cout<<inputSeq[i%n]<<" "<<tt<<"\n";
				return 0;
			}
	}
	return 1;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	for(i=0;i<n;i++)
		a[i]=gondolaSeq[i];
	for(i=0;i<n;i++)
		ma=max(ma,(ll)gondolaSeq[i]);
	mi=10e17;
	for(i=0;i<n;i++)
		if(gondolaSeq[i]<mi)
		{
			mi=gondolaSeq[i];
			sat=i;
			tt=mi-1;
		}
	for(i=sat;i<2*n;i++)
	{
		tt++;
		while(tt>n)
			tt-=n;
	//	cout<<i%n<<" "<<tt<<"\n";
		e[i%n]=tt;
	}
	for(i=0;i<n;i++)
	{
		c[a[i]]=e[i];
		f[i+1]=i+1;
	}
	for(i=n+1;i<=ma;i++)
	{
		if(c[i]==0)
		{
			replacementSeq[i-n-1]=f[c[ma]];
			f[c[ma]]=i;
		}
		else
		{
			replacementSeq[i-n-1]=f[c[i]];
			f[c[i]]=i;
		}
	//	cout<<i-n-1<<" "<<replacementSeq[i-n-1]<<"\n";
	}
	return ma-n;
}

//----------------------
ll powo(ll aa,ll bb)
{
	if(bb==0)
		return 1;
	else
	if(bb==1)
		return aa;
	else
	{
		ll tj=powo(aa,bb/2);
		tj*=tj;
		tj%=mo;
		if(bb%2==1)
			tj*=aa;
		tj%=mo;
		return tj;
	}
}
int countReplacement(int n, int inputSeq[])
{
	if(!valid(n,inputSeq))
		return 0;
	else
	{
		hs=1;
		v.pb(n);
		for(i=0;i<n;i++)
			if(inputSeq[i]>n)
			{
			//	b[inputSeq[i]]=1;
				v.pb(inputSeq[i]);
				hl++;
			}
		for(i=0;i<n;i++)
			ma=max(ma,(ll)inputSeq[i]);
		mi=10e17;
		for(i=0;i<n;i++)
			if(inputSeq[i]<mi)
			{
				mi=inputSeq[i];
				sat=i;
				tt=mi-1;
			}
		sort(v.begin(),v.end());
		for(i=1;i<v.size();i++)
		{
			hs*=powo(hl,v[i]-v[i-1]-1);
			hs%=mo;
			hl--;
		}
		if(mi>n)
			hs*=n;
		hs%=mo;
	}
	return hs;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:131:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=1;i<v.size();i++)
            ^

• 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