#include "gondola.h"
#include <bits/stdc++.h>
#define MOD 1000000009
int powmod(int a,int b) {
if (b == 0)return 1;
if (b == 1)return a;
int lilhelp = powmod(a,b/2);
int ret = (lilhelp * lilhelp) % MOD;
if (b % 2 == 0) ret = (ret * a) % MOD;
return ret;
}
int valid(int n, int inputSeq[])
{
std::set<int>st;
int ls = -1,in;
for (int i = 0;i<n;i++) {
st.insert(inputSeq[i]);
if (inputSeq[i] <= n) {
if (ls == -1) {
in = i;
ls = inputSeq[i];
continue;
}
if (inputSeq[i] < ls) {
if (inputSeq[i] != 1)return 0;
else if (ls - inputSeq[i] != n - i + in)return 0;
}
else {
if (inputSeq[i] - ls != i - in)return 0;
}
in = i;
ls = inputSeq[i];
}
}
if (st.size() != n)return 0;
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int in[n],le = 0,idx = -1 , sz = 0;
std::vector< std::pair<int,int> >v;
for (int i = 0;i<n;i++) in[i] = i + 1;
for (int i = 0;i<n;i++) {
if (gondolaSeq[i] <= n) {
idx = i;
in[i] = gondolaSeq[i];
}
else {
v.push_back(std::make_pair(gondolaSeq[i],i));
sz++;
}
}
std::sort(v.begin(),v.end());
if (idx != -1) {
int l = idx - 1,r = idx + 1;
while (l >= 0) {
if (in[l + 1] == 1)in[l] = n;
else in[l] = in[l + 1] - 1;
l--;
}
while (r < n) {
if (in[r - 1] == n)in[r] = 1;
else in[r] = in[r - 1] + 1;
r++;
}
}
for (int i = 0;i<sz;i++) {
if (i == 0) {
replacementSeq[le++] = in[v[i].second];
int k = n + 1;
while (k < v[i].first) {
replacementSeq[le++] = k;
k++;
}
}
else {
replacementSeq[le++] = in[v[i].second];
int k = v[i - 1].first + 1;
while (k < v[i].first) {
replacementSeq[le++] = k;
k++;
}
}
/*std::cout<<i<<" "<<le<<std::endl;
for (int j = 0;j<le;j++) std::cout<<replacementSeq[j]<<" ";
std::cout<<std::endl;*/
}
return le;
}
//----------------------
long long countReplacement(int n, int inputSeq[])
{
if (valid(n,inputSeq) == 0)return 0;
long long ans = 1 , lft = 0 , sz = 0,lst;
std::vector< std::pair<long long,long long> >v;
for (int i = 0;i<n;i++) {
if (inputSeq[i] > n) {
v.push_back(std::make_pair(inputSeq[i],i));
sz++;
lft++;
}
}
std::sort(v.begin(),v.end());
lst = n;
for (int i = 0;i<sz;i++) {
ans = (ans * powmod(sz - (i + 1) + 1,v[i].first - lst - 1)) % MOD;
lft--;
lst = v[i].first;
}
if (sz == n)ans *= n;
return ans % MOD;
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (st.size() != n)return 0;
~~~~~~~~~~^~~~
gondola.cpp: In function 'long long int countReplacement(int, int*)':
gondola.cpp:98:11: error: ambiguating new declaration of 'long long int countReplacement(int, int*)'
long long countReplacement(int n, int inputSeq[])
^~~~~~~~~~~~~~~~
In file included from gondola.cpp:1:0:
gondola.h:12:5: note: old declaration 'int countReplacement(int, int*)'
int countReplacement(int n, int inputSeq[]);
^~~~~~~~~~~~~~~~
