| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 605848 |
2022-07-26T03:40:52 Z |
juancarlovieri |
ICC (CEOI16_icc) |
C++17 |
|
135 ms |
620 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
int par[105];
vector<int> all[105];
int aarr[105];
int barr[105];
int cnt2;
int* conv(vector<int> x, int* a) {
for (int i = 0; i < x.size(); ++i) a[i] = x[i];
return a;
}
int tanya (vector<int> a, vector<int> b) {
vector<int> aa;
vector<int> bb;
for (auto i : a) {
for (auto j : all[i]) aa.push_back(j + 1);
}
for (auto i : b) {
for (auto j : all[i]) bb.push_back(j + 1);
}
++cnt2;
if (cnt2 > 2250) while (1);
return query(aa.size(), bb.size(), conv(aa, aarr), conv(bb, barr));
}
int find(int i) {
if (par[i] == i) return i;
return par[i] = find(par[i]);
}
pair<vector<int>, vector<int>> div(vector<int> x) {
vector<int> a, b;
for (int i = 0; i < x.size() / 2; ++i) a.push_back(x[i]);
for (int i = x.size() / 2; i < x.size(); ++i) b.push_back(x[i]);
return {a, b};
}
pair<int, int> ans;
int tanya2(vector<int> a, vector<int> b) {
for (auto& i : a) ++i;
for (auto& i : b) ++i;
++cnt2;
if (cnt2 > 2250) while (1);
return query(a.size(), b.size(), conv(a, aarr), conv(b, barr));
}
bool cari(vector<int> act) {
if (act.size() == 1) return 0;
// puts("TSE");
auto [a, b] = div(act);
while (tanya(a, b) == 0) {
random_shuffle(act.begin(), act.end());
a = div(act).first;
b = div(act).second;
}
// if (tanya(a, b)) {
vector<int> na, nb;
for (auto i : a) {
for (auto j : all[i]) na.push_back(j);
}
for (auto i : b) {
for (auto j : all[i]) nb.push_back(j);
}
a = na, b = nb;
while (a.size() > 1) {
auto [a1, a2] = div(a);
// for (auto i : a1) cout << i << ' ';
// cout << endl;
// for (auto i : b) cout << i << ' ';
// cout << endl;
if (tanya2(a1, b)) a = a1;
else a = a2;
}
while (b.size() > 1) {
auto [b1, b2] = div(b);
if (tanya2(a, b1)) b = b1;
else b = b2;
}
ans = {find(a[0]), find(b[0])};
// while(a.size() > 1) {
// auto [a1, a2] = div(a);
// if (tanya(a1, b)) a = a1;
// else a = a2;
// }
// while(b.size() > 1) {
// auto [b1, b2] = div(b);
// if (tanya(a, b1)) b = b1;
// else b = b2;
// }
// ans = {a[0], b[0]};
// // cout << a[0] << ' ' << b[0] << endl;
// a = all[a[0]];
// b = all[b[0]];
// // for (auto i : a) cout << i << ' ';
// // cout << endl;
// // for (auto i : b) cout << i << ' ';
// // cout << endl;
// while(a.size() > 1) {
// auto [a1, a2] = div(a);
// // for (auto i : a1) cout << i << ' ';
// // cout << endl;
// // for (auto i : b) cout << i << ' ';
// // cout << endl;
// if (tanya2(a1, b)) a = a1;
// else a = a2;
// }
// while(b.size() > 1) {
// auto [b1, b2] = div(b);
// if (tanya2(a, b1)) b = b1;
// else b = b2;
// }
setRoad(a[0] + 1, b[0] + 1);
return 1;
// } else {
// if (cari(a)) return 1;
// if (cari(b)) return 1;
// }
return 0;
}
void run(int n) {
srand(time(0));
// query(1, 1, {}, {});
iota(par, par + n, 0);
vector<int> act(n);
iota(act.begin(), act.end(), 0);
for (int i = 0; i < n; ++i) all[i].push_back(i);
for (int ii = 0; ii < n - 1; ++ii) {
random_shuffle(act.begin(), act.end());
// cout << "FINDING NEW " << ii << endl;
// assert(cari(act));
// for (auto i : all[ans.second]) {
// all[ans.first].push_back(i);
// }
// par[ans.second] = ans.first;
// act.clear();
// for (int i = 0; i < n; ++i) if (find(i) == i) act.push_back(i);
// for (auto i : act) {
// for (auto j : all[i])
// cout << j << ' ';
// cout << endl;
// }
int tmp = 0;
int sukses = -1;
for (int i = 0; i < 20; ++i) {
if ((1 << i) > act.size()) break;
vector<int> a, b;
for (int j = 0; j < act.size(); ++j) {
if (j & (1 << i)) b.push_back(act[j]);
else a.push_back(act[j]);
}
if (a.empty() or b.empty()) continue;
// for (auto i : a) {
// cout << i << ' ';
// }
// cout << endl;
// for (auto i : b) {
// cout << i << ' ';
// }
// cout << endl;
if (tanya(a, b)) {
sukses = i;
// cout << i << endl;
tmp |= (1 << i);
}
}
// cout << sukses << endl;
vector<int> a, b;
for (int j = 0; j < act.size(); ++j) {
if (j & (1 << sukses)) b.push_back(act[j]);
else a.push_back(act[j]);
}
vector<int> na, nb;
for (auto i : a) {
for (auto j : all[i]) na.push_back(j);
}
for (auto i : b) {
for (auto j : all[i]) nb.push_back(j);
}
if (na.size() > nb.size()) swap(na, nb), swap(a, b);
while (na.size() > 1) {
auto [na1, na2] = div(na);
if (tanya2(na1, nb)) {
na = na1;
} else na = na2;
}
int idx = -1;
ans = {find(na[0]), tmp ^ find(na[0])};
for (int i = 0; i < act.size(); ++i) if (act[i] == find(na[0])) ans.second = act[tmp ^ i];
for (auto i : all[ans.second]) all[ans.first].push_back(i);
par[ans.second] = ans.first;
nb.clear();
for (auto i : all[ans.second]) nb.push_back(i);
// for (auto i : na) cout << i << ' ';
// cout << endl;
// for (auto i : nb) cout << i << ' ';
// cout << endl;
while (nb.size() > 1) {
auto [nb1, nb2] = div(nb);
if (tanya2(na, nb1)) {
nb = nb1;
} else nb = nb2;
}
assert(tanya2(na, nb));
setRoad(na[0] + 1, nb[0] + 1);
act.clear();
for (int i = 0; i < n; ++i) if (find(i) == i) act.push_back(i);
}
}
Compilation message
icc.cpp: In function 'int* conv(std::vector<int>, int*)':
icc.cpp:12:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for (int i = 0; i < x.size(); ++i) a[i] = x[i];
| ~~^~~~~~~~~~
icc.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > div(std::vector<int>)':
icc.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 0; i < x.size() / 2; ++i) a.push_back(x[i]);
| ~~^~~~~~~~~~~~~~
icc.cpp:38:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i = x.size() / 2; i < x.size(); ++i) b.push_back(x[i]);
| ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:157:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | if ((1 << i) > act.size()) break;
| ~~~~~~~~~^~~~~~~~~~~~
icc.cpp:159:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for (int j = 0; j < act.size(); ++j) {
| ~~^~~~~~~~~~~~
icc.cpp:181:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | for (int j = 0; j < act.size(); ++j) {
| ~~^~~~~~~~~~~~
icc.cpp:203:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
203 | for (int i = 0; i < act.size(); ++i) if (act[i] == find(na[0])) ans.second = act[tmp ^ i];
| ~~^~~~~~~~~~~~
icc.cpp:201:9: warning: unused variable 'idx' [-Wunused-variable]
201 | int idx = -1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
468 KB |
Ok! 122 queries used. |
| 2 |
Correct |
6 ms |
468 KB |
Ok! 122 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
508 KB |
Ok! 670 queries used. |
| 2 |
Correct |
30 ms |
500 KB |
Ok! 553 queries used. |
| 3 |
Correct |
31 ms |
496 KB |
Ok! 581 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
504 KB |
Ok! 1633 queries used. |
| 2 |
Correct |
128 ms |
620 KB |
Ok! 1289 queries used. |
| 3 |
Correct |
112 ms |
492 KB |
Ok! 1615 queries used. |
| 4 |
Correct |
110 ms |
516 KB |
Ok! 1605 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
508 KB |
Ok! 1588 queries used. |
| 2 |
Correct |
122 ms |
520 KB |
Ok! 1594 queries used. |
| 3 |
Correct |
123 ms |
500 KB |
Ok! 1455 queries used. |
| 4 |
Correct |
111 ms |
468 KB |
Ok! 1654 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
504 KB |
Ok! 1488 queries used. |
| 2 |
Correct |
123 ms |
508 KB |
Ok! 1476 queries used. |
| 3 |
Correct |
111 ms |
508 KB |
Ok! 1410 queries used. |
| 4 |
Correct |
107 ms |
496 KB |
Ok! 1478 queries used. |
| 5 |
Correct |
119 ms |
620 KB |
Ok! 1606 queries used. |
| 6 |
Correct |
135 ms |
508 KB |
Ok! 1498 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
496 KB |
Ok! 1583 queries used. |
| 2 |
Correct |
107 ms |
492 KB |
Ok! 1312 queries used. |
