#include <bits/stdc++.h>
#include "gondola.h"
#include "grader.cpp"
using namespace std;
#define pb push_back
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define ll long long
const int N = (int)3e5 + 7;
int valid(int n, int inputSeq[]) {
int cnt = 1, start = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] == cnt) {
start = i;
break;
}
}
for (int i = start; i < n; i++) {
if (inputSeq[i] != cnt) {
return 0;
}
cnt++;
}
for (int i = 0; i < start; i++) {
if (inputSeq[i] != cnt) {
return 0;
}
cnt++;
}
return 1;
}
//----------------------
int has[N], pos[N];
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int start = -1, mx = -1;
memset(pos, -1, sizeof pos);
for (int i = 0; i < n; i++) {
has[gondolaSeq[i]] = 1;
pos[gondolaSeq[i]] = i;
mx = max(mx, gondolaSeq[i]);
if (gondolaSeq[i] <= n) {
if (start != -1) continue;
start = i - gondolaSeq[i] + 1;
if (start < 0) start += n;
}
}
deque < int > ans, dq;
if (start == -1)
start = 0;
for (int i = n + 1; i <= mx; i++) {
if (has[i]) {
int qwe = pos[i];
qwe -= start;
if (qwe < 0) qwe += n;
qwe++;
ans.pb(qwe);
while (!dq.empty()) {
ans.pb(dq.front());
dq.pop_front();
}
dq.clear();
} else {
dq.pb(i);
}
}
int i = 0;
for (int to : ans) {
replacementSeq[i++] = to;
}
return i;
}
//----------------------
int mod = (int)1e9 + 9;
int mult(ll a, ll b) {
return (a * b) % mod;
}
ll binpow(ll a, ll n) {
ll res = 1;
while (n) {
if (n & 1) {
res = mult(res, a);
}
a = mult(a, a);
n >>= 1;
}
return res;
}
int countReplacement(int n, int inputSeq[]) {
if (valid(n, inputSeq)) return 0;
int res = 1;
sort(inputSeq, inputSeq + n);
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n) continue;
if (!i) {
res = mult(res, binpow(n, inputSeq[i] - n - 1));
} else {
res = mult(res, binpow(n - i, inputSeq[i] - max(inputSeq[i - 1], n) - 1));
}
}
if (inputSeq[0] > n) {
res = mult(res, n);
}
return res;
}
Compilation message
/tmp/cc3gi8hS.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cccpD7gu.o:gondola.cpp:(.text.startup+0x0): first defined here
/tmp/cc3gi8hS.o:(.bss+0xf4260): multiple definition of `gondolaSequence'
/tmp/cccpD7gu.o:(.bss+0x33e1a0): first defined here
/tmp/cc3gi8hS.o:(.bss+0x0): multiple definition of `replacementSequence'
/tmp/cccpD7gu.o:(.bss+0x249f40): first defined here
collect2: error: ld returned 1 exit status
