| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1289837 | lambd47 | ICC (CEOI16_icc) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include"icc.h"
using namespace std;
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
/*
int query(int a, int b, vector<int> va, vector<int> vb){
cout<<a<<" "<<b<<"\n";
for(auto x:va)cout<<x<<" ";
cout<<"\n";
for(auto y:vb)cout<<y<<" ";
cout<<"\n";
int x;cin>>x;
return x;
}
void setRoad(int a,int b){
cout<<a<<" "<<b<<"receba\n";
}*/
const int MX=1e2+7;
const int lg=7;
mt19937 rng(time(0));
void run(int n){
vector<vector<int>> vec(n);
vector<int> maluco(n);
iota(all(maluco),0);
shuffle(all(maluco),rng);
L(i,0,n-1)vec[i].push_back(maluco[i]+1);
int aa[MX];
int bb[MX];
auto ask=[&](vector<int> a, vector<int> b)->bool{
L(i,0,sz(a)-1)aa[i]=a[i];
L(i,0,sz(b)-1)bb[i]=b[i];
//cout<<"=========\n";
return query(sz(a),sz(b),aa,bb);//mudar essa bullshitaiada
};
R(tam,n,2){
vector<vector<int>> v(2);
vector<int> ord(__lg(tam)+1);
iota(all(ord),0);
shuffle(all(ord),rng);
L(kk,0,sz(ord)-1){
i=ord[kk]
L(j,0,tam-1){
int b=((1<<i)&j)?1:0;
for(auto a:vec[j])v[b].push_back(a);
}
if(kk==sz(ord)-1)break;
if(ask(v[0],v[1]))break;
v[0].clear();
v[1].clear();
}
int l=0;int r=sz(v[0])-1;
int ans=0;
vector<int> aux;
while(l<=r){
aux.clear();
int m=(l+r)/2;
if(l==r){
ans=l;
l=r+1;
continue;
}
L(i,l,m)aux.push_back(v[0][i]);
if(ask(aux,v[1])){
r=m;
}
else{
l=m+1;
}
}
vector<int> goat;goat.push_back({v[0][ans]});
l=0;r=sz(v[1])-1;
ans=l;
while(l<=r){
aux.clear();
int m=(l+r)/2;
if(l==r){
ans=l;
l=r+1;
continue;
}
L(i,l,m)aux.push_back(v[1][i]);
if(ask(aux,goat)){
r=m;
}
else{
l=m+1;
}
}
int a=goat[0];
int b=v[1][ans];
setRoad(a,b);
int ida;int idb;
L(i,0,tam-1){
for(auto x:vec[i]){
if(x==a)ida=i;
if(x==b)idb=i;
}
}
for(auto x:vec[ida])vec[idb].push_back(x);
swap(vec[tam-1],vec[ida]);
}
}