// ~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;
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) exit(0);
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(){
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;
}
//*
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();
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();
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:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 0; i < out.size(); i++)
| ~~^~~~~~~~~~~~
library.cpp: In function 'void parti()':
library.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i = 0; i < av.size(); i++)
| ~~^~~~~~~~~~~
library.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i = 0; i < av.size(); i++)
| ~~^~~~~~~~~~~
library.cpp:60:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | if(per[i] <= (av.size() - 1) / 2)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
library.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i = 0; i < av.size(); i++)
| ~~^~~~~~~~~~~
library.cpp:72:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if(per[i] > (av.size() - 1) / 2)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
328 KB |
# of queries: 2796 |
| 2 |
Correct |
22 ms |
356 KB |
# of queries: 2764 |
| 3 |
Correct |
47 ms |
328 KB |
# of queries: 2941 |
| 4 |
Correct |
43 ms |
328 KB |
# of queries: 2782 |
| 5 |
Correct |
38 ms |
360 KB |
# of queries: 2754 |
| 6 |
Correct |
35 ms |
352 KB |
# of queries: 2760 |
| 7 |
Correct |
41 ms |
328 KB |
# of queries: 2955 |
| 8 |
Correct |
41 ms |
468 KB |
# of queries: 2686 |
| 9 |
Correct |
32 ms |
340 KB |
# of queries: 2744 |
| 10 |
Correct |
22 ms |
328 KB |
# of queries: 1852 |
| 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: 5 |
| 15 |
Correct |
3 ms |
328 KB |
# of queries: 90 |
| 16 |
Correct |
2 ms |
328 KB |
# of queries: 165 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
328 KB |
# of queries: 2796 |
| 2 |
Correct |
22 ms |
356 KB |
# of queries: 2764 |
| 3 |
Correct |
47 ms |
328 KB |
# of queries: 2941 |
| 4 |
Correct |
43 ms |
328 KB |
# of queries: 2782 |
| 5 |
Correct |
38 ms |
360 KB |
# of queries: 2754 |
| 6 |
Correct |
35 ms |
352 KB |
# of queries: 2760 |
| 7 |
Correct |
41 ms |
328 KB |
# of queries: 2955 |
| 8 |
Correct |
41 ms |
468 KB |
# of queries: 2686 |
| 9 |
Correct |
32 ms |
340 KB |
# of queries: 2744 |
| 10 |
Correct |
22 ms |
328 KB |
# of queries: 1852 |
| 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: 5 |
| 15 |
Correct |
3 ms |
328 KB |
# of queries: 90 |
| 16 |
Correct |
2 ms |
328 KB |
# of queries: 165 |
| 17 |
Correct |
319 ms |
380 KB |
# of queries: 19778 |
| 18 |
Correct |
326 ms |
364 KB |
# of queries: 19317 |
| 19 |
Correct |
431 ms |
476 KB |
# of queries: 19730 |
| 20 |
Correct |
212 ms |
456 KB |
# of queries: 18260 |
| 21 |
Correct |
335 ms |
496 KB |
# of queries: 16821 |
| 22 |
Correct |
347 ms |
500 KB |
# of queries: 19988 |
| 23 |
Correct |
359 ms |
480 KB |
# of queries: 19878 |
| 24 |
Correct |
149 ms |
364 KB |
# of queries: 8929 |
| 25 |
Correct |
351 ms |
492 KB |
# of queries: 19198 |
| 26 |
Correct |
300 ms |
504 KB |
# of queries: 17829 |
| 27 |
Correct |
140 ms |
356 KB |
# of queries: 8893 |
| 28 |
Correct |
379 ms |
500 KB |
# of queries: 19821 |
| 29 |
Runtime error |
343 ms |
376 KB |
Execution killed with signal 13 |
| 30 |
Halted |
0 ms |
0 KB |
- |
