| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 593046 | Tekor | The Big Prize (IOI17_prize) | 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>
using namespace std;
#define pii pair <int,int>
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define en '\n'
#define all(v) v.begin(),v.end()
const int N = 2e5 + 10;
int k,mx,kol;
vector <int> was[N];
bool u[N];
vector <pii> q;
int t[N * 4],t1[N * 4];
void build(int v,int tl,int tr) {
if(tl == tr) {
t[v] = 1;
t1[v] = 0;
return;
}
int tm = (tl + tr) / 2;
build(v + v,tl,tm);
build(v + v + 1,tm + 1,tr);
t[v] = t[v + v] + t[v + v + 1];
}
int get(int v,int tl,int tr,int x) {
if(tl == tr)return tl;
int tm = (tl + tr) / 2;
if(t[v + v] >= x)return get(v + v,tl,tm,x);
else return get(v + v + 1,tm + 1,tr,x - t[v + v]);
}
void upd(int v,int tl,int tr,int pos) {
if(tl == tr) {
t[v] = 0;
t1[v] = 1;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm)upd(v + v,tl,tm,pos);
else upd(v + v + 1,tm + 1,tr,pos);
t[v] = t[v + v] + t[v + v + 1];
t1[v] = t1[v + v] + t1[v + v + 1];
}
int get1(int v,int tl,int tr,int l,int r) {
if(tl > r || tr < l)return 0;
if(tl >= l && tr <= r)return t1[v];
int tm = (tl + tr) / 2;
return get1(v + v,tl,tm,l,r) + get1(v + v + 1,tm + 1,tr,l,r);
}
/*
8
3 2 3 1 3 3 2 3
*/
vector <int> Ask(int x) {
if(u[x])return was[x];
u[x] = 1;
kol++;
assert(kol <= 10000);
was[x] = ask(x);
return was[x];
}
int find_best(int pp) {
k = pp;
int m = (k - 1) / 2;
for(int i = 0;i < min(k,453);i++) {
kol++;
vector <int> res = Ask(i);
if(res[0] + res[1] == 0)return i;
mx = max(mx,res[0] + res[1]);
}
build(1,0,k - 1);
while(1) {
int l = 0,r = k - 1 - (int)q.size();
while(l <= r) {
int mid = (l + r) / 2;
int zap = get(1,0,k - 1,mid + 1);
vector <int> res = Ask(zap);
int sum = res[0] + res[1];
if(sum == 0)return zap;
if(sum != mx) {
q.pb(mp(zap,sum));
upd(1,0,k - 1,zap);
break;
}
res[0] -= get1(1,0,k - 1,0,zap - 1);
if(res[0] != 0) {
r = mid - 1;
}else {
l = mid + 1;
}
}
}
}