#include "insects.h" #include <bits/stdc++.h> using std::cin; using std::cout; using std::endl; using std::vector; using std::string; using ll = long long; using vi = vector<ll>; using vii = vector<vi>; using pii = std::pair<ll,ll>; constexpr ll mod = 1'000'002'022; #define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++) #define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++) #define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--) #define all(a) a.begin(),a.end() #define pb emplace_back #define ln "\n" struct union_find{ int N; vi par; union_find(int n): N(n){ par.resize(N); rep(i,0,N) par[i] = i; } ll root(ll u){ if(par[u] == u) return u; return par[u] = root(par[u]); } void merge(ll u, ll v){ u = root(u); v = root(v); if(u != v){ par[u] = v; } } }; int min_cardinality(int N) { union_find tree(N); std::function<vi(ll,ll)> dfs = [&](ll l, ll r){ if(l+1 == r){ vi ret = {l}; return ret; } ll m = (l+r)/2; vi L = dfs(l,m), R = dfs(m,r); if(L.size() > R.size()) std::swap(L,R); ll sz = R.size(); vi left(sz), right(sz, L.size()+1); while(true){ vi mid(sz,-1); vii query(L.size()+1); bool flag = false; rep(i,0,sz){ if(left[i]+1 == right[i]) continue; mid[i] = (left[i]+right[i])/2; assert(1 <= mid[i] && mid[i] <= L.size()); query[mid[i]].pb(i); flag = true; } if(!flag) break; rep(i,0,L.size()){ move_inside(L[i]); for(auto el: query[i+1]){ move_inside(R[el]); ll val = press_button(); if(val == 2) right[el] = i+1; else if(val == 1) left[el] = i+1; else assert(false); move_outside(R[el]); } } rep(i,0,L.size()){ move_outside(L[i]); } } std::set<ll> nex; for(auto el: L) nex.insert(el); for(auto el: R) nex.insert(el); rep(i,0,sz){ if(left[i] < L.size()){ tree.merge(L[left[i]], R[i]); nex.erase(R[i]); } } vi ret(all(nex)); /*cout << l << " " << r << " "; for(auto el: L) cout << el << " "; cout << " "; for(auto el: R) cout << el << " "; cout << " "; rep(i,0,sz) cout << left[i] << " "; cout << " "; for(auto el: ret) cout << el << " "; cout << endl;*/ return ret; }; dfs(0,N); vi cnt(N); //rep(i,0,N) cout << tree.root(i) << endl; rep(i,0,N) cnt[tree.root(i)]++; ll min = N; rep(i,0,N){ if(cnt[i]) min = std::min(min, cnt[i]); } return int(min); }

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from insects.cpp:3:
insects.cpp: In lambda function:
insects.cpp:63:38: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         assert(1 <= mid[i] && mid[i] <= L.size());
insects.cpp:87:18: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |       if(left[i] < L.size()){