#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
#ifndef JAKOB
#include"icc.h"
#else
int query(int size_a, int size_b, int a[], int b[]);
void setRoad(int a, int b);
#endif
bool query(vector<int>a,vector<int>b){
if(a.empty()||b.empty())
return false;
for(int&i:a)
i++;
for(int&i:b)
i++;
return query((int)a.size(),(int)b.size(),&a[0],&b[0])==1;
}
void set_road(int a,int b){
setRoad(a+1,b+1);
}
pair<int,int>get3(vector<int>s1,vector<int>s2){
if(s1.size()==1)
swap(s1,s2);
if(s1.size()==1)
return{s1[0],s2[0]};
int ss=(int)s1.size();
vector<int>a,b;
for(int i=0;i<ss/2;i++)
a.push_back(s1[i]);
for(int i=ss/2;i<ss;i++)
b.push_back(s1[i]);
if(query(a,s2))
return get3(a,s2);
else
return get3(b,s2);
}
pair<int,int>get1(vector<vector<vector<int>>>s){
while(true){
vector<vector<vector<int>>>s2;
for(auto&i:s){
if(i.size()==1)
continue;
int sz=(int)i.size();
s2.emplace_back();
for(int j=0;j<sz/2;j++)
s2.back().push_back(i[j]);
s2.emplace_back();
for(int j=sz/2;j<sz;j++)
s2.back().push_back(i[j]);
}
vector<int>a1,a2;
for(int i=0;i<(int)s2.size();i++){
for(auto&i1:s2[i]){
for(int i2:i1){
if(i%2)
a2.push_back(i2);
else
a1.push_back(i2);
}
}
}
if(query(a1,a2)){
return get3(a1,a2);
}
s=s2;
}
}
void run(int n){
vector<vector<int>>components;
for(int i=0;i<n;i++)
components.push_back({i});
for(int _i=1;_i<n;_i++){
auto res=get1({components});
vector<int>nc;
for(int i=0;i<(int)components.size();i++){
bool has=false;
for(int j:components[i]){
if(j==res.first)
has=true;
}
if(has){
for(int j:components[i])
nc.push_back(j);
components.erase(components.begin()+i);
break;
}
}
for(int i=0;i<(int)components.size();i++){
bool has=false;
for(int j:components[i]){
if(j==res.second)
has=true;
}
if(has){
for(int j:components[i])
nc.push_back(j);
components.erase(components.begin()+i);
break;
}
}
components.push_back(nc);
set_road(res.first,res.second);
}
}
#ifdef JAKOB
vector<pair<int,int>>gsteps;
set<pair<int,int>>gconns;
int gcstep;
int gqueries;
int gerr;
int gmqc;
int query(int size_a, int size_b, int a[], int b[]){
sort(a,a+size_a);
sort(b,b+size_b);
{
int i=0,j=0;
while(i<size_a&&j<size_b){
if(a[i]==b[j]){
cout<<"NOT DISJOINT\n";
abort();
}
if(a[i]<b[j])
i++;
else
j++;
}
}
gqueries++;
for(int i=0;i<size_a;i++)
for(int j=0;j<size_b;j++)
if(gconns.count({a[i],b[j]})==1||gconns.count({b[j],a[i]})==1)
return 1;
return 0;
}
void gprocess_step(){
gcstep++;
gconns.insert(gsteps[gcstep]);
}
void setRoad(int a, int b){
if(a<b)
swap(a,b);
if(a!=gsteps[gcstep].first||b!=gsteps[gcstep].second){
cout<<"ERROR got "<<a<<" "<<b<<", expected "<<gsteps[gcstep].first<<" "<<gsteps[gcstep].second<<"\n";
gerr++;
}else
cout<<"OK "<<a<<" "<<b<<"\n";
gprocess_step();
}
void solve(){
gconns.clear();
gsteps.clear();
gcstep=-1;
gqueries=0;
gerr=0;
int n=100;
vector<int>perm(n);
for(int i=0;i<n;i++)
perm[i]=i;
for(int i=0;i<n;i++)
swap(perm[i],perm[rand()%n]);
for(int i=1;i<n;i++)
gsteps.push_back({i,rand()%i});
for(auto&i:gsteps){
i.first=perm[i.first];
i.second=perm[i.second];
if(i.first<i.second)
swap(i.first,i.second);
i.first++;
i.second++;
}
for(int i=0;i<n-1;i++)
swap(gsteps[i],gsteps[rand()%(n-1)]);
gprocess_step();
run(n);
cout<<"query count: "<<gqueries<<"\n";
cout<<"error count: "<<gerr<<"\n";
if(gerr)
exit(0);
gmqc=max(gmqc,gqueries);
}
int main(){
ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
//freopen("input.in","r",stdin);freopen("output.out","w",stdout);
//int t=1;//cin>>t;
//while(t--)solve();
for(int i=0;i<50;i++){
srand(i);
solve();
}
cout<<"max queries: "<<gmqc<<"\n";
return 0;
}
#endif
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
604 KB |
Ok! 107 queries used. |
| 2 |
Correct |
4 ms |
640 KB |
Ok! 102 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
600 KB |
Ok! 555 queries used. |
| 2 |
Correct |
25 ms |
600 KB |
Ok! 634 queries used. |
| 3 |
Correct |
28 ms |
604 KB |
Ok! 644 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
74 ms |
604 KB |
Ok! 1528 queries used. |
| 2 |
Correct |
97 ms |
716 KB |
Ok! 1584 queries used. |
| 3 |
Correct |
78 ms |
604 KB |
Ok! 1619 queries used. |
| 4 |
Correct |
77 ms |
604 KB |
Ok! 1560 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
77 ms |
708 KB |
Ok! 1580 queries used. |
| 2 |
Correct |
102 ms |
696 KB |
Ok! 1591 queries used. |
| 3 |
Correct |
78 ms |
604 KB |
Ok! 1584 queries used. |
| 4 |
Correct |
75 ms |
604 KB |
Ok! 1551 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
102 ms |
692 KB |
Ok! 1589 queries used. |
| 2 |
Correct |
79 ms |
696 KB |
Ok! 1589 queries used. |
| 3 |
Correct |
78 ms |
700 KB |
Ok! 1596 queries used. |
| 4 |
Correct |
82 ms |
692 KB |
Ok! 1614 queries used. |
| 5 |
Correct |
80 ms |
1108 KB |
Ok! 1557 queries used. |
| 6 |
Correct |
80 ms |
704 KB |
Ok! 1553 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
82 ms |
600 KB |
Ok! 1589 queries used. |
| 2 |
Correct |
79 ms |
708 KB |
Ok! 1584 queries used. |
