#include "gondola.h"
#include <algorithm>
#include <iostream>
#include <map>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 250000;
int const modulo = 1000000009;
std::map<int, int> frec;
int valid(int n, int inputSeq[])
{
for(int i = 0; i < n; i++)
if(inputSeq[i] <= n) {
std::rotate(inputSeq, inputSeq + (n + i - inputSeq[i] + 1) % n, inputSeq + n);
break;
}
for(int i = 0; i < n; i++) {
if(frec[inputSeq[i]] == 1)
return false;
frec[inputSeq[i]] = 1;
if(inputSeq[i] <= n && i + 1 != inputSeq[i])
return false;
}
return true;
}
//----------------------
int seen[1 + nmax];
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
for(int i = 0; i < n; i++)
if(gondolaSeq[i] <= n) {
std::rotate(gondolaSeq, gondolaSeq + (n + i - gondolaSeq[i] + 1) % n, gondolaSeq + n);
break;
}
int smax = 0;
for(int i = 0; i < n; i++)
smax = MAX(smax, gondolaSeq[i]);
int pos = 0;
for(int i = 0; i < n; i++)
if(smax == gondolaSeq[i])
pos = i;
for(int i = 0;i < n; i++)
seen[gondolaSeq[i]] = 1 + i;
for(int i = n + 1; i <= smax; i++)
if(seen[i] == 0) {
replacementSeq[i - n - 1] = pos;
pos = i;
} else
replacementSeq[i - n - 1] = seen[i];
return smax - n;
}
//----------------------
int lgpow(int a, int b){
if(b == 0)
return 1;
else if(b == 1)
return a;
else {
int result = lgpow(a, b / 2);
if(b % 2 == 0)
return 1LL * result * result % modulo;
else
return 1LL * result * result % modulo * a % modulo;
}
}
int countReplacement(int n, int inputSeq[])
{
if(valid(n, inputSeq) == 0)
return 0;
else {
for(int i = 0; i < n; i++)
if(inputSeq[i] <= n) {
std::rotate(inputSeq, inputSeq + (n + i - inputSeq[i] + 1) % n, inputSeq + n);
break;
}
std::vector<int> v;
for(int i = 0; i < n; i++)
if(n < inputSeq[i] )
v.push_back(inputSeq[i]);
std::sort(v.begin(), v.end());
int last = n;
int result = 1;
for(int i = 0; i < v.size(); i++){
result = 1LL * result * lgpow(v.size() - i, v[i] - 1 - last);
last = v[i];
}
return result;
}
}
Compilation message
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:92:10: error: 'vector' is not a member of 'std'
std::vector<int> v;
^~~~~~
gondola.cpp:92:17: error: expected primary-expression before 'int'
std::vector<int> v;
^~~
gondola.cpp:95:9: error: 'v' was not declared in this scope
v.push_back(inputSeq[i]);
^
gondola.cpp:96:15: error: 'v' was not declared in this scope
std::sort(v.begin(), v.end());
^
