| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1025909 | vjudge1 | ICC (CEOI16_icc) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include “icc.h”
using namespace std;
int query(int size_a, int size_b, int a[], int b[]);
void setRoad(int a, int b);
void run(int N) {
int T = N-1;
vector<vector<int>>sets;
for(int i=1; i<=N; ++i) {
vector<int>tmp;
tmp.push_back(i);
sets.push_back(tmp);
}
while(T--) {
int len = sets.size();
while(len > 1) {
int x = len / 2, cnt = 0;
vector<int>v1, v2;
for(int i=0; i<sets.size(); i+=x) {
for(int j = i; j < min(i+x, (int)sets.size()-1); ++j) {
if(cnt % 2) {
for(int k: sets[j]) v2.push_back(k);
}
else {
for(int k: sets[j]) v1.push_back(k);
}
}
++cnt;
}
int arr1[v1.size()], arr2[v2.size()];
for(int i=0; i<v1.size(); ++i) arr1[i] = v1[i];
for(int i=0; i<v2.size(); ++i) arr2[i] = v2[i];
int X = query((int)v1.size(), (int)v2.size(), arr1, arr2);
if(!X) len /= 2;
else {
vector<int>V1, V2;
for(int i=0; i<sets.size(); i+=x) {
for(int j = i; j < min(i+x, (int)sets.size()-1); ++j) {
if(cnt%2) V2.push_back(j);
else V1.push_back(j);
}
++cnt;
}
int l = 0, r = V1.size() - 1;
while(l < r) {
int m = (l+r)/2;
vector<int>nv;
for(int i=l; i<=m; ++i) {
for(int j: sets[V1[i]]) nv.push_back(j);
}
int siz = nv.size(), arr_tmp[siz];
for(int i=0; i<siz; ++i) arr_tmp[i] = nv[i];
X = query(siz, (int)v2.size(), arr_tmp, arr2);
if(!X) l = m + 1;
else r = m;
}
int ans1 = V1[r];
l = 0, r = V2.size() - 1;
while(l < r) {
int m = (l+r)/2;
vector<int>nv;
for(int i=l; i<=m; ++i) {
for(int j: sets[V2[i]]) nv.push_back(j);
}
int siz = nv.size(), arr_tmp[siz];
for(int i=0; i<siz; ++i) arr_tmp[i] = nv[i];
X = query(siz, (int)v1.size(), arr_tmp, arr1);
if(!X) l = m + 1;
else r = m;
}
int ans2 = V2[r];
l = 0, r = sets[ans1].size() - 1;
int arr_tmp[sets[ans2].size()];
for(int i=0; i<sets[ans2].size(); ++i) arr_tmp[i] = sets[ans2][i];
while(l < r) {
int m = (l+r)/2;
vector<int>nv;
for(int i=l; i<=m; ++i) nv.push_back(sets[ans1][i]);
int siz = nv.size(), arr_tmp2[siz];
for(int i=0; i<siz; ++i) arr_tmp2[i] = nv[i];
X = query(siz, (int)sets[ans2].size(), arr_tmp2, arr_tmp);
if(!X) l = m + 1;
else r = m;
}
int arr_tmp2[1] = {r};
l = 0, r = sets[ans2.size()] - 1;
while(l < r) {
int m = (l+r)/2;
vector<int>nv;
for(int i=l; i<=m; ++i) nv.push_back(sets[ans2][i]);
int siz = nv.size(), arr_tmp3[siz];
for(int i=0; i<siz; ++i) arr_tmp3[i] = nv[i];
X = query(siz, 1, arr_tmp3, arr_tmp2);
if(!X) l = m + 1;
else r = m;
}
setRoad(arr_tmp2[0], r);
for(int x: sets[ans2]) sets[ans1].push_back(x);
sets.erase(sets.begin() + ans2);
}
}
}
}