#include <bits/stdc++.h> #include "grader.h" using namespace std; //#include "grader.cpp" mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define rnd(l, r) uniform_int_distribution<int> (l,r)(rng) void solve(int n){ vector<int> id(n); iota(id.begin(), id.end(), 1); map<int,int> mp; int ct = 0; while(ct < 60 && id.size()) { int c = id[rnd(0, id.size()-1)]; int cur = kth(c); mp[cur] ++ ; ct ++ ; if(mp[cur] > 1) { ct ++ ; if(cnt(cur) > n/3) { say_answer(cur); return; }; }; vector<int> ni; for(int &i : id) if(i != c) ni.push_back(i); swap(ni, id); }; say_answer(1); }