#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; random_device rd; mt19937_64 gen(rd()); ll query(ll x, ll y, vector<ll> v){ if(x > y) swap(x, y); // cout << x << ' ' << y << '\n'; // cout << " --> "; // for(auto it : v) cout << it << ' '; // cout << endl; 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); // cout << x << ' ' << y << endl; Answer(x, y); } void f(vector<ll> v){ // cout << " ------> "; // for(auto it : v) cout << it << ' '; // cout << endl; ll sz = v.size(); if(sz == 1) return; if(sz == 2){ ans(v[0], v[1]); return; } vector<bool> vis(n, false); uniform_int_distribution<ll> dis(0, sz - 1); ll at = v[dis(gen)],sz1 = 0; vector<vector<ll>> v1; for(auto it : v){ if(it == at) continue; if(query(at, it, {at, it})){ ans(at, it); v1.pb({it}); vis[it] = true; sz1++; } } for(auto it : v){ if(it == at or vis[it]) continue; ll l = -1,r = sz1 - 1; while(r > l + 1){ vector<ll> vv; for(auto i : v) if(!vis[i]) vv.pb(i); ll mid = l + (r - l) / 2; for(int i = 0; i <= mid; i++) vv.pb(v1[i][0]); if(query(it, at, vv)) r = mid; else l = mid; } v1[r].pb(it); } // cout << " --> " << sz1 << endl; 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); return; }