| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 96836 | Kastanda | ICC (CEOI16_icc) | C++11 | 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.
// I do it for the glory
#include<bits/stdc++.h>
#include "icc.h"
#define pb push_back
using namespace std;
mt19937 Rnd(time(0));
int fe, se, qq;
bool Rand()
{
return (Rnd() & 1);
}
void GoForIt(vector < int > L, vector < int > R)
{
while (L.size() > 1)
{
vector < int > L1, L2;
for (int i = 0; i < (int)L.size(); i++)
{
if (i < (L.size() >> 1))
L1.pb(L[i]);
else
L2.pb(L[i]);
}
qq ++;
bool w = query(L1.size(), R.size, L1.data(), R.data());
if (w) L = L1;
else L = L2;
}
while (R.size() > 1)
{
vector < int > R1, R2;
for (int i = 0; i < (int)R.size(); i++)
{
if (i < (R.size() >> 1))
R1.pb(R[i]);
else
R2.pb(R[i]);
}
qq ++;
bool w = query(L.size(), R1.size, L.data(), R1.data());
if (w) R = R1;
else R = R2;
}
fe = L[0];
se = R[0];
return ;
}
void run(int N)
{
int P[N + 1];
vector < int > A[N + 1];
for (int i = 1; i <= N; i++)
A[i].pb(i), P[i] = i;
for (int q = 1; q <= N - 1; q ++)
{
bool done = 0;
vector < int > L, R;
while (!done)
{
L.clear(); R.clear();
for (int i = 1; i <= N; i++)
{
bool w = Rand();
for (int v : A[i])
{
if (w) L.pb(v);
else R.pb(v);
}
}
if (!L.size() || !R.size())
continue; // What are the odds of that ?
done = query(L.size(), R.size(), L.data(), R.data());
}
qq = 0;
GoForIt(L, R);
if (qq > 12) assert(0);
setRoad(fe, se);
int v = fe, u = se, pu = P[u];
for (int w : A[pu])
P[w] = P[v], A[P[v]].pb(w);
A[pu].clear();
}
return ;
}