| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1025919 |
2024-07-17T11:13:53 Z |
vjudge1 |
ICC (CEOI16_icc) |
C++14 |
|
35 ms |
600 KB |
#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<(int)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<(int)v1.size(); ++i) arr1[i] = v1[i];
for(int i=0; i<(int)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<(int)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 = (int)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 = (int)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 = (int)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 = (int)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<(int)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 = (int)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);
break;
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Not all edges were guessed! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
600 KB |
Not all edges were guessed! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
600 KB |
Not all edges were guessed! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
600 KB |
Not all edges were guessed! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
600 KB |
Not all edges were guessed! |
| 2 |
Halted |
0 ms |
0 KB |
- |
