| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 605193 |
2022-07-25T13:44:38 Z |
Drew_ |
ICC (CEOI16_icc) |
C++17 |
|
513 ms |
520 KB |
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f1 first
#define s2 second
using ii = pair<int, int>;
// int query(int size_a, int size_b, int a[], int b[]);
// void setRoad(int u, int v);
// void WA() { cout << "WA\n"; assert(1); exit(0); }
mt19937 RNG(69);
const int MAX = 107;
int ds[MAX];
inline int frep(int x) { return ds[x] == x ? x : ds[x] = frep(ds[x]); }
inline void join(int x, int y) { ds[frep(x)] = frep(y); }
namespace brute
{
void solve(int N)
{
iota(ds+1, ds+N+1, 1);
int a[MAX], b[MAX];
for (int rep = 0; rep < N-1; ++rep)
{
bool ok = false;
for (int i = 1; i <= N && !ok; ++i)
{
for (int j = i+1; j <= N && !ok; ++j)
{
if (frep(i) == frep(j))
continue;
a[0] = i; b[0] = j;
if (query(1, 1, a, b))
{
setRoad(i, j);
join(i, j);
ok = true;
}
}
}
}
}
}
void run(int N)
{
int ty = -1, qcount = 0;
const auto split = [&](vector<ii> v) -> pair<vector<ii>, vector<ii>>
{
sort(v.begin(), v.end());
vector<ii> tmp;
for (auto &[x, y] : v)
{
if (!tmp.empty() && x == tmp.back().f1) tmp.back().s2++;
else tmp.pb({x, 1});
}
ty = (int)tmp.size();
bitset<MAX> L;
int dif = 1e9;
for (int rep = 0; rep < 696; ++rep)
{
shuffle(tmp.begin(), tmp.end(), RNG);
int p = 0, q = 0;
for (auto &[x, y] : tmp)
{
if (p > q) q += y;
else p += y;
}
if (abs(p-q) < dif)
{
dif = abs(p-q);
p = 0, q = 0; L.reset();
for (auto &[x, y] : tmp)
{
if (p > q) q += y;
else L[x] = true, p += y;
}
}
}
vector<ii> l, r;
for (auto &[x, y] : v)
{
if (L[x]) l.pb({x, y});
else r.pb({x, y});
}
return {l, r};
};
iota(ds+1, ds+N+1, 1);
int a[MAX], b[MAX];
for (int rep = 0; rep < N-1; ++rep)
{
// cerr << "rep: " << rep << '\n';
// split [1, N] into two groups
// city `x` must be in the same group with city `frep(x)`
vector<vector<ii>> cur;
{
vector<ii> vec;
for (int i = 1; i <= N; ++i)
vec.pb({frep(i), i});
sort(vec.begin(), vec.end());
cur.pb(vec);
}
for (;;)
{
vector<vector<ii>> A, B;
for (auto vec : cur)
{
auto [v1, v2] = split(vec);
if (ty == 1)
continue;
A.pb(v1); B.pb(v2);
}
// cerr << "vec: ";
// for (auto vec : cur)
// {
// for (auto &[x, y] : vec)
// cerr << y << " ";
// cerr << ", ";
// }
// cerr << '\n';
int sa = 0, sb = 0;
for (auto v : A)
for (auto [x, y] : v)
a[sa++] = y;
for (auto v : B)
for (auto [x, y] : v)
b[sb++] = y;
// for (auto [x, y] : v1)
// for (auto [p, q] : v2)
// assert(y != q);
// cerr << "A: ";
// for (auto vec : A)
// {
// for (auto &[x, y] : vec)
// cerr << y << " ";
// cerr << ", ";
// }
// cerr << '\n';
// cerr << "B: ";
// for (auto vec : B)
// {
// for (auto &[x, y] : vec)
// cerr << y << " ";
// cerr << ", ";
// }
// cerr << '\n';
// if (++qcount >= 2250) assert(1);
if (query(sa, sb, a, b))
{
vector<ii> v1, v2;
{
int l = 0, r = (int)A.size() - 1;
while (l < r)
{
int mid = (l + r) >> 1;
sa = 0;
for (int i = l; i <= mid; ++i)
for (auto [x, y] : A[i])
a[sa++] = y;
for (int i = l; i <= mid; ++i)
for (auto [x, y] : B[i])
b[sb++] = y;
if (query(sa, sb, a, b)) r = mid;
else l = mid + 1;
}
v1 = A[l], v2 = B[l];
sa = 0;
for (auto [x, y] : v1)
a[sa++] = y;
sb = 0;
for (auto [x, y] : v2)
b[sb++] = y;
}
// cerr << "v1: ";
// for (auto [x, y] : v1)
// cerr << y << " ";
// cerr << '\n';
// cerr << "v2: ";
// for (auto [x, y] : v2)
// cerr << y << " ";
// cerr << '\n';
{
int l = 0, r = (int)v2.size() - 1;
while (l < r)
{
int mid = (l + r) >> 1;
sb = mid-l+1;
for (int i = l; i <= mid; ++i)
b[i-l] = v2[i].s2;
// if (++qcount >= 2250) assert(1);
if (query(sa, sb, a, b)) r = mid;
else l = mid + 1;
}
sb = 1; b[0] = v2[l].s2;
}
{
int l = 0, r = (int)v1.size() - 1;
while (l < r)
{
int mid = (l + r) >> 1;
sa = mid-l+1;
for (int i = l; i <= mid; ++i)
a[i-l] = v1[i].s2;
// if (++qcount >= 2250) assert(1);
if (query(sa, sb, a, b)) r = mid;
else l = mid + 1;
}
sa = 1; a[0] = v1[l].s2;
}
setRoad(a[0], b[0]);
join(a[0], b[0]);
break;
}
else
{
cur.clear();
for (auto v : A)
cur.pb(v);
for (auto v : B)
cur.pb(v);
}
};
}
// if (N == 100)
// {
// assert(1);
// }
}
// int N, cur = 0, QC = 0;
// int U[MAX], V[MAX];
// bitset<MAX> yes[MAX];
// void setRoad(int u, int v)
// {
// // cerr << "SET ----->> " << u << " and " << v << '\n';
// if ((U[cur] == u && V[cur] == v) || (U[cur] == v && V[cur] == u))
// {
// if (++cur < N-1)
// yes[U[cur]][V[cur]] = yes[V[cur]][U[cur]] = true;
// return;
// }
// WA();
// }
// int query(int size_a, int size_b, int a[], int b[])
// {
// QC++;
// for (int i = 0; i < size_a; ++i)
// for (int j = 0; j < size_b; ++j)
// {
// assert(a[i] != b[j]);
// if (yes[a[i]][b[j]])
// return true;
// }
// return false;
// }
// int main()
// {
// ios :: sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// cin >> N;
// for (int i = 0; i < N-1; ++i)
// cin >> U[i] >> V[i];
// yes[U[0]][V[0]] = yes[V[0]][U[0]] = true;
// run(N);
// if (cur == N-1) cout << "AC\n";
// else cout << "WA\n", assert(1);
// cout << "query count: " << QC << '\n';
// }
Compilation message
icc.cpp: In function 'void run(int)':
icc.cpp:55:15: warning: unused variable 'qcount' [-Wunused-variable]
55 | int ty = -1, qcount = 0;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
468 KB |
Ok! 96 queries used. |
| 2 |
Correct |
7 ms |
500 KB |
Ok! 95 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
492 KB |
Ok! 503 queries used. |
| 2 |
Correct |
113 ms |
492 KB |
Ok! 432 queries used. |
| 3 |
Correct |
106 ms |
492 KB |
Ok! 453 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
281 ms |
500 KB |
Ok! 1241 queries used. |
| 2 |
Correct |
491 ms |
508 KB |
Ok! 1044 queries used. |
| 3 |
Correct |
241 ms |
520 KB |
Ok! 1177 queries used. |
| 4 |
Correct |
394 ms |
512 KB |
Ok! 1210 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
320 ms |
508 KB |
Ok! 1169 queries used. |
| 2 |
Correct |
403 ms |
520 KB |
Ok! 1193 queries used. |
| 3 |
Correct |
482 ms |
508 KB |
Ok! 1135 queries used. |
| 4 |
Correct |
232 ms |
496 KB |
Ok! 1203 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
492 ms |
520 KB |
Ok! 1128 queries used. |
| 2 |
Correct |
488 ms |
508 KB |
Ok! 1143 queries used. |
| 3 |
Correct |
513 ms |
520 KB |
Ok! 1156 queries used. |
| 4 |
Correct |
473 ms |
516 KB |
Ok! 1184 queries used. |
| 5 |
Correct |
397 ms |
504 KB |
Ok! 1257 queries used. |
| 6 |
Correct |
447 ms |
500 KB |
Ok! 1255 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
476 ms |
520 KB |
Ok! 1141 queries used. |
| 2 |
Correct |
497 ms |
512 KB |
Ok! 1078 queries used. |
