| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1028738 | parsadox2 | 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;
const int N = 2e5 + 10;
int n;
bool marked[N] , dead[N];
int Sq(int val)
{
for(int i = 1 ; i <= val ; i++) if(i * i >= val)
return i;
return -1;
}
void Solve()
{
vector <int> all;
for(int i = 0 ; i < n ; i++) if(!dead[i])
all.push_back(i);
int m = all.size() , sq = Sq(m);
if(m == 1)
return;
if(m < 500)
{
for(auto u : m)
{
auto now = ask(u);
if(now[0] + now[1] != 0)
dead[u] = true;
}
return;
}
int mx = 0;
for(int i = 0 ; i < sq ; i++)
{
auto now = ask(all[i]);
mx = max(mx , now[0] + now[1]);
}
for(auto u : all)
marked[u] = false;
for(int asd = 0 ; asd < mx ; asd++)
{
all.clear();
for(int i = 0 ; i < n ; i++) if(!dead[i] && !marked[i])
all.push_back(i);
m = all.size();
int low = -1 , high = m;
while(high - low > 1)
{
int mid = (low + high) >> 1;
int id = all[mid];
auto now = ask(id);
if(now[0] + now[1] != mx)
{
marked[id] = true;
break;
}
dead[id] = true;
for(int i = 0 ; i < id ; i++) if(!dead[i] && marked[i])
now[0]--;
if(now[0] == 0)
low = mid;
else
high = mid;
}
}
for(int i = 0 ; i < n ; i++) if(!marked[i])
dead[i] = true;
Solve();
}
int find_best(int nn) {
n = nn;
Solve();
for(int i = 0 ; i < n ; i++) if(!dead[i])
return i;
return -1;
}