#include "gondola.h"
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
using namespace std;
int b[200005],c[200005],a[200005];
const int mod = 1e9 + 7;
int valid(int n, int gondolaSeq[]){
map <int,int> mp;
int k = -1;
for (int i=0;i<n;i++){
a[i] = gondolaSeq[i];
if (mp.find(a[i]) != mp.end()) return 0;
mp[a[i]] = 1;
if (a[i] > n) continue;
if (k == -1) k= i;
else if (a[k] > a[i]) k = i;
}
if (k==-1) return 1;
int m = 0;
int st = a[k];
for (int j = k; j < n; j++)
if (a[j] <= n) b[++m] = a[j],c[m] = st + (j - k);
for (int j = 0; j < k; j++)
if (a[j] <= n) b[++m] = a[j],c[m] = st + (n - k) + j;
for (int i = 1; i <= m; i++){
if (b[i] != c[i]) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int k = -1;
for (int i=0;i<n;i++){
a[i] = gondolaSeq[i];
if (a[i] > n) continue;
if (k == -1) k= i;
else if (a[k] > a[i]) k = i;
}
int st;
if (k == -1) k = 0,st = 1;
else st = a[k];
for (int j = k; j < n; j++) b[j] = st + (j - k);
for (int j = 0; j < k; j++) b[j] = st + (n - k) + j;
for (int j = 0; j < n; j++) if (b[j] > n) b[j] -= n;
int x = n + 1,m = -1;
vector <pair <int,int> > vec;
for (int i=0;i<n;i++){
if (gondolaSeq[i] > n) vec.pb({gondolaSeq[i],i});
}
sort(vec.begin(),vec.end());
for (int j=0;j<vec.size();j++){
int final = vec[j].f,i = vec[j].s;
int cur = b[i];
while (cur != final){
replacementSeq[++m] = cur;
cur = x++;
}
}
return m + 1;
}
//----------------------
ll pwr(ll a,ll b){
ll c=1;
while (b){
if (b&1) c=c*a%mod;
a=a*a%mod;
b/=2;
}
return c;
}
int countReplacement(int n, int inputSeq[]){
int chk = valid(n,inputSeq);
if (!chk) return 0;
vector <int> vec;
vec.pb(n);
for (int i = 0; i < n; i++)
if(inputSeq[i] > n) vec.pb(inputSeq[i]);
sort(vec.begin(),vec.end());
ll ans = 1,len = vec.size() - 1;
for (int i = 1; i < vec.size(); i++){
ll dist = vec[i] - vec[i - 1];
ans = ans * pwr(dist,len - i) % mod;
}
return ans;
}
Compilatio
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int j=0;j<vec.size();j++){
| ~^~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (int i = 1; i < vec.size(); i++){
| ~~^~~~~~~~~~~~
gondola.cpp: At global scope:
gondola.cpp:107:1: error: 'Compilatio' does not name a type
107 | Compilatio
| ^~~~~~~~~~
