# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
72626 | 2018-08-26T12:39:25 Z | mhnd | The Big Prize (IOI17_prize) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 2e5+50; const int oo = 1e9; const int mod = 1e9+7; int dsu[N]; vector<int> a; int find(int u){ return u==dsu[u]?u:dsu[u] = find(dsu[u]); } int find_best(int n){ int cur = 0; set<int> st; for(int i=0;i<n;i++){ dsu[i]=i; st.insert(i); } for(int i=0;i<5000;i++){ a = ask(cur); if(!a[0] && !a[1])return cur; if(a[0] > a[1]){ int md = cur/2; md = find(md); st.erase(md); auto it = st.lower_bound(md); if(it != st.begin())it--; dsu[md] = *it; cur = md; }else{ int md = (n+cur-1)/2; md = find(md); st.erase(md); auto it = st.lower_bound(md); if(it != st.begin())it--; dsu[md] = *it; cur = md; } } return 0; }