#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
int valid(int n, int a[]){
vector<pair<int,int>> v;
for(int i = 0 ; i < n ; i += 1){
if(a[i] <= n){
v.push_back({a[i],i});
}
}
sort(v.begin(),v.end());
for(int i = 1 ; i < v.size() ; i += 1){
int diff1 = v[i].first-v[i-1].first , diff2;
if(v[i].second > v[i-1].second){
diff2 = v[i].second-v[i-1].second;
}else{
diff2 = n-v[i-1].second+v[i].second;
}
if(diff1 != diff2){
return 0;
}
}
set<int> st;
for(int i = 0 ; i < n ; i += 1){
if(st.count(a[i])){
return 0;
}
st.insert(a[i]);
}
return 1;
}
//----------------------
int replacement(int n, int a[], int replacementSeq[]){
int in[n];
for(int i = 0 ; i < n ; i += 1){
in[i] = i+1;
}
pair<int,int> v = {-1,-1};
vector<pair<int,int>> g;
for(int i = 0 ; i < n ; i += 1){
if(a[i] <= n){
v = {a[i],i};
}else{
g.push_back({a[i],i});
}
}
if(v.first != -1){
v.second -= v.first-1;
if(v.second < 0){
v.second += n;
}
int cnt = 1;
for(int i = v.second ; i < n ; i += 1){
in[i] = cnt;
cnt += 1;
}
for(int i = 0 ; i < v.second ; i += 1){
in[i] = cnt;
cnt += 1;
}
}
sort(g.begin(),g.end());
if(g.size() == 0){
return 0;
}
int p = 0 , cnt = 0;
for(int i = n+1 ; i <= g.back().first ; i += 1){
cnt += 1;
replacementSeq[i-n-1] = in[g[p].second];
in[g[p].second] = i;
if(i == g[p].first){
p += 1;
}
}
return cnt;
}
//----------------------
const int mod = 1000000009;
long long pw(long long a , long long b){
long long ret = 1;
while(b){
if(b % 2 == 1){
ret *= a;
ret %= mod;
}
a *= a;
a %= mod;
b /= 2;
}
return ret;
}
int countReplacement(int n, int a[]){
if(!valid(n,a)){
return 0;
}
vector<pair<int,int>> g;
bool ok = true;
for(int i = 0 ; i < n ; i += 1){
if(a[i] > n){
g.push_back({a[i],i});
}else{
ok = false;
}
}
sort(g.begin(),g.end());
int last = n;
long long ret = 1;
for(int i = 0 ; i < g.size() ; i += 1){
ret *= pw(g.size()-i,g[i].first-last-1);
ret %= mod;
last = g.first;
}
if(ok){
ret = (ret*n)%mod;
}
return ret;
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int i = 1 ; i < v.size() ; i += 1){
| ~~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i = 0 ; i < g.size() ; i += 1){
| ~~^~~~~~~~~~
gondola.cpp:117:12: error: 'class std::vector<std::pair<int, int> >' has no member named 'first'
117 | last = g.first;
| ^~~~~
