#include "gondola.h"
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int valid(int n, int inputSeq[])
{
vector<int> occurences (250001, 0);
vector<int> index (n, -1);
for (int i = 0; i < n; i++){
occurences[inputSeq[i]]++;
if (inputSeq[i] <= n){
//cout << i << ' ' << reduced_sequence[i] << endl;
index[inputSeq[i] - 1] = i;
}
}
for (int i = 0; i < occurences.size(); i++){
if (occurences[i] > 1){
return 0;
}
}
int lowest_g;
for (int i = 0; i < n; i++){
if (index[i] != -1){
lowest_g = i;
break;
}
}
for (int i = lowest_g; i < n; i++){
if (index[i] != -1){
//cout << i << ' ' << index[i] << endl;
if ((index[lowest_g] + i - lowest_g) % n != index[i]){
return 0;
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int first_original = 0;
int first_value = 1;
for (int i = 0; i < n; i++){
if (gondolaSeq[i] <= n){
first_original = i;
first_value = gondolaSeq[i];
}
}
vector<pair<int, int> > to_replace;
for (int i = 0; i < n; i++){
int current_pos = (i + first_original) % n;
int current_original_value = (i + first_value);
if (current_original_value > n){
current_original_value -= n;
}
int target_value = gondolaSeq[current_pos];
//cout << first_value << ' ' << i << ' ' << gondolaSeq[i] << endl;
if (target_value != current_original_value){
to_replace.push_back(make_pair(target_value, current_original_value));
}
}
sort(to_replace.begin(), to_replace.end());
int current_unused = n + 1;
int current_replacement = 0;
//cout << to_replace.size() << endl;
for (int i = 0; i < to_replace.size(); i++){
int c_value = to_replace[i].second;
while (c_value != to_replace[i].first){
replacementSeq[current_replacement] = c_value;
c_value = current_unused;
current_replacement++;
current_unused++;
}
}
return current_replacement;
}
//----------------------
long long fast_pow(long long a, long long k, long long p){
if (a == 0){
return 0;
}
if (k == 0){
return 1;
}
if (k % 2 == 1){
long long b = fast_pow(a, k / 2, p);
return (((b * b) % p) * a) % p);
}
long long b = fast_pow(a, k / 2, p);
return ((b * b) % p);
}
int countReplacement(int n, int inputSeq[])
{
long long p = 1000000009;
if (valid(n, inputSeq) == 0){
return 0;
}
long long first_original = 0;
long long first_value = 1;
for (int i = 0; i < n; i++){
if (inputSeq[i] <= n){
first_original = i;
first_value = inputSeq[i];
}
}
vector<pair<long long, long long> > to_replace;
to_replace.push_back(make_pair(n, 0));
for (long long i = 0; i < n; i++){
long long current_pos = (i + first_original) % n;
long long current_original_value = (i + first_value);
if (current_original_value > n){
current_original_value -= n;
}
long long target_value = inputSeq[current_pos];
//cout << first_value << ' ' << i << ' ' << gondolaSeq[i] << endl;
if (target_value != current_original_value){
to_replace.push_back(make_pair(target_value, current_original_value));
}
}
sort(to_replace.begin(), to_replace.end());
long long total = 1;
long long current_options = to_replace.size() - 1;
for (int i = 0; i < to_replace.size() - 1; i++){
//cout << current_options << ' ' << to_replace[i + 1].first << ' ' << to_replace[i].first << endl;
total = (total * fast_pow(current_options, to_replace[i + 1].first - to_replace[i].first - 1, p)) % p;
current_options--;
}
return ((int) total);
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < occurences.size(); i++){
~~^~~~~~~~~~~~~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < to_replace.size(); i++){
~~^~~~~~~~~~~~~~~~~~~
gondola.cpp: In function 'long long int fast_pow(long long int, long long int, long long int)':
gondola.cpp:114:39: error: expected ';' before ')' token
return (((b * b) % p) * a) % p);
^
gondola.cpp:114:39: error: expected primary-expression before ')' token
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:163:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < to_replace.size() - 1; i++){
~~^~~~~~~~~~~~~~~~~~~~~~~
