| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 948814 | phoenix0423 | ICC (CEOI16_icc) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
#include "icc.h"
const int maxn = 105;
int n;
int par[maxn];
int root(int x){ return x == par[x] ? x : par[x] = root(par[x]);}
vector<int> comp[maxn];
// bool query(int sa, int sb, vector<int> a, vector<int> b){
// for(auto x : a) cout<<x<<" ";
// cout<<" | ";
// for(auto x : b) cout<<x<<" ";
// cout<<"\n";
// int x;
// cin>>x;
// return x;
// }
// void setRoad(int a, int b){
// cout<<"set : "<<a<<" "<<b<<"\n";
// }
void run(int _n){
n = _n;
for(int i = 1; i <= n; i++) comp[i].pb(i), par[i] = i;
random_device rd;
mt19937 rng(rd());
for(int rd = 0; rd < n - 1; rd++){
set<int> st;
for(int i = 1; i <= n; i++) st.insert(root(i));
vector<vector<int>> s(2);
bool c = false;
while(!c){
s[0].clear(), s[1].clear();
for(auto x : st){
int cur = rng() % 2;
for(auto u : comp[x]) s[cur].pb(u);
}
c = query(s[0].size(), s[1].size(), s[0], s[1]);
}
int l = 0, r = s[0].size() - 1;
while(l != r){
int m = (l + r) / 2;
vector<int> ns;
for(int i = l; i <= m; i++) ns.pb(s[0][i]);
c = query(ns.size(), s[1].size(), ns, s[1]);
if(c) r = m;
else l = m + 1;
}
vector<int> tmp(1, s[0][l]);
swap(s[0], tmp);
l = 0, r = s[1].size() - 1;
while(l != r){
int m = (l + r) / 2;
vector<int> ns;
for(int i = l; i <= m; i++) ns.pb(s[1][i]);
c = query(1, ns.size(), s[0], ns);
if(c) r = m;
else l = m + 1;
}
setRoad(s[0][0], s[1][l]);
int a = root(s[0][0]), b = root(s[1][l]);
par[a] = b;
for(auto x : comp[a]) comp[b].pb(x);
}
}