Submission #413753

#	Time	Username	Problem	Language	Result	Execution time	Memory
413753		Antekb	Gondola (IOI14_gondola)	C++14	100 / 100	33 ms	2600 KiB

gondola

#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
	bool b=0;
	int V[n];
	for(int i=0; i<n; i++)V[i]=inputSeq[i];
	sort(V, V+n);
	for(int i=1; i<n; i++)if(V[i]==V[i-1])return 0;
	for(int i=0; i<n; i++){
		if(inputSeq[i]<=n){
			int t=inputSeq[i]-i-1;
			//cout<<inputSeq[i]<<"\n";
			for(int j=0; j<n; j++)V[j]=inputSeq[(j-t+n)%n];
			//for(int j=0; j<n; j++)cout<<V[j]<<" ";
			b=1;
			break;
		}
	}
	if(b==0)return 1;
	for(int i=0; i<n; i++)if(V[i]<=n && V[i]!=i+1)b=0;
	for(int i=0; i<n; ++i)inputSeq[i]=V[i];
	return b;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	if(!valid(n, gondolaSeq))return 0;
	/*vector<int > V(n);
	for(int i=0; i<n; i++)V[i]=inputSeq[i];
	sort(V.begin(), V.end());*/
	int m=0;
	for(int i=0; i<n; i++){
		if(gondolaSeq[i]>gondolaSeq[m])m=i;
	}
	int l=gondolaSeq[m]-n;
	bool b=1;
	//for(int i=0; i<n; i++)cout<<gondolaSeq[i]<<" ";
	//cout<<"\n"<<m<<"\n";
	for(int i=0; i<n; i++){
		if(gondolaSeq[i]>n && i!=m)replacementSeq[gondolaSeq[i]-n-1]=i+1;
	}
	gondolaSeq[m]=m+1;
	for(int i=0; i<l; i++){
		if(!replacementSeq[i]){
			replacementSeq[i]=gondolaSeq[m];
			gondolaSeq[m]=i+n+1;
		}
	}
	return l;
}

//----------------------
typedef long long ll;
const int mod=1e9+9;
ll pot(int a, int b){
	if(b==0)return 1;
	if(b==1)return a;
	ll c=pot(a, b/2);
	c=c*c%mod;
	return c*pot(a, b&1)%mod;
}
int countReplacement(int n, int inputSeq[])
{
	if(!valid(n, inputSeq))return 0;
	long long ans=1;
	bool b=0;
	for(int i=0; i<n; i++)if(inputSeq[i]==i+1)b=1;
	if(!b)ans=n;
	vector<int> V;
	for(int i=0; i<n; i++)if(inputSeq[i]>n)V.push_back(inputSeq[i]);
	V.push_back(n);
	sort(V.begin(), V.end());
	for(int i=1; i<V.size(); i++){
		ans=ans*pot(V.size()-i, V[i]-V[i-1]-1)%mod;
	}
	return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:40:7: warning: unused variable 'b' [-Wunused-variable]
   40 |  bool b=1;
      |       ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int 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