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 <bits/stdc++.h>
#include "gondola.h"
using namespace std;
typedef long long ll;
const int N = 1e5+34;
int n,a[N];
int pos[3*N],bio[3*N];
int treba[N];
int valid(int br,int *inputseq){
n = br;
for(int i = 1; i <= n; i++) a[i] = inputseq[i-1];
for(int i = 1; i <= n; i++){
if(a[i] <= n) pos[a[i]] = i;
if(bio[a[i]]) return 0;
bio[a[i]] = 1;
}
int lst = 0;
bool ok = 1;
for(int i = 1; i <= n; i++){
if(!pos[i]) continue;
if(!lst){
lst = i;
continue;
}
if(pos[lst] < pos[i]){
if(pos[i]-pos[lst] != i-lst){
ok = 0;
break;
}
}
else{
if(pos[lst]-pos[i]-1 != lst-1+n-i){
ok = 0;
break;
}
}
lst = i;
}
return ok;
}
int replacement(int br,int *gondolaSeq,int *replacementSeq){
n = br;
for(int i = 1; i <= n; i++) a[i] = gondolaSeq[i-1];
for(int i = 1; i <= n; i++){
if(a[i] <= n){
treba[i] = a[i];
}
else if(i > 1){
if(treba[i-1] == n) treba[i] = 1;
else if(treba[i-1]) treba[i] = treba[i-1]+1;
}
}
for(int i = n; i >= 1; i--){
if(treba[i]) continue;
if(treba[i+1] == 1) treba[i] = n;
else treba[i] = treba[i+1]-1;
}
for(int i = 1; i <= n; i++){
assert(1 <= treba[i] && treba[i] <= n);
}
vector <pair<int,int>> v;
for(int i = 1; i <= n; i++){
if(treba[i] != a[i]) v.push_back({a[i],treba[i]});
}
sort(v.begin(),v.end());
/*cout << v.size() << " evo" << endl;
for(auto f : v){
cout << f.first << " " << f.second << endl;
}
cout << endl;*/
int cnt = 0,stigo = n;
for(auto f : v){
for(int j = stigo; j < f.first; j++) replacementSeq[cnt++] = (j == stigo ? f.second : j);
stigo = f.first;
}
return cnt;
}
int countReplacement(int br,int *inputSeq){
}
/*int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int a;
cin >> a;
int *niz = (int*)malloc(sizeof(int)*a);
for(int i = 0; i < a; i++) cin >> niz[i];
cout << valid(a,niz) << endl;
int a;
cin >> a;
int *niz = (int*)malloc(sizeof(int)*a);
for(int i = 0; i < a; i++) cin >> niz[i];
int *drugi = (int*)malloc(sizeof(int)*200);
int len = replacement(a,niz,drugi);
cout << len << endl;
for(int i = 0; i < len; i++){
cout << drugi[i] << " ";
}
cout << endl;
}*/
Compilation message (stderr)
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:94:1: warning: no return statement in function returning non-void [-Wreturn-type]
94 | }
| ^
# | 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... |