#include <bits/stdc++.h>
using namespace std;
//#include "gondola.h"
vector<int> bld(int n, int k, int gondolaSeq[]) {
vector<int> seq;
seq.push_back(gondolaSeq[k]);
for(int i = 1; i <= n - gondolaSeq[k]; i ++) {
int j = (k + i) % n;
seq.push_back(gondolaSeq[j]);
}
reverse(seq.begin(), seq.end());
for(int i = 1; i <= gondolaSeq[k] - 1; i ++) {
int j = (k - i + n) % n;
seq.push_back(gondolaSeq[j]);
}
reverse(seq.begin(), seq.end());
return seq;
}
int valid(int n, int inputSeq[]) {
int max_value = *max_element(inputSeq, inputSeq + n);
vector<int> arr;
int total = 0;
for(int i = 0; i < n; i ++) {
if(inputSeq[i] <= n) {
arr.push_back(i);
}
}
for(int i = 0; i + 1 < arr.size(); i ++) {
if(inputSeq[arr[i]] > inputSeq[arr[i + 1]]) {
total ++ ;
}
}
sort(inputSeq, inputSeq + n);
for(int i = 0; i + 1 < n; i ++) {
if(inputSeq[i] == inputSeq[i + 1]) {
return 0;
}
}
return total < 2;
}
//----------------------
struct DSU {
vector<int> par;
void init(int n) {
par.resize(n + 10);
for(int i = 1; i <= n; i ++) par[i] = i;
}
int get_root(int x) {
return par[x] == x ? x : par[x] = get_root(par[x]);
}
void unite(int u, int v) {
u = get_root(u);
v = get_root(v);
if(u == v) return ;
par[v] = u;
}
};
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int max_value = *max_element(gondolaSeq, gondolaSeq + n);
DSU F;
F.init(max_value + 1);
int k = 0;
for(int i = 0; i < n; i ++) {
if(gondolaSeq[k] > gondolaSeq[i]) {
k = i;
}
}
for(int i = 0; i < n; i ++) {
F.unite(gondolaSeq[i] + 1, gondolaSeq[i]);
}
int l = 0;
if(gondolaSeq[k] > n) {
for(int i = 0; i < n; i ++) {
for(int j = i + 1; j < gondolaSeq[i]; j = F.get_root(j)) {
replacementSeq[l ++] = j;
F.unite(j + 1, j);
}
}
} else {
vector<int> seq = bld(n, k, gondolaSeq);
for(int i = 0; i < n; i ++) {
for(int j = i + 1; j < seq[i]; j = F.get_root(j)) {
replacementSeq[l ++] = j;
F.unite(j + 1, j);
}
}
}
return l;
}
//----------------------
const int mod = 1000000009;
int binpow(int a, int b) {
if(!b) return 1;
if(b % 2 == 0) {
int x = binpow(a, b / 2);
return 1LL * x * x % mod;
}
return 1LL * binpow(a, b - 1) * a % mod;
}
int countReplacement(int n, int inputSeq[]) {
if(!valid(n, inputSeq)) return 0;
int k = 0;
for(int i = 0; i < n; i ++) {
if(inputSeq[k] > inputSeq[i]) {
k = i;
}
}
vector<int> seq;
for(int i = 0; i < n; i ++) {
if(inputSeq[i] > n) {
seq.push_back(inputSeq[i]);
}
}
sort(seq.begin(), seq.end());
int curr = n;
int total = 1;
if(inputSeq[k] > n) {
for(int i = 0; i < n; i ++) {
total = 1LL * total * (i + 1) % mod;
}
}
for(int i = 0; i < seq.size(); i ++) {
if(seq[i] > curr + 1)
total = 1LL * total * binpow((seq.size() - i), seq[i] - 1 - curr) % mod;
curr = seq[i];
}
return total;
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i = 0; i + 1 < arr.size(); i ++) {
| ~~~~~~^~~~~~~~~~~~
gondola.cpp:26:9: warning: unused variable 'max_value' [-Wunused-variable]
26 | int max_value = *max_element(inputSeq, inputSeq + n);
| ^~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:158:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for(int i = 0; i < seq.size(); i ++) {
| ~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccVdWx0i.o: in function `main':
grader.cpp:(.text.startup+0xb6): undefined reference to `valid'
/usr/bin/ld: grader.cpp:(.text.startup+0x108): undefined reference to `countReplacement'
/usr/bin/ld: grader.cpp:(.text.startup+0x132): undefined reference to `replacement'
collect2: error: ld returned 1 exit status
