#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;
mt19937 rng(time(0));
vector<int> f[1005];
set<pair<int, int>> S;
pair<int, int> getind(int ind)
{
for(auto i : S)
{
ind--;
if(ind == 0)
return i;
}
assert(0);
}
int ask(int m, int x, int n)
{
vector<int> v(n);
v[x - 1] = 1;
for(auto i : S)
{
m--;
for(auto j : f[i.first])
v[j - 1] = 1;
if(m == 0)
break;
}
return Query(v);
}
bool fask(int a, int b, int n)
{
vector<int> v(n);
v[a - 1] = 1;
v[b - 1] = 1;
return (Query(v) == 1);
}
void add(int ind, int x, int n)
{
pair<int, int> p = getind(ind);
S.erase(p);
if(fask(p.second, x, n))
{
f[p.first].push_back(x);
p.second = x;
}
else
{
f[x].push_back(x);
for(auto i : f[p.first])
f[x].push_back(i);
f[p.first].clear();
p.first = x;
}
// cout << p.first << ' ' << p.second << ' ' << x << '\n';
// exit(0);
S.insert(p);
}
void Solve(int N)
{
for(int i = 0; i <= N; i++)
f[i].clear();
S.clear();
vector<int> vec;
for(int i = 1; i <= N; i++)
vec.push_back(i);
// shuffle(vec.begin(), vec.end(), rng);
for(auto x : vec)
{
if(ask(S.size(), x, N) == S.size() + 1)
{
f[x].push_back(x);
S.insert({x, x});
}
else if(ask(S.size(), x, N) == S.size())
{
int l = 0, r = S.size();
while(r - l > 1)
{
int m = (l + r) / 2;
if(ask(m, x, N) == m)
r = m;
else
l = m;
}
add(r, x, N);
}
else if(ask(S.size(), x, N) == S.size() - 1)
{
int l = 0, r = S.size();
while(r - l > 1)
{
int m = (l + r) / 2;
if(ask(m, x, N) == m - 1)
r = m;
else
l = m;
}
int i2 = r;
l = 0, r--;
while(r - l > 1)
{
int m = (l + r) / 2;
if(ask(m, x, N) == m)
r = m;
else
l = m;
}
int i1 = r;
pair<int, int> p1 = getind(i1);
pair<int, int> p2 = getind(i2);
S.erase(p1);
S.erase(p2);
if(fask(x, p1.first, N))
{
f[p1.first].swap(f[p1.second]);
swap(p1.first, p1.second);
reverse(f[p1.first].begin(), f[p1.first].end());
}
if(fask(x, p2.second, N))
{
f[p2.first].swap(f[p2.second]);
swap(p2.first, p2.second);
reverse(f[p2.first].begin(), f[p2.first].end());
}
pair<int, int> p = {p1.first, p2.second};
f[p1.first].push_back(x);
for(auto i : f[p2.first])
f[p1.first].push_back(i);
f[p2.first].clear();
S.insert(p);
}
else
assert(0);
}
Answer(f[S.begin()->first]);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |