#include "meetings.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int get(int l, int r)
{
return l+mt()*mt()%(r-l+1);
}
// void Bridge(int u, int v)
// {
// cout<<"haha"<<u<<' '<<v<<'\n';
// }
// int Query(int u, int v, int w)
// {
// cout<<u<<' '<<v<<' '<<w<<'\n';
// int x;
// cin>>x;
// return x;
// }
int st, en;
bool cmp(int a, int b)
{
if(a==st) return 1;
if(a==en) return 0;
if(b==st) return 0;
if(b==en) return 1;
return Query(st, a, b)==a;
}
void dfs(int u, vector<int> ver)
{
if(ver.size()==1) return;
if(ver.size()==2)
{
if(ver[0]>ver[1]) swap(ver[0], ver[1]);
Bridge(ver[0], ver[1]);
return;
}
shuffle(ver.begin(), ver.end(), mt);
map<int, vector<int>> mp;
mp.clear();
int v=u;
while(v==u)
{
int pos=get(0, ver.size()-1);
v=ver[pos];
}
mp[u].emplace_back(u);
mp[v].emplace_back(v);
for(int x:ver)
{
if(x==u || x==v) continue;
int nw=Query(u, v, x);
mp[nw].emplace_back(x);
}
vector<int> path;
path.clear();
for(auto it:mp)
{
path.emplace_back(it.fi);
dfs(it.fi, it.se);
}
st=u, en=v;
sort(path.begin(), path.end(), cmp);
for(int i = 1; i < path.size(); i++)
Bridge(min(path[i-1], path[i]), max(path[i-1], path[i]));
}
void Solve(int n)
{
vector<int> tmp;
tmp.clear();
for(int i = 0; i < n; i++)
tmp.emplace_back(i);
shuffle(tmp.begin(), tmp.end(), mt);
dfs(tmp[0], tmp);
}
// int main()
// {
// Solve(5);
// }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |