// ~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];
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(){
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:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 0; i < out.size(); i++)
| ~~^~~~~~~~~~~~
library.cpp: In function 'void parti()':
library.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i = 0; i < av.size(); i++)
| ~~^~~~~~~~~~~
library.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i = 0; i < av.size(); i++)
| ~~^~~~~~~~~~~
library.cpp:57:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | if(per[i] <= (av.size() - 1) / 2)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
library.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 0; i < av.size(); i++)
| ~~^~~~~~~~~~~
library.cpp:69:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | if(per[i] > (av.size() - 1) / 2)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
328 KB |
# of queries: 2623 |
| 2 |
Correct |
21 ms |
356 KB |
# of queries: 2667 |
| 3 |
Correct |
35 ms |
340 KB |
# of queries: 2846 |
| 4 |
Correct |
32 ms |
328 KB |
# of queries: 2755 |
| 5 |
Correct |
36 ms |
344 KB |
# of queries: 2819 |
| 6 |
Correct |
40 ms |
356 KB |
# of queries: 2850 |
| 7 |
Correct |
39 ms |
328 KB |
# of queries: 2721 |
| 8 |
Correct |
35 ms |
448 KB |
# of queries: 2729 |
| 9 |
Correct |
34 ms |
360 KB |
# of queries: 2741 |
| 10 |
Correct |
23 ms |
336 KB |
# of queries: 1726 |
| 11 |
Correct |
1 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: 6 |
| 15 |
Correct |
1 ms |
328 KB |
# of queries: 99 |
| 16 |
Correct |
3 ms |
328 KB |
# of queries: 213 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
328 KB |
# of queries: 2623 |
| 2 |
Correct |
21 ms |
356 KB |
# of queries: 2667 |
| 3 |
Correct |
35 ms |
340 KB |
# of queries: 2846 |
| 4 |
Correct |
32 ms |
328 KB |
# of queries: 2755 |
| 5 |
Correct |
36 ms |
344 KB |
# of queries: 2819 |
| 6 |
Correct |
40 ms |
356 KB |
# of queries: 2850 |
| 7 |
Correct |
39 ms |
328 KB |
# of queries: 2721 |
| 8 |
Correct |
35 ms |
448 KB |
# of queries: 2729 |
| 9 |
Correct |
34 ms |
360 KB |
# of queries: 2741 |
| 10 |
Correct |
23 ms |
336 KB |
# of queries: 1726 |
| 11 |
Correct |
1 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: 6 |
| 15 |
Correct |
1 ms |
328 KB |
# of queries: 99 |
| 16 |
Correct |
3 ms |
328 KB |
# of queries: 213 |
| 17 |
Correct |
314 ms |
612 KB |
# of queries: 19499 |
| 18 |
Correct |
308 ms |
448 KB |
# of queries: 19762 |
| 19 |
Runtime error |
298 ms |
376 KB |
Execution killed with signal 13 |
| 20 |
Halted |
0 ms |
0 KB |
- |
