This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "gondola.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
int vis[1000001];
int res1[1000001];
pair <int, int> arr[1000001];
long long x[1000001];
long long mod = 1e9+9;
map <int, int> vis1;
long long binpow (long long a, long long b) {
if (b == 0)
return 1;
if (b % 2 == 1)
return binpow (a, b-1) * 1ll * a % mod;
else {
int c = binpow (a, b/2);
return c * 1ll * c % mod;
}
}
int valid(int n, int inputSeq[])
{
int ind = 0;
int num = 0;
for(int i = 0 ; i< n ; i++){
if(inputSeq[i]>=1 && inputSeq[i] <=n ){
ind = i;
num = inputSeq[i];
}
if(inputSeq[i] <1)
return 0;
if(vis[inputSeq[i]] ==1)
return 0;
vis[inputSeq[i]]=1;
}
if(num==0)
return 1;
for(int i = 0 ; i < n; i++)
if(inputSeq[i] <= n){
if( (ind + (inputSeq[i] - num) +n ) %n!=i )
return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int mx = 0;
int mxind=0;
int ind = 0;
int num = 0;
int cnt = 0;
for(int i = 0 ; i < n; i++){
arr[i] = make_pair(gondolaSeq[i] , i+1);
vis[gondolaSeq[i]]=1;
if( gondolaSeq[i]>=1 && gondolaSeq[i] <=n ){
ind = i+1;
num = gondolaSeq[i];
}
if ( mx < gondolaSeq[i]){
mx = gondolaSeq[i];
mxind =i;
}
}
sort(arr, arr + n);
if(num == 0){
vector <int > vec;
for(int i = mx-1; i>n;i--){
if(vis[i]==0)
vec.push_back(i);
}
for(int i= 0; i < n ;i++){
int t = arr[i].second;
int p = arr[i].first;
replacementSeq[cnt]=t;
cnt ++;
while( vec.size () > 0 && p > vec.back()){
replacementSeq[cnt]=vec.back();
cnt ++;
vec.pop_back();
}
}
return mx - n;
}
for(int i =1; i <=n ;i++){
res1[i-1] = (num + i -ind + n)%n ;
if(res1[i-1]==0)
res1[i-1]=n;
}
vector <int > vec;
for(int i = mx-1; i>n;i--){
if(vis[i]==0)
vec.push_back(i);
}
for(int i =0 ; i <n;i++){
int t = arr[i].second;
int p = arr[i].first;
if(gondolaSeq[t-1]!=res1[t-1]){
replacementSeq[cnt]=res1[t-1];
cnt ++;
while( vec.size () > 0 && gondolaSeq[t-1] > vec.back()){
replacementSeq[cnt]=vec.back();
cnt ++;
vec.pop_back();
}
}
}
return mx - n;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
int ind = 0;
int num = 0;
for(int i = 0 ; i< n ; i++){
if(inputSeq[i]>=1 && inputSeq[i] <=n ){
ind = i;
num = inputSeq[i];
}
if(inputSeq[i] <1)
return 0;
if(vis1[inputSeq[i]] ==1)
return 0;
vis1[inputSeq[i]]=1;
}
if(num!=0)
for(int i = 0 ; i < n; i++)
if(inputSeq[i] <= n){
if( (ind + (inputSeq[i] - num) +n ) %n!=i )
return 0;
}
sort(inputSeq, inputSeq + n);
for(int i = 0 ; i < n; i++)
x[i] = inputSeq[i];
bool f=true;
long long res= 1;
for(int i = 0; i < n ; i++ ){
if(x[i] > n){
if(f){
res = res * 1ll * binpow( (n- i), (x[i] - n - 1) ) % mod;
}
else{
res = res * 1ll * binpow( (n- i), x[i] - x[i-1] - 1) % mod;
}
f=false;
}
}
if(x[0] > n)
res = res * 1ll * n % mod;
return res;
}
Compilation message (stderr)
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:103:13: warning: unused variable 'p' [-Wunused-variable]
103 | int p = arr[i].first;
| ^
gondola.cpp:53:9: warning: variable 'mxind' set but not used [-Wunused-but-set-variable]
53 | int mxind=0;
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |