Submission #1241177

#TimeUsernameProblemLanguageResultExecution timeMemory
1241177MarwenElarbiSphinx's Riddle (IOI24_sphinx)C++20
36 / 100
34 ms436 KiB
#include <bits/stdc++.h> #include "sphinx.h" using namespace std; #define fi first #define se second #define pb push_back const int nax = 5e5+5; vector<int> mark(int N,int color,int l,int r){ vector<int> ans(N,color); for (int i = l; i <= r; ++i) { if((i-l)%2) ans[i]=color; else ans[i]=-1; } return ans; } std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) { vector<int> p, imp; for (int i = 0; i < N; ++i) (i%2 ? imp : p).push_back(i); vector<int> ans(N); for (int i = 0; i < N; ++i) { int lst=-1; while(true){ if(lst>p.back()) break; int cur = lower_bound(p.begin(),p.end(),lst)-p.begin(); int x = perform_experiment(mark(N,i,p[cur],N-1)); if(x-(p[cur]>0)==N-1-p[cur]+1) break; int r=p.size(); int l=cur-1; while(r-l>1){ int mid=(r+l)/2; if(perform_experiment(mark(N,i,p[cur],p[mid]))-(p[cur]>0)-(p[mid]<N-1)==p[mid]-p[cur]+1) l=mid; else r=mid; } ans[p[r]]=i; lst=p[r]+1; } } for (int i = 0; i < N; ++i) { int lst=-1; while(true){ if(lst>imp.back()) break; int cur = lower_bound(imp.begin(),imp.end(),lst)-imp.begin(); int x = perform_experiment(mark(N,i,imp[cur],N-1)); if(x-1==N-1-imp[cur]+1) break; int r=imp.size(); int l=cur-1; while(r-l>1){ int mid=(r+l)/2; if(perform_experiment(mark(N,i,imp[cur],imp[mid]))-1-(imp[mid]<N-1)==imp[mid]-imp[cur]+1) l=mid; else r=mid; } ans[imp[r]]=i; lst=imp[r]+1; } } return ans; }
#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...