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"
#define st first
#define nd second
#define ii pair<int,int>
#define pb push_back
#define sz(x) (x.size())
#include<bits/stdc++.h>
using namespace std;
int find_fixed(int n,int inputSeq[]) {
int fixed=0;
for(int i=0;i<n;i++) {
if(inputSeq[i]<=n) {
fixed=i;
break ;
}
}
return fixed;
}
int valid(int n, int inputSeq[]) {
map<int,int> fr;
int fixed=find_fixed(n,inputSeq);
int tot=2;
int cur=inputSeq[fixed];
for(int i=fixed;(tot-=(i==fixed));i=(i+1)%n,cur++) {
if(cur>n) cur-=n;
if(inputSeq[i]>n) {
fr[inputSeq[i]]++;
continue ;
}
if(inputSeq[i]!=cur) return 0;
}
for(auto x:fr) {
if(x.nd>1) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int fixed=find_fixed(n,gondolaSeq);
int cur=(gondolaSeq[fixed]<=n?gondolaSeq[fixed]:1);
int tot=2;
vector<ii> change;
for(int i=fixed;(tot-=(i==fixed));i=(i+1)%n,cur++) {
if(cur>n) cur-=n;
if(gondolaSeq[i]>n) {
change.pb({gondolaSeq[i],cur});
}
}
sort(change.begin(),change.end());
int sz=0;
int val=n;
for(int i=0;i<sz(change);i++) {
auto x=change[i];
replacementSeq[sz++]=x.nd;
val++;
while(val<x.st) {
replacementSeq[sz++]=val++;
}
}
return sz;
}
#define MOD 1000000009
//----------------------
int fe(int x,int y) {
if(y==0) return 1;
if(y==1) return x;
int res=fe(x,y/2);
res=1ll*res*res%MOD;
if(y&1) return 1ll*res*x%MOD;
return res;
}
int countReplacement(int n, int inputSeq[]) {
int isvalid=valid(n,inputSeq);
vector<int> ranges;
if(!isvalid) return 0;
for(int i=0;i<n;i++) {
if(inputSeq[i]<=n) continue ;
ranges.pb(inputSeq[i]);
}
int ans=(sz(ranges)==n?n:1);
ranges.pb(n);
sort(ranges.begin(),ranges.end());
int cursz=sz(ranges)-1;
for(int i=1;i<sz(ranges);i++,cursz--) {
int range=ranges[i]-ranges[i-1]-1;
ans=1ll*ans*fe(cursz,range)%MOD;
}
return ans;
}
Compilation message (stderr)
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:94:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<sz(change);i++) {
^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:147:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
int ans=(sz(ranges)==n?n:1);
^
gondola.cpp:155:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<sz(ranges);i++,cursz--) {
^
# | 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... |