#include "gondola.h"
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back
#define ss second
#define ff first
#define ext exit(0)
using namespace std;
ll i,j,z=0,st,ans;
vector<ll> vc,vv;
vector<pair<ll,ll> >v;
map<ll,ll>m;
int valid(int n, int inputSeq[])
{
for(i=0;i<n;i++){
if(m[inputSeq[i]]==1) return 0;
m[inputSeq[i]]++;
}
for(i=0;i<n;i++){
if(inputSeq[i]<n){
st=(i-inputSeq[i]+1+n)%n;
for(i=st;i<n;i++) vv.pub(inputSeq[i]);
for(i=0;i<st;i++) vv.pub(inputSeq[i]);
for(i=0;i<n;i++){
if(vv[i]>n) continue;
if(vv[i]!=i+1) return 0;
}
return 1;
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
for(i=0;i<n;i++) gondolaSeq[i]--;
for(i=0;i<n;i++){
if(gondolaSeq[i] < n){
st=(i-gondolaSeq[i]+n)%n;
}
}
for(i=0;i<n;i++){
if(gondolaSeq[i] >= n) v.pub(mp(gondolaSeq[i],(i-st+n)%n));
}
sort(v.begin(),v.end());
if(v.size()==0) {
return 0;
}
while(1){
if(v.size()==1){
while(v[0].ff>v[0].ss && v[0].ff>=n){
if(v[0].ff-1>=n)vc.pub(v[0].ff-1);
else vc.pub(v[0].ss);
v[0].ff--;
}
break;
}
if(v.back().ff==v[v.size()-2].ff+1){
vc.pub(v.back().ss);
v.pob();
}
else {
vc.pub(v.back().ff-1);
v.back().ff--;
if(v.back().ff==v.back().ss) v.pob();
}
}
reverse(vc.begin(),vc.end());
for(i=0;i<vc.size();i++) replacementSeq[i]=vc[i]+1;
return vc.size();
}
ll countReplacement(ll n, ll inputSeq[]) {
if(!valid(n,inputSeq)) return 0;
bool boo=false;
for(i=0;i<n;i++){
if(inputSeq[i]>n)vc.pub(inputSeq[i]);
else boo=true;
}
sort(vc.begin(),vc.end());
ll prev=n+1,ans=1,mod=1000000009;
for(i=0;i<vc.size();i++){
ll o=vc.size()-i,s=1,u=vc[i]-prev;
while(u>0){
if(u%2){
s=(ll)(s*o)%mod;
}
o=(ll)(o*o)%mod;
u/=2;
}
ans=(ll)(ans*s)%mod;
prev=vc[i]+1;
}
if(!boo) ans=(ll)(ans*n)%mod;
return ans;
}
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:70:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<vc.size();i++) replacementSeq[i]=vc[i]+1;
~^~~~~~~~~~
gondola.cpp: In function 'long long int countReplacement(long long int, long long int*)':
gondola.cpp:74:22: error: cannot convert 'long long int*' to 'int*' for argument '2' to 'int valid(int, int*)'
if(!valid(n,inputSeq)) return 0;
^
gondola.cpp:82:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<vc.size();i++){
~^~~~~~~~~~
