Submission #1017718

#TimeUsernameProblemLanguageResultExecution timeMemory
1017718serkanrashidGondola (IOI14_gondola)C++14
55 / 100
18 ms5808 KiB
#include "gondola.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+5; int n,a[maxn]; bool check_valid() { unordered_set<int>used; int st = -1; for(int i = 0; i < n; i++) { if(used.find(a[i])!=used.end()) return false; used.insert(a[i]); if(1<=a[i] && a[i] <= n) st = i; } if(st==-1) return true; int last = a[st]; int i = (st+1)%n; while(i!=st) { last++; if(last>n) last = 1; if(1<=a[i] && a[i]<=n) { if(last!=a[i]) return false; } i = (i+1)%n; } return true; } int valid(int N, int inputSeq[]) { n = N; for(int i = 0; i < n; i++) a[i] = inputSeq[i]; return check_valid(); } int need[maxn]; void make_need() { int st = -1; for(int i = 0; i < n; i++) if(1 <= a[i] && a[i] <= n) st = i; if(st==-1) { for(int i = 0; i < n; i++) need[i] = i+1; return; } int last = a[st]; int i = (st+1)%n; while(i!=st) { last++; if(last>n) last = 1; need[i] = last; i = (i+1)%n; } } vector<int> do_replace() { int l = 0; for(int i = 0; i < n; i++) if(a[i]>l) l = a[i]; l = l - n; vector<pair<int,int> >pos; for(int i = 0; i < n; i++) if(a[i]>n) pos.push_back({a[i],need[i]}); sort(pos.begin(),pos.end()); vector<int>res; int last = n; for(pair<int,int> nb : pos) { res.push_back(nb.second); for(int j = last+1; j < nb.first; j++) res.push_back(j); last = nb.first; } return res; } int replacement(int N, int gondolaSeq[], int replacementSeq[]) { n = N; for(int i = 0; i < n; i++) a[i] = gondolaSeq[i]; make_need(); vector<int>pom = do_replace(); for(int i = 0; i < pom.size(); i++) replacementSeq[i] = pom[i]; return pom.size(); } int countReplacement(int N, int inputSeq[]) { n = N; for(int i = 0; i < n; i++) a[i] = inputSeq[i]; if(!check_valid()) return 0; ///OSHTE }

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i = 0; i < pom.size(); i++) replacementSeq[i] = pom[i];
      |                    ~~^~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:109:1: warning: control reaches end of non-void function [-Wreturn-type]
  109 | }
      | ^
#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...