| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 940453 | parlimoos | ICC (CEOI16_icc) | C++14 | 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.
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
// #include "icc.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
int n;
int dsu[101];
vector<int> cs;
vector<arr(2)> sgs[10];
vector<int> dsuset[101];
int query(int sza , int szb , int a[] , int b[]){
cout << "Query :\n";
for(int i = 0 ; i < sza ; i++) cout << a[i] << " ";
cout << endl;
for(int i = 0 ; i < szb ; i++) cout << b[i] << " ";
cout << endl;
int res;
cin >> res;
return res;
}
int setRoad(int a , int b){
cout << "Set : " << a << " " << b << "|\n";
int res;
cin >> res;
return res;
}
void init(){
fill(&dsu[0] , &dsu[n + 1] , -1);
for(int i = 1 ; i <= n ; i++) cs.pb(i) , dsuset[i].pb(i);
}
int findDsu(int v){
if(dsu[v] == -1) return v;
return (dsu[v] = findDsu(dsu[v]));
}
void uDsu(int a , int b){
a = findDsu(a) , b = findDsu(b);
if((int)dsuset[a].size() < (int)dsuset[b].size()) swap(a , b);
int inx = int(lb(cs.bg() , cs.end() , b) - cs.bg());
for(int i = inx ; i < (int)cs.size() - 1 ; i++) cs[i + 1] = cs[i];
cs.pp();
dsu[b] = a;
for(int v : dsuset[b]) dsuset[a].pb(v);
}
int getSet(){
int sz[2];
for(int i = 0 ; i < 10 ; i++){
sz[0] = 0 , sz[1] = 0;
for(int sg = 0 ; sg < (int)sgs[i].size() ; sg++){
for(int v = sgs[i][sg][0] ; v <= sgs[i][sg][1] ; v++){
sz[(sg & 1)] += (int)dsuset[cs[v]].size();
}
}
int a[sz[0]] , b[sz[1]];
int cnt1 = 0 , cnt2 = 0;
for(int sg = 0 ; sg < (int)sgs[i].size() ; sg++){
for(int v = sgs[i][sg][0] ; v <= sgs[i][sg][1] ; v++){
for(int u : dsuset[cs[v]]){
if((sg & 1)) b[cnt2++] = u;
else a[cnt1++] = u;
}
}
}
while(sz[0] != cnt1 or sz[1] != cnt2);
int d = query(sz[0] , sz[1] , a , b);
if(d == 1) return i;
}
cout << "Ay Kheda!\n";
}
arr(2) f(){
for(int i = 0 ; i < 10 ; i++) sgs[i].cl();
int c = (((int)cs.size() - 2) >> 1);
sgs[0].pb({0 , c}) , sgs[0].pb({c + 1 , (int)cs.size() - 1});
for(int i = 0 ; i < 9 ; i++){
for(auto sg : sgs[i]){
if(sg[0] == sg[1]) sgs[i + 1].pb({sg[0] , sg[1]});
else{
c = (sg[0] + sg[1] - 1) >> 1;
sgs[i + 1].pb({sg[0] , c}) , sgs[i + 1].pb({c + 1 , sg[1]});
}
}
}
int inx = getSet();
vector<int> a , b;
for(int sg = 0 ; sg < (int)sgs[inx].size() ; sg++){
for(int v = sgs[inx][sg][0] ; v <= sgs[inx][sg][1] ; v++){
for(int u : dsuset[cs[v]]){
if((sg & 1)) b.pb(u);
else a.pb(u);
}
}
}
int l = 0 , r = (int)a.size() - 1;
while(r > l){
int c = (l + r - 1) >> 1;
int sz[2] = {c - l + 1 , (int)b.size()};
int aa[sz[0]] , bb[sz[1]];
for(int i = 0 ; i < sz[1] ; i++) bb[i] = b[i];
for(int i = 0 ; i < sz[0] ; i++) aa[i] = a[l + i];
int d = query(sz[0] , sz[1] , aa , bb);
if(d == 1) r = c;
else l = c + 1;
}
int ans1 = l;
l = 0 , r = (int)b.size() - 1;
while(r > l){
int c = (l + r - 1) >> 1;
int sz[2] = {1 , c - l + 1};
int aa[sz[0]] , bb[sz[1]];
for(int i = 0 ; i < sz[1] ; i++) bb[i] = b[l + i];
aa[0] = a[ans1];
int d = query(sz[0] , sz[1] , aa , bb);
if(d == 1) r = c;
else l = c + 1;
}
return {a[ans1] , b[l]};
}
int main(){
cin >> n;
init();
for(int i = 1 ; i < n ; i++){
arr(2) d = f();
int dd = setRoad(d[0] , d[1]);
if(dd == 0){
cout << "-1\n" << flush;
break;
}
uDsu(d[0] , d[1]);
}
}