#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
bool Check(vector<int> a)
{
int n=a.size(),i,j,k;
for(i=0;i<n;i++) if(a[i]<=n) break;
if(i==n)
{
sort(a.begin(),a.end());
for(i=1;i<n;i++) if(a[i]==a[i-1]) return 0;
return 1;
}
vector<int> b;
j=i-a[i]+1;
if(j<0)
{
for(k=j+n;k<n;k++) b.pb(a[k]);
for(k=0;k<j+n;k++) b.pb(a[k]);
}
else
{
for(k=j;k<n;k++) b.pb(a[k]);
for(k=0;k<j;k++) b.pb(a[k]);
}
//for(i=0;i<n;i++) printf("%i ",b[i]);printf("\n");
for(i=0;i<n;i++) if(b[i]<=n && b[i]!=i+1) return 0;
for(i=0;i<n;i++) if(b[i]==0) return 0;
sort(b.begin(),b.end());
for(i=1;i<n;i++) if(b[i]==b[i-1]) return 0;
return 1;
}
vector<int> Replace(vector<int> a)
{
int n=a.size(),i,j,k;vector<int> sol;
for(i=0;i<n;i++) if(a[i]<=n) break;
if(i==n)
{
vector<pair<int,int> > tmp;
for(i=0;i<n;i++) tmp.pb(mp(a[i],i+1));
sort(tmp.begin(),tmp.end());
int m=n;
for(i=0;i<tmp.size();i++)
{
sol.pb(tmp[i].second);m++;
while(m<tmp[i].first)
{
sol.pb(m);m++;
}
}
return sol;
}
vector<int> b;
j=i-a[i]+1;
if(j<0)
{
for(k=j+n;k<n;k++) b.pb(a[k]);
for(k=0;k<j+n;k++) b.pb(a[k]);
}
else
{
for(k=j;k<n;k++) b.pb(a[k]);
for(k=0;k<j;k++) b.pb(a[k]);
}
vector<pair<int,int> > tmp;
int m=n;
for(i=0;i<n;i++) if(b[i]>n) tmp.pb(mp(b[i],i+1));
sort(tmp.begin(),tmp.end());
for(i=0;i<tmp.size();i++)
{
sol.pb(tmp[i].second);m++;
while(m<tmp[i].first)
{
sol.pb(m);m++;
}
}
return sol;
}
const int mod=1e9+9;
int pow(int x, int k)
{
int ret=1;
for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) ret=(ll)ret*x%mod;
return ret;
}
int Count(vector<int> a)
{
vector<int> tmp;
int i,j,k,n=a.size();
for(i=0;i<n;i++) if(a[i]>n) tmp.pb(a[i]);
sort(tmp.begin(),tmp.end());
int last=n,sol=1,sz=tmp.size();
for(i=0;i<sz;i++)
{
int dist=tmp[i]-last-1;
sol=(ll)sol*pow(sz-i,dist)%mod;
last=tmp[i];
}
if(sz==n) sol=(ll)sol*n%mod;
return sol;
}
int valid(int n, int a[])
{
int i;
vector<int> b;
for(i=0;i<n;i++) b.pb(a[i]);
return (int)Check(b);
}
int replacement(int n, int a[], int sol[])
{
int i;
vector<int> b;
for(i=0;i<n;i++) b.pb(a[i]);
vector<int> ans=Replace(b);
for(i=0;i<ans.size();i++) sol[i]=ans[i];
return ans.size();
}
int countReplacement(int n, int a[])
{
int i;
vector<int> b;
for(i=0;i<n;i++) b.pb(a[i]);
if(Check(b)) return Count(b);
else return 0;
}
Compilation message
gondola.cpp: In function 'std::vector<int> Replace(std::vector<int>)':
gondola.cpp:47:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<tmp.size();i++)
~^~~~~~~~~~~
gondola.cpp:73:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<tmp.size();i++)
~^~~~~~~~~~~
gondola.cpp: In function 'int Count(std::vector<int>)':
gondola.cpp:93:8: warning: unused variable 'j' [-Wunused-variable]
int i,j,k,n=a.size();
^
gondola.cpp:93:10: warning: unused variable 'k' [-Wunused-variable]
int i,j,k,n=a.size();
^
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:119:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<ans.size();i++) sol[i]=ans[i];
~^~~~~~~~~~~
/tmp/cc8lVF5W.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
