| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 817110 | anton | 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 pii pair<int, int>
const int MAX_N = 1e2;
int n;
vector<int> groups[MAX_N+1];
int dsu[MAX_N+1];
int my_query(int sa, int sb, int a[], int b[]){
for(int i = 0; i<sa; i++){
//cout<<a[i]<<" ";
}
//cout<<endl<<"__"<<endl;
for(int i = 0; i<sb; i++){
//cout<<b[i]<<" ";
}
//cout<<endl;
int res;
//cin>>res;
res = query(sa, sb, a, b);
return res;
}
void merge(int a, int b){
int ga = dsu[a];
int gb = dsu[b];
if(ga==gb){
return;
}
if(ga>gb){
swap(ga, gb);
}
for(auto e: groups[gb]){
groups[ga].push_back(e);
dsu[e] = ga;
}
groups[gb].clear();
}
void my_setRoad(int a, int b){
merge(a, b);
setRoad(a, b);
//cout<<"road "<<a<<" "<<b<<endl;
}
void pbv(vector<int>& a, vector<int>&b){
a.insert(a.end(), b.begin(), b.end());
}
vector<int> all_except(int id){
vector<int> b;
for(int i = 0; i<n; i++){
if(i!=id){
pbv(b, groups[i]);
}
}
return b;
}
int query_group(int id){
vector<int> a;
pbv(a, groups[id]);
vector<int> b = all_except(id);
return my_query(a.size(), b.size(),&a[0], &b[0]);
}
void find(vector<int>& a, vector<int>& b){
int aid = -1;
for(int step = (1<<7); step>=1; step/=2){
if(aid+step<a.size()){
if(aid+step==0){
aid+=step;
continue;
}
////cout<<"qa"<<endl;
if(my_query(a.size()-aid-step, b.size(), &a[aid+step], &b[0])){
aid+=step;
}
}
}
int bid= -1;
for(int step = (1<<7); step>=1; step/=2){
if(bid+step<b.size()){
if(bid+step==0){
bid+=step;
continue;
}
if(my_query(1, b.size()-bid-step, &a[aid], &b[bid+step])){
bid+=step;
}
}
}
////cout<<aid<<" "<<bid<<endl;
my_setRoad(a[aid], b[bid]);
}
pair<vector<int>, vector<int>> get_split(){
pair<vector<int>, vector<int>> pv;
vector<int> gs;
for(int i = 0; i<n; i++){
if(groups[i].size()>0){
gs.push_back(i);
}
}
random_shuffle(gs.begin(), gs.end());
for(int i= 0; i<gs.size()/2; i++){
pbv(pv.first, groups[gs[i]]);
}
for(int i= gs.size()/2; i<gs.size(); i++){
pbv(pv.second, groups[gs[i]]);
}
if(pv.first.size()>0&& pv.second.size()>0){
return pv;
}
else{
return get_split();
}
}
signed main(){
cin>>n;
srand(42);
for(int i = 0; i<n; i++){
dsu[i+1] = i;
groups[i].push_back(i+1);
}
for(int i = 0; i<n-1; i++){
/*for(int i = 0; i<n; i++){
if(groups[i].size()>0){
if(query_group(i)==1){
auto tmp = all_except(i);
find(groups[i], tmp);
}
}
}*/
auto pvv = get_split();
//cout<<"ok"<<endl;
while(!my_query(pvv.first.size(), pvv.second.size(), &pvv.first[0], &pvv.second[0])){
pvv = get_split();
}
find(pvv.first, pvv.second);
}
}