| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 249607 | kostia244 | The Big Prize (IOI17_prize) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using vi = vector<int>;
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 {};
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;
p = findgood(p, 0, cg , 0);
if(p.size() < 35) {
for(auto i : p) {
std::vector<int> res = ask(i);
if(res[0] + res[1] == 0)
return i;
}
} else return solve(p);
}
int find_best(int n) {
for(int i = 0; i < min((int)p.size(), 500); i++) {
vi t = ask(i);
cb = min(cb, (int)p.size() - t[0] - t[1]);
}
cg = p.size() - cb;
vi t;
for(int i = 0; i < n; i++) t.push_back(i);
return solve(t);
}