| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 824031 |
2023-08-13T11:42:52 Z |
sysia |
ICC (CEOI16_icc) |
C++17 |
|
98 ms |
520 KB |
//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "icc.h"
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
typedef pair<int, int> T;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int p(int a, int b){
return a + rng() % (b-a+1);
}
struct Interactor{
int n;
set<T>s, f;
vector<T>edges;
int ptr = 0, cnt = 0;
void add(){
if (ptr >= (int)edges.size()) {
cerr << cnt << "\n";
cout << "yay\n";
return;
}
// cerr << "added ";debug(edges[ptr]);
s.insert(edges[ptr]);
swap(edges[ptr].first, edges[ptr].second);
s.insert(edges[ptr]);
ptr++;
}
Interactor(){
// n = 100;
n = p(1, 7);
debug(n);
// n = 5;
vector<int>ord(n+1);
iota(ord.begin(), ord.end(),0);
shuffle(ord.begin()+1, ord.end(), rng);
// edges = {{2, 5}, {3, 5}, {4, 3}, {1, 5}};
for (int i = 2; i<=n; i++){
int par = p(1, i-1);
edges.emplace_back(ord[i], ord[par]);
debug(ord[i], ord[par]);
}
add();
}
int query(int size_a, int size_b, int a[], int b[]){
cnt++;
for (int i = 0; i<size_a; i++){
for (int j = 0; j<size_b; j++){
if (a[i] == b[j]){
assert(false);
exit(0);
}
if (s.find({a[i], b[j]}) != s.end()) return 1;
}
}
return 0;
}
void setRoad(int a, int b){
if (s.find({a, b}) == s.end()){
assert(false);
} else {
if (f.find({a, b}) != f.end()){
assert(false);
}
f.insert({a, b});
f.insert({b, a});
}
add();
}
} I;
struct DSU{
vector<int>rep, sz;
DSU(int n){
rep.resize(n+1);
iota(rep.begin(), rep.end(), 0);
sz.assign(n+1, 1);
}
int f(int a){
return a == rep[a] ? a : rep[a] = f(rep[a]);
}
void u(int a, int b){
a = f(a); b = f(b);
assert(a != b);
if (sz[a] < sz[b]) swap(a, b);
rep[b] = a;
sz[a] += sz[b];
}
};
void run(int n){ //int n as arg
// int n = I.n;
vector<vector<int>>tab(n+1);
DSU dsu(n+1);
auto create_groups = [&](int cnt){
for (int rep = 1; rep <= cnt; rep++) tab[rep].clear();
int ptr = 1;
vector<int>s(n+1);
for (int i = 1; i<=n; i++){
if (dsu.f(i) == i){
s[i] = ptr++;
}
}
for (int i = 1; i<=n; i++){
tab[s[dsu.f(i)]].emplace_back(i);
}
for (int i = 1; i<=cnt; i++){
debug(i, tab[i]);
}
};
typedef vector<int> vi;
auto comp_to_vert = [&](vi &now){
vector<int>ret;
for (auto x: now){
for (auto v: tab[x]){
ret.emplace_back(v);
}
}
return ret;
};
auto ask = [&](vector<int>x, vector<int>y){
return query((int)x.size(), (int)y.size(), x.data(), y.data());
};
vi A, B;
auto divide = [&](int i){
int mask = 0;
for (int p = 0; (1<<p) <= i; p++){
A.clear(); B.clear();
for (int rep = 1; rep <= i; rep++){
if (rep&(1<<p)) A.emplace_back(rep);
else B.emplace_back(rep);
}
if (ask(comp_to_vert(A), comp_to_vert(B))) {
mask += (1<<p);
}
}
return mask;
};
auto binsearch = [&](int i, int mask){
A.clear(); B.clear();
debug(mask);
for (int j = 1; j <= i; j++){
int k = (j^mask);
if (j < k && k <= i){
A.emplace_back(j);
B.emplace_back(k);
}
}
debug(A);
debug(B);
vector<int> a = comp_to_vert(A);
vector<int> b = comp_to_vert(B);
debug(a, b);
int ans[2];
for (int rep = 0; rep < 2; rep++){
int l = 0, r = (int)a.size()-1;
ans[rep] = r;
while (r >= l){
int mid = (l+r)/2;
if (ask(vi(a.begin(), a.begin()+mid+1), b)) {
ans[rep] = a[mid];
r = mid-1;
} else l = mid+1;
}
swap(a, b);
}
debug(ans[0], ans[1]);
dsu.u(ans[0], ans[1]);
setRoad(ans[0], ans[1]);
};
for (int i = n; i >= 2; i--){
create_groups(i);
binsearch(i, divide(i));
}
}
// int32_t main(){ run(); }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
504 KB |
Ok! 130 queries used. |
| 2 |
Correct |
6 ms |
468 KB |
Ok! 124 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
468 KB |
Ok! 674 queries used. |
| 2 |
Correct |
30 ms |
504 KB |
Ok! 648 queries used. |
| 3 |
Correct |
32 ms |
488 KB |
Ok! 665 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
496 KB |
Ok! 1640 queries used. |
| 2 |
Incorrect |
89 ms |
520 KB |
Program is not terminated properly. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
504 KB |
Program is not terminated properly. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
468 KB |
Program is not terminated properly. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
468 KB |
Too many queries! 1678 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
