#include "gondola.h"
#include <iostream>
using namespace std;
long long int ans[100005];
long long int a[100005],b[100005],n;
int qs(int s,int e)
{
if(s>=e)return 0;
int l=s,r=e,mid=(a[l]+a[r])/2;
while(l<=r)
{
while(a[l]<mid)l++;
while(a[r]>mid)r--;
if(l<=r)
{
swap(a[l],a[r]);
swap(b[l],b[r]);
l++;
r--;
}
}
qs(s,r);
qs(l,e);
}
int valid(int N,long long int a[])
{
n=N;
int tmp=-1,mi=500005,tag[500005];
for(int i=0;i<=500000;i++)tag[i]=0;
for(int i=0;i<n;i++)
{
if(tag[a[i]]==1)return 0;
tag[a[i]]++;
}
for(int i=0;i<n;i++)
if(a[i]<=n && a[i]<mi)
{
tmp=i;
mi=a[i];
}
if(tmp==-1)return 1;
int p=n-1,i=tmp,t=mi;
while(p--)
{
i++;
i%=n;
t++;
if(a[i]<=n && a[i]!=t)return 0;
}
return 1;
}
//----------------------
int replacement(int N, int gondolaSeq[], int replacementSeq[])
{
n=N;
int t=-1;
for(int i=0;i<n;i++)a[i]=gondolaSeq[i];
for(int i=0;i<n;i++)
{
if(a[i]<=n)
{
t=i;
break;
}
}
if(t==-1)for(int i=0;i<n;i++)b[i]=i+1;
else
{
b[t]=a[t];
int now=a[t],i=t;
int p=n-1;
while(p--)
{
i++;
i%=n;
now=now%n+1;
b[i]=now;
}
}
//for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;
qs(0,n-1);
//for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;
int ans1=0,x=n+1;
for(int i=0;i<n;i++)
{
while(a[i]!=b[i])
{
replacementSeq[ans1]=b[i];
b[i]=x;
ans1++;
x++;
}
}
return ans1;
}
//----------------------
int countReplacement(int N,long long int inputSeq[])
{
cout<<"ok"<<endl;
if(valid(N,inputSeq)==0)return 0;
n=N;
int t=-1;
for(int i=0;i<n;i++)a[i]=inputSeq[i];
for(int i=0;i<n;i++)
{
if(a[i]<=n)
{
t=i;
break;
}
}
long long int ans1=1,x=n+1,tmp;
if(t==-1)
{
for(int i=0;i<n;i++)b[i]=i+1;
ans1=(ans1*n)%1000000009;
}
else
{
b[t]=a[t];
long long int now=a[t],i=t;
long long int p=n-1;
while(p--)
{
i++;
i%=n;
now=now%n+1;
b[i]=now;
}
}
//for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;
qs(0,n-1);
//for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;
for(long long int i=0;i<n;i++)
{
tmp=0;
while(a[i]!=b[i])
{
b[i]=x;
tmp++;
x++;
}
if(tmp!=0)
{
ans[0]++;
ans[ans[0]]=tmp;
}
}
for(long long int i=1;i<=ans[0];i++)
{
//cout<<ans[i]<<" ";
for(long long int j=1;j<=ans[i]-1;j++)ans1=(ans1*(ans[0]-i+1))%1000000009;
}
return ans1;
}
Compilation message
gondola.cpp: In function 'int qs(int, int)':
gondola.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
/tmp/cc8Z1fGT.o: In function `main':
grader.cpp:(.text.startup+0xc3): undefined reference to `countReplacement'
grader.cpp:(.text.startup+0xe2): undefined reference to `valid'
collect2: error: ld returned 1 exit status
