// ~Be name khoda~ //
#include<bits/stdc++.h>
#include "library.h"
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define cl clear
#define endll '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 10;
const int maxn5 = 2e3 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 2e18;
int per[maxn5];
vector <int> av, as, part, out, adj[maxn5];
bool mark[maxn5];
int cnt = 0;
bool done = false;
inline int found_adj(){
int e = 0;
for(auto u : as) for(auto v : adj[u]){
e += out[v - 1];
//cout << u << ' ';
}
e /= 2;
//cout << " final " << e << endl;
return int(as.size()) - e;
}
inline bool ask(){
cnt++;
if(cnt > 20000){
done = true;
return false;
}
for(int i = 0; i < out.size(); i++)
out[i] = 0;
for(auto u : as)
out[u - 1] = 1;
int ans = Query(out);
return ans < found_adj();
}
inline void parti(){
if(done) return;
for(int i = 0; i < av.size(); i++)
per[i] = i;
shuffle(per, per + av.size(), rng);
as.clear();
for(int i = 0; i < av.size(); i++)
if(per[i] <= (av.size() - 1) / 2)
as.pb(av[i]);
bool re = ask();
if(re){
part.clear();
for(auto u : as)
part.pb(u);
return;
}
if(done) return;
//*
as.clear();
for(int i = 0; i < av.size(); i++)
if(per[i] > (av.size() - 1) / 2)
as.pb(av[i]);
re = ask();
if(re){
part.clear();
for(auto u : as)
part.pb(u);
return;
}
//*/
parti();
return;
}
inline pair<int, int> find_adj(){
if(av.size() == 2) return {av[0], av[1]};
if(av.size() == 3){
as.clear();
as.pb(av[0]);
as.pb(av[1]);
bool re = ask();
if(re) return {av[0], av[1]};
as.pop_back();
as.pb(av[2]);
re = ask();
if(re) return {av[0], av[2]};
return {av[1], av[2]};
}
parti();
if(done) return {0, 0};
av.clear();
for(auto u : part)
av.pb(u);
return find_adj();
}
void Solve(int n)
{
if(n == 1){
vector <int> ans;
ans.pb(1);
Answer(ans);
return;
}
out.resize(n);
int rem = n - 1;
while(rem){
av.clear();
for(int i = 1; i <= n; i++) if(adj[i].size() < 2)
av.pb(i);
pair <int, int> tmp = find_adj();
if(done) return;
adj[tmp.fi].pb(tmp.se);
adj[tmp.se].pb(tmp.fi);
//cout << "found out " << tmp.fi << ' ' << tmp.se << " adj " << endl;
rem--;
}
vector <int> ans;
int v = -1;
for(int i = 1; i <= n; i++) if(adj[i].size() == 1)
v = i;
ans.pb(v);
mark[v] = true;
v = adj[v][0];
while(true){
ans.pb(v);
mark[v] = true;
if(adj[v].size() == 1)
break;
int u = adj[v][0];
if(mark[u])
u = adj[v][1];
v = u;
}
Answer(ans);
return;
}
Compilation message
library.cpp: In function 'bool ask()':
library.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0; i < out.size(); i++)
| ~~^~~~~~~~~~~~
library.cpp: In function 'void parti()':
library.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i = 0; i < av.size(); i++)
| ~~^~~~~~~~~~~
library.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i = 0; i < av.size(); i++)
| ~~^~~~~~~~~~~
library.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | if(per[i] <= (av.size() - 1) / 2)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
library.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i = 0; i < av.size(); i++)
| ~~^~~~~~~~~~~
library.cpp:78:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if(per[i] > (av.size() - 1) / 2)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
328 KB |
# of queries: 2646 |
| 2 |
Correct |
36 ms |
356 KB |
# of queries: 2494 |
| 3 |
Correct |
37 ms |
328 KB |
# of queries: 2886 |
| 4 |
Correct |
34 ms |
352 KB |
# of queries: 2759 |
| 5 |
Correct |
38 ms |
340 KB |
# of queries: 2841 |
| 6 |
Correct |
43 ms |
340 KB |
# of queries: 2772 |
| 7 |
Correct |
47 ms |
360 KB |
# of queries: 2841 |
| 8 |
Correct |
49 ms |
336 KB |
# of queries: 2686 |
| 9 |
Correct |
39 ms |
344 KB |
# of queries: 2746 |
| 10 |
Correct |
23 ms |
328 KB |
# of queries: 1717 |
| 11 |
Correct |
0 ms |
328 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
328 KB |
# of queries: 0 |
| 13 |
Correct |
0 ms |
328 KB |
# of queries: 3 |
| 14 |
Correct |
0 ms |
328 KB |
# of queries: 4 |
| 15 |
Correct |
2 ms |
328 KB |
# of queries: 92 |
| 16 |
Correct |
3 ms |
328 KB |
# of queries: 208 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
328 KB |
# of queries: 2646 |
| 2 |
Correct |
36 ms |
356 KB |
# of queries: 2494 |
| 3 |
Correct |
37 ms |
328 KB |
# of queries: 2886 |
| 4 |
Correct |
34 ms |
352 KB |
# of queries: 2759 |
| 5 |
Correct |
38 ms |
340 KB |
# of queries: 2841 |
| 6 |
Correct |
43 ms |
340 KB |
# of queries: 2772 |
| 7 |
Correct |
47 ms |
360 KB |
# of queries: 2841 |
| 8 |
Correct |
49 ms |
336 KB |
# of queries: 2686 |
| 9 |
Correct |
39 ms |
344 KB |
# of queries: 2746 |
| 10 |
Correct |
23 ms |
328 KB |
# of queries: 1717 |
| 11 |
Correct |
0 ms |
328 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
328 KB |
# of queries: 0 |
| 13 |
Correct |
0 ms |
328 KB |
# of queries: 3 |
| 14 |
Correct |
0 ms |
328 KB |
# of queries: 4 |
| 15 |
Correct |
2 ms |
328 KB |
# of queries: 92 |
| 16 |
Correct |
3 ms |
328 KB |
# of queries: 208 |
| 17 |
Correct |
428 ms |
376 KB |
# of queries: 19719 |
| 18 |
Correct |
387 ms |
500 KB |
# of queries: 19581 |
| 19 |
Correct |
401 ms |
496 KB |
# of queries: 19139 |
| 20 |
Correct |
366 ms |
492 KB |
# of queries: 18313 |
| 21 |
Correct |
329 ms |
488 KB |
# of queries: 17132 |
| 22 |
Correct |
385 ms |
504 KB |
# of queries: 19743 |
| 23 |
Correct |
355 ms |
492 KB |
# of queries: 19837 |
| 24 |
Correct |
142 ms |
356 KB |
# of queries: 8972 |
| 25 |
Correct |
334 ms |
508 KB |
# of queries: 19697 |
| 26 |
Correct |
357 ms |
372 KB |
# of queries: 18008 |
| 27 |
Correct |
137 ms |
364 KB |
# of queries: 9063 |
| 28 |
Correct |
315 ms |
488 KB |
# of queries: 19785 |
| 29 |
Correct |
370 ms |
484 KB |
# of queries: 19675 |
| 30 |
Correct |
375 ms |
500 KB |
# of queries: 19580 |
