#include "park.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define ff first #define sd second const int mxN = 1500; ll n,cc; random_device rd; mt19937_64 gen(rd()); bool vis1[mxN][mxN]; ll query(ll x, ll y, vector<ll> v){ if(x > y) swap(x, y); int place[n]; for(int i = 0; i < n; i++) place[i] = 0; for(auto it : v) place[it] = 1; return Ask(x, y, place); } void ans(ll x, ll y){ if(x > y) swap(x, y); cc++; assert(cc > 45000); vis1[x][y] = true; Answer(x, y); } void f(vector<ll> v){ ll sz = v.size(); if(sz == 1) return; if(sz == 2){ ans(v[0], v[1]); return; } uniform_int_distribution<ll> dis(0, sz - 1); ll at = v[dis(gen)],sz1 = 0; vector<bool> vis(n, false); vector<vector<ll>> v1; for(auto it : v){ if(it == at) continue; if(query(it, at, {it, at})){ sz1++; ans(it, at); v1.pb({it}); vis[it] = true; } } vector<ll> vv; for(auto it : v) if(it != at) vv.pb(it); for(auto it : v){ if(it == at or vis[it]) continue; for(int i = 0; i < sz1; i++){ if(query(v1[i][0], it, vv)){ v1[i].pb(it); break; } } } for(int i = 0; i < sz1; i++) f(v1[i]); } void Detect(int T, int N) { n = N; vector<ll> v; for(int i = 0; i < n; i++) v.pb(i); f(v); cout << cc << endl; return; }