Submission #1189764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189764		boclobanchat	Gondola (IOI14_gondola)	C++20	100 / 100	49 ms	5960 KiB

gondola

#include<bits/stdc++.h>
#include"gondola.h"
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int mod=1e9+9;
int poww(int n,int m)
{
	int res=n,ans=1;
	while(m)
	{
		if(m&1) ans=(long long)ans*res%mod;
		res=(long long)res*res%mod,m/=2;
	}
	return ans;
}
int valid(int n,int inputSeq[])
{
	int uni=-1;
	bool ck=true;
	map<int,int> mp;
	for(int i=0;i<n;i++)
	{
		if(mp[inputSeq[i]]) return 0;
		if(inputSeq[i]<=n)
		{
			int res=(inputSeq[i]-(i+1)+n)%n;
			if(uni==-1) uni=res;
			else if(res!=uni) return 0;
		}
		mp[inputSeq[i]]=true;
	}
	return 1;
}
int replacement(int n,int gondolaSeq[],int replacementSeq[])
{
	int uni=-1,ans=0,prv=n;
	for(int i=0;i<n;i++) if(gondolaSeq[i]<=n&&uni==-1) uni=(gondolaSeq[i]-(i+1)+n)%n;
	if(uni==-1) uni=0;
	vector<ii> val(n);
	for(int i=0;i<n;i++) val[i]={gondolaSeq[i],i};
	sort(val.begin(),val.end());
	for(int i=0;i<n;i++) if(val[i].fi>n)
	{
		int pre=(val[i].se+uni)%n+1;
		replacementSeq[ans++]=pre;
		for(int j=prv+1;j<val[i].fi;j++) replacementSeq[ans++]=j;
		prv=val[i].fi;
	}
	return ans;
}
int countReplacement(int n,int inputSeq[])
{
	int uni=-1,ans=1,prv=n;
	bool ck=true,eu=false;
	map<int,int> mp;
	for(int i=0;i<n;i++)
	{
		if(mp[inputSeq[i]]) return 0;
		if(inputSeq[i]<=n)
		{
			int res=(inputSeq[i]-(i+1)+n)%n;
			if(uni==-1) uni=res,eu=true;
			else if(res!=uni) return 0;
		}
		mp[inputSeq[i]]=true;
	}
	if(uni==-1) uni=0;
	vector<ii> val(n);
	for(int i=0;i<n;i++) val[i]={inputSeq[i],i};
	sort(val.begin(),val.end());
	for(int i=0;i<n;i++) if(val[i].fi>n) ans=(long long)ans*poww(n-i,val[i].fi-prv-1)%mod,prv=val[i].fi;
	if(!eu) ans=(long long)ans*n%mod;
	return ans;
}

• 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