| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1289868 | ChuanChen | ICC (CEOI16_icc) | C++20 | 0 ms | 0 KiB |
#define LOCAL
#ifndef LOCAL
#include "icc.h"
#endif
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void setRoad(int a, int b) {
cout << "report" << a << ' ' << b << endl;
};
#endif
#define debug(v) cerr << #v << ": " << v << endl;
mt19937 rng(time(NULL));
const int MAXN = 110;
int rep[MAXN], N;
vector<int> comp[MAXN];
int do_query(vector<int> a, vector<int> b) {
#ifdef LOCAL
for (int i : a) cout << i << ' ';
cout << endl;
for (int i : b) cout << i << ' ';
cout << endl;
int v; cin >> v;
return v;
#else
int tmp[MAXN], tmp2[MAXN];
for (int i=0; i<(int)a.size(); i++) tmp[i] = a[i]+1;
for (int i=0; i<(int)b.size(); i++) tmp2[i] = b[i]+1;
return query((int)a.size(), (int)b.size(), tmp, tmp2);
#endif
}
pair<int, int> find_aresta(vector<int> A, vector<int> B){
if(A.size() == B.size() && A.size() == 1) return {A[0], B[0]};
if(A.size() > B.size()) swap(A, B);
vector<int> t1, t2;
for(int i = 0; i < B.size()/2; i++) t1.push_back(B[i]);
for(int i = B.size()/2; i < B.size(); i++) t2.push_back(B[i]);
// cerr << "A: "; for(int i : A) cerr << i << ' '; cerr << endl;
// cerr << "t1: "; for(int i : t1) cerr << i << ' '; cerr << endl;
// cerr << "t2: "; for(int i : t2) cerr << i << ' '; cerr << endl;
int verdic = do_query(A, t1);
if(verdic == 1) return find_aresta(A, t1);
else return find_aresta(A, t2);
}
int find(int no){
if(rep[no] == no) return no;
return rep[no] = find(rep[no]);
}
void merge(int a, int b){
a = find(a), b = find(b);
// cerr << "merging " << a << ' ' << b << endl;
if(comp[a].size() < comp[b].size()) swap(a, b);//sz[a] > sz[b]
rep[b] = rep[a];
for(int i : comp[b]) comp[a].push_back(i);
comp[b].clear();
// cerr << "comp[a]: "; for(int i : comp[a]) cerr << i << ' '; cerr << endl;
}
void solve(int n){
if(n == 1) return;
// debug(n);
// debug(all_n);
vector<int> comp_no_qst;
for(int i = 0; i < N; i++) comp_no_qst.push_back(rep[i]);
// cerr << "comp_no_qst: "; for(int i : comp_no_qst) cerr << i << ' '; cerr << endl;
sort(comp_no_qst.begin(), comp_no_qst.end());
int maxComp = comp_no_qst.back();
comp_no_qst.erase( unique(comp_no_qst.begin(), comp_no_qst.end()), comp_no_qst.end() );
vector<int> ks;
for(int k = 0; (1<<k) <= maxComp; k++) ks.push_back(k);
shuffle(ks.begin(), ks.end(), rng);
// for(int k = 0;; k++){
for(int k : ks){
vector<int> A, B;
for(int c : comp_no_qst){
if(c&(1<<k)) for(int no : comp[c]) A.push_back(no);
else for(int no : comp[c]) B.push_back(no);
}
int verdic = do_query(A, B);
if(verdic){
auto [a, b] = find_aresta(A, B);
setRoad(a, b);
merge(a, b);
break;
}
}
solve(n-1);
}
void run(int n){
N = n;
for(int i = 0; i < n; i++){
rep[i] = i;
comp[i].push_back(i);
}
solve(n);
}
#ifdef LOCAL
int main() {
int n; cin >> n;
run(n);
return 0;
}
#endif