#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, n)
#define ffj For(j, 0, n)
#define ffa ffi ffj
#define s <<" "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=100000, MOD=1000000009;
int valid(int n, int inputSeq[]) {
set<int> have;
ffi have.insert(inputSeq[i]);
if (have.size() != n) return 0;
int correct[MAXN];
ffi if (inputSeq[i] <= n) {
correct[i] = inputSeq[i];
For (j, i+1, n) {
correct[j] = 1+correct[j-1];
if (correct[j] == n+1) correct[j] = 1;
}
correct[0] = 1+correct[n-1];
if (correct[0] == n+1) correct[0] = 1;
For (j, 1, i) {
correct[j] = 1+correct[j-1];
if (correct[j] == n+1) correct[j] = 1;
}
break;
}
ffi if (inputSeq[i] != correct[i] && inputSeq[i] <= n) return 0;
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int correct[MAXN];
ffi correct[i] = i+1;
ffi if (gondolaSeq[i] <= n) {
correct[i] = gondolaSeq[i];
For (j, i+1, n) {
correct[j] = 1+correct[j-1];
if (correct[j] == n+1) correct[j] = 1;
}
correct[0] = 1+correct[n-1];
if (correct[0] == n+1) correct[0] = 1;
For (j, 1, i) {
correct[j] = 1+correct[j-1];
if (correct[j] == n+1) correct[j] = 1;
}
break;
}
int at = 0;
int val = 0, save;
ffi if (gondolaSeq[i] > val) val = gondolaSeq[i], save = i;
int loc[250001];
For (i, 0, 250001) loc[i] = -1;
ffi loc[gondolaSeq[i]] = i;
For (i, n+1, val+1) {
if (loc[i] == -1) {
replacementSeq[at] = correct[save];
correct[save] = i;
at++;
}
else {
replacementSeq[at] = correct[loc[i]];
correct[loc[i]] = i;
at++;
}
}
return at;
}
int countReplacement(int n, int inputSeq[]) {
if (valid(n, inputSeq) == 0) return 0;
ll ret = 1;
set<int> have;
int big = 0;
ffi if (inputSeq[i] > n) have.insert(inputSeq[i]), big = max(big, inputSeq[i]);
int at = n+1;
ll base = have.size();
ll pb[31];
for (int i: have) {
int p = i-at;
pb[0] = base;
//w<< base s p <<e;
For (i, 1, 31) pb[i] = pb[i-1]*pb[i-1], pb[i] %= MOD;
For (i, 0, 31) if (p & (1<<i)) {
//w<<i s (1<<i) s pb[i]<<e;
ret *= pb[i];
ret %= MOD;
}
//w<< ret<<e;
base--;
at = i+1;
}
bool small = false;
ffi if (inputSeq[i] <= n) small = true;
if (!small) ret *= n, ret %= MOD;
return ret;
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:21:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (have.size() != n) return 0;
~~~~~~~~~~~~^~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:65:46: warning: 'save' may be used uninitialized in this function [-Wmaybe-uninitialized]
replacementSeq[at] = correct[save];
~~~~~~~~~~~~^
/tmp/ccQVTPwc.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
