Submission #964535

#	Time	Username	Problem	Language	Result	Execution time	Memory
964535		UmairAhmadMirza	Gondola (IOI14_gondola)	C++14	100 / 100	52 ms	6480 KiB

gondola

#include <bits/stdc++.h>
#include <gondola.h>
using namespace std;
int const mod=1e9+9;
long long power(long long a,long long b){
	if(b==0)
		return 1;
	if(b==1)
		return a;
	long long pw=power(a,b/2);
	pw%=mod;
	pw*=pw;
	pw%=mod;
	if(b&1)
		pw*=a;
	pw%=mod;
	return pw;
}
int valid(int n, int inputSeq[]){
	map<int,bool> mp;
	deque<int> d;
	int k=n+1;
	for (int i = 0; i < n; ++i)//check unique
	{
		d.push_back(inputSeq[i]);
		if(mp[inputSeq[i]]){

			return 0;
		}
		mp[inputSeq[i]]=1;
		k=min(k,inputSeq[i]);
	}
	if(k==n+1)
		return 1;
	while(d[k-1]!=k){
		d.push_front(d.back());
		d.pop_back();
		// cerr<<"1"<<endl;
	}
	// cerr<<"1"<<endl;
	for (int i = 0; i < n; ++i)
		if(d[i]<=n && d[i]!=i+1)
			return 0;
	return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	int maxa=0;
	for (int i = 0; i < n; ++i)
		maxa=max(gondolaSeq[i],maxa);
	int k=n+1;
	deque<int> d;
	for (int i = 0; i < n; ++i)//check unique
	{
		d.push_back(gondolaSeq[i]);
		k=min(k,gondolaSeq[i]);
	}
	if(k<n+1){
		while(d[k-1]!=k){
			d.push_front(d.back());
			d.pop_back();
		}
		// cerr<<"set"<<endl;
	}
	int c=0;
	set<pair<int,int>> s;
	for (int i = 0; i < n; ++i)
		if(d[i]>n)
			s.insert({d[i],i+1});
	while(s.size()){
		auto p=*(s.begin());
		int dd=p.first;
		int cur=p.second;
		s.erase(p);
		while(cur<dd){
			replacementSeq[c]=cur;
			c++;
			cur=n+c;
		}
	}
	return c;
}
int countReplacement(int n, int inputSeq[]){
	if(valid(n,inputSeq)==0)
		return 0;
	vector<long long> v;
	long long ans=1;
	for (int i = 0; i < n; ++i)
		if(inputSeq[i]>n)
			v.push_back(inputSeq[i]);
	sort(v.begin(), v.end());
	long long cur=n;
	int sz=v.size();
	if(sz==n)
		ans=sz;
	for (int i = 0; i < sz; ++i)
	{
		// cout<<sz-i<<' '<<(v[i]-cur)-1<<endl;
		ans*=power(sz-i,(v[i]-cur)-1)%mod;
		ans%=mod;
		cur=v[i];
	}
	return ans%mod;
}

• 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