Submission #411974

#TimeUsernameProblemLanguageResultExecution timeMemory
411974losmi247Gondola (IOI14_gondola)C++14
55 / 100
26 ms2400 KiB
#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; } bool svi = 1; for(int i = 1; i <= n; i++){ if(a[i] <= n) svi = 0; } if(svi){ for(int i = 1; i <= n; i++){ treba[i] = i; } } 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:106:1: warning: no return statement in function returning non-void [-Wreturn-type]
  106 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...