#include "gondola.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAX=1e6;
const int mod=1e9;
int arr[MAX],fre[MAX];
int power(int base,int exp)
{
int res=1;
while(exp)
{
if(exp%2)
res*=base;
base*=base;
res%=mod;
base%=mod;
exp/=2;
}
return res;
}
int valid(int n, int inputSeq[])
{
int N=n,ok=1;
for(int A=0;A<N;A++)
{
fre[inputSeq[A]]++;
if(fre[inputSeq[A]]>1)
return 0;
}
for(int A=0;A<N;A++)
{
if(inputSeq[A]<=N)
{
ok=0;
inputSeq[A]--;
for(int B=A;B>=0;B--)
{
arr[B]=inputSeq[A];
inputSeq[A]--;
if(inputSeq[A]<0)
inputSeq[A]+=N;
}
inputSeq[A]=arr[A];
for(int B=A+1;B<N;B++)
{
inputSeq[A]++;
if(inputSeq[A]>=N)
inputSeq[A]=0;
arr[B]=inputSeq[A];
}
inputSeq[A]=arr[A]+1;
break;
}
}
if(ok)
return 1;
for(int A=0;A<N;A++)
arr[A]++;
for(int A=0;A<N;A++)
{
if(inputSeq[A]<=N and arr[A]!=inputSeq[A])
return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
return -2;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq))
return 0;
sort(inputSeq,inputSeq+n);
vector<int> vec;
for(int A=0;A<n;A++)
if(inputSeq[A]>n)
vec.push_back(inputSeq[A]);
sort(vec.begin(),vec.end());
int res=1,ptr=0,cnt=vec.size();
while(ptr<n and inputSeq[ptr]<=n)
++ptr;
for(int A=0;A<vec.size()-1;A++)
{
while(ptr<n and inputSeq[ptr]<=vec[A])
++ptr,--cnt;
//cout<<ptr<<"\n";
if(vec[A+1]-vec[A]>1)
{
res*=power(cnt,vec[A+1]-vec[A]-1);
res%=mod;
}
}
if(vec[0]!=n+1)
{
res*=vec.size();
res%=mod;
}
if(inputSeq[0]>n)
{
res*=n;
res%=mod;
}
return res;
}
/*signed main()
{
ios_base::sync_with_stdio(false);
int arr[]={3,4};
cout<<countReplacement(2,arr);
return 0;
}*/
Compilation message
gondola.cpp: In function 'long long int countReplacement(long long int, long long int*)':
gondola.cpp:95:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int A=0;A<vec.size()-1;A++)
~^~~~~~~~~~~~~
/tmp/cckZ1MJV.o: In function `main':
grader.cpp:(.text.startup+0xc3): undefined reference to `countReplacement'
grader.cpp:(.text.startup+0xe2): undefined reference to `valid'
grader.cpp:(.text.startup+0x106): undefined reference to `replacement'
collect2: error: ld returned 1 exit status
