| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 249590 | kostia244 | Ancient Books (IOI17_books) | C++17 | 0 ms | 0 KiB |
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 "prize.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using vi = vector<int>;
map<int, vector<int>> memo;
vector<int> fffff(int p) {
if(memo.count(p)) return memo[p];
return memo[p] = ask(p);
}
#define ask fffff
int cb = 1<<30, cg;
vector<int> cnt(20, 0);
vi findgood(vi vals, int cl, int cc, int cr, int _Dep = 0) {
if(vals.empty() || !cc) return {};
if(vals.size() == cc) return vals;
int l = vals.size()/2;
int r = l+1, go = -1;
cnt[_Dep]++;
//for(auto i : vals) cout << i << " "; cout << cl << " " << cc << " " << cr << "::" << endl;
vi gg, t;
while(l >= 0 || r < vals.size()) {
if(l >= 0) {
t = ask(vals[l]);
if(t[0] + t[1] == cg) {
go = l;
break;
}
gg.push_back(vals[l--]);
}
if(r < vals.size()) {
t = ask(vals[r]);
if(t[0] + t[1] == cg) {
go = r;
break;
}
gg.push_back(vals[r++]);
}
}
if(l < 0 && r >= vals.size()) return gg;
vi vl, vr;
for(int i = 0; i < vals.size(); i++) {
if(i == go) continue;
if(i <= l) vl.push_back(vals[i]);
if(i >= r) vr.push_back(vals[i]);
}
t[0] -= cl;
t[1] -= cr;
//cout << vals.size() << " to " << vl.size() << " + " << vr.size() << " " << _Dep << " " << cl << " / " << cc << " / " << cr << endl;
//cout << cl << " " << cc << " " << cr << " " << gg.size()+vl.size()+vr.size() << " " << vals.size() << endl;
for(auto &i : findgood(vl, cl, t[0], cr+t[1], _Dep+1)) gg.push_back(i);
for(auto &i : findgood(vr, cl+t[0], t[1], cr, _Dep+1)) gg.push_back(i);
return gg;
}
int solve(vector<int> p) {
vi g, pg;
int i = 0;
while(i < p.size()) {
vi t = ask(p[i]);
cb = min(cb, (int)p.size() - t[0] - t[1]);
if(p.size() >= 500) {
int t = sqrt(p.size());
if(cb > t) break;
}
i++;
}
cg = p.size() - cb;
if(p.size() > 1000) {
p = findgood(p, 0, cg , 0);
}
//for(auto i : p) cout << i << " is good.\n";
//for(auto i : cnt) cout << i << " ";cout << endl;
for(auto i : p) {
std::vector<int> res = ask(i);
if(res[0] + res[1] == 0)
return i;
}
}
int find_best(int n) {
vi t;
for(int i = 0; i < n; i++) t.push_back(i);
return solve(t);
}