| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 707184 | minhcool | 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>
#include "icc.h"
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, rt[N], sz[N];
int root(int x){
return (x == rt[x] ? x : rt[x] = root(rt[x]));
}
int arr1[N], arr2[N];
/*
bool query(int a, int b, int c[], int d[]){
cout << a << " " << b << '\n';
for(int i = 0; i < a; i++) cout << c[i] << " ";
cout << "\n";
for(int i = 0; i < b; i++) cout << d[i] << " ";
cout << "\n";
int val;
cin >> val;
return val;
}*/
/*
void setRoad(int x, int y){
cout << "ADDING " << x << " " << y << '\n';
}*/
bool queryy(vector<int> a, vector<int> b){
if(!a.size() || !b.size()) return 0;
for(auto it : a) if(!it) return 0;
for(auto it : b) if(!it) return 0;
for(int i = 0; i < a.size(); i++) arr1[i] = a[i];
for(int i = 0; i < b.size(); i++) arr2[i] = b[i];
//cout << "OK\n";
return query(a.size(), b.size(), arr1, arr2);
}
void merge(int x, int y){
x = root(x), y = root(y);
assert(x != y);
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
rt[y] = x;
}
void solvee(vector<int> a, vector<int> b){// conected component
assert(a.size() && b.size());
for(auto it : a) assert(it);
for(auto it : b) assert(it);
int le = 0, ri = a.size() - 1;
while(le < ri){
int mid = (le + ri) >> 1;
vector<int> temp;
for(int i = 0; i <= mid; i++) temp.pb(a[i]);
if(!queryy(temp, b)) le = mid + 1;
else ri = mid;
}
//int val1 = a[le], tempo = (le >> indd) ^ 1;
int val1 = a[le];
le = 0, ri = b.size() - 1;
while(le < ri){
int mid = (le + ri) >> 1;
vector<int> temp;
for(int i = 0; i <= mid; i++) temp.pb(b[i]);
if(!queryy(a, temp)) le = mid + 1;
else ri = mid;
}
int val2 = b[le];
merge(val1, val2);
setRoad(val1, val2);
}
int ind[N];
mt19937 rng(7405);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
bool ck1[N], ck2[N];
void run(int N){
n = N;
for(int i = 1; i <= n; i++){
rt[i] = i;
sz[i] = 1;
}
int temp = n - 1;
while(temp--){
vector<int> v;
for(int i = 1; i <= n; i++) if(root(i) == i) v.pb(i);
for(int i = 0; i < v.size(); i++) ind[v[i]] = i;
vector<int> a, b;
int indd = 7;
for(int i = 6; i >= 0; i--){
//cout << i << "\n";
a.clear(), b.clear();
for(int j = 1; j <= n; j++){
if(ind[root(j)] & (1LL << i)) a.pb(j);
else b.pb(j);
}
if(queryy(a, b)){
//cout << "OKAY\n";
indd = i;
break;
}
}
a.clear(), b.clear();
for(int i = 0; i < v.size(); i++){
if(i & (1LL << indd)) a.pb(v[i]);
else b.pb(v[i]);
}
vector<int> c, d;
for(int i = 1; i <= n; i++){
bool ck = 0;
for(auto it : a) ck |= (root(i) == it);
if(ck) c.pb(i);
else d.pb(i);
}
/*
for(auto it : c){
for(auto it2 : d){
vector<int> x, y;
x.pb(it), y.pb(it2);
if(queryy(x, y)){
merge(it, it2);
setRoad(it, it2);
break;
}
}
}*/
/*
cout << "TEMP\n";
for(auto it : a) cout << it << " ";
cout << "\n";
for(auto it : b) cout << it << " ";
cout << "\n";*/
int le = 0, ri = a.size() - 1;// first position to be correct
while(le < ri){
int mid = (le + ri) >> 1;
vector<int> temp1, temp2;
for(int i = 1; i <= n; i++) ck1[i] = ck2[i] = 0;
for(int i = 0; i <= mid; i++) ck1[a[i]] = 1;
for(int i = 0; i < b.size(); i++) ck2[b[i]] = 1;
for(int i = 1; i <= n; i++){
if(ck1[root(i)]) temp1.pb(i);
if(ck2[root(i)]) temp2.pb(i);
}
//for(int i = 0; i <= mid; i++) temp.pb(a[i]);
if(!queryy(temp1, temp2)) le = mid + 1;
else ri = mid;
}
vector<int> c;
for(auto it : b){
int x = (it >> indd), y = (a[le] >> indd);
if(x == (y ^ 1)) c.pb(it);
}
//b = c;
//int val1 = a[le], tempo = (le >> indd) ^ 1;
int val1 = a[le];
le = 0, ri = b.size() - 1;
while(le < ri){
int mid = (le + ri) >> 1;
vector<int> temp1, temp2;
for(int i = 1; i <= n; i++) ck1[i] = ck2[i] = 0;
for(int i = 0; i <= mid; i++) ck2[b[i]] = 1;
for(int i = 0; i < a.size(); i++) ck1[a[i]] = 1;
for(int i = 1; i <= n; i++){
if(ck1[root(i)]) temp1.pb(i);
if(ck2[root(i)]) temp2.pb(i);
}
//for(int i = 0; i <= mid; i++) temp.pb(b[i]);
if(!queryy(temp1, temp2)) le = mid + 1;
else ri = mid;
}
int val2 = b[ri];
vector<int> v1, v2;
for(int i = 1; i <= n; i++){
if(root(i) == val1) v1.pb(i);
if(root(i) == val2) v2.pb(i);
}
//bool done = 0;
/*
for(auto it : v1){
if(done) break;
for(auto it2 : v2){
vector<int> x, y;
x.pb(it), y.pb(it2);
if(queryy(x, y)){
merge(it, it2);
setRoad(it, it2);
done = 1;
break;
}
}
}*/
assert(v1.size() && v2.size());
solvee(v1, v2);
//cout << "OKAY " << val1 << " " << val2 << "\n";
//solvee(v1, v2);*/
}
}
/*
void process(){
int n;
cin >> n;
run(n);
}
signed main(){
//ios_base::sync_with_stdio(0);
//cin.tie(0);
process();
}*/