| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1289775 | Sofiatpc | ICC (CEOI16_icc) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <icc.h>
using namespace std;
const int MAXN = 105;
int p[MAXN], s[MAXN], a[MAXN], b[MAXN];
int find(int x){
if(p[x] == x)return x;
return p[x] = find(p[x]);
}
void merge(int a, int b){
a = find(a), b = find(b);
if(s[a] < s[b])swap(a,b);
p[b] = a;
s[a] += s[b];
}
void run(int n){
for(int i = 1; i <= n; i++){
p[i] = i; s[i] = 1;
}
for(int z = 1; z < n; z++){
int pta, ptb;
for(int i = 0; i <= 6; i++){
pta = 0, ptb = 0;
for(int j = 1; j <= n; j++){
int x = find(j);
if(x & (1<<i)){ a[pta] = j; pta++; }
else { b[ptb] = j; ptb++; }
}
int x = query(pta, ptb, a, b);
if(x == 1)break;
}
int la = 1, ra = pta;
while(la != ra){
int mid = (la+ra)/2;
if( query(mid, ptb, a, b) == 1)ra = mid;
else la = mid+1;
}
int lb = 1, rb = ptb;
while(lb != rb){
int mid = (lb+rb)/2;
if( query(pta, mid, a, b) == 1)rb = mid;
else lb = mid+1;
}
setRoad(a[la-1],b[lb-1]);
merge(a[la-1], b[lb-1]);
}
}
