// ~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 |
39 ms |
344 KB |
# of queries: 2635 |
| 2 |
Correct |
31 ms |
352 KB |
# of queries: 2643 |
| 3 |
Correct |
33 ms |
356 KB |
# of queries: 2871 |
| 4 |
Correct |
34 ms |
328 KB |
# of queries: 2753 |
| 5 |
Correct |
41 ms |
336 KB |
# of queries: 2892 |
| 6 |
Correct |
37 ms |
340 KB |
# of queries: 2987 |
| 7 |
Correct |
39 ms |
336 KB |
# of queries: 2841 |
| 8 |
Correct |
24 ms |
448 KB |
# of queries: 2642 |
| 9 |
Correct |
40 ms |
332 KB |
# of queries: 2765 |
| 10 |
Correct |
13 ms |
352 KB |
# of queries: 1684 |
| 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: 109 |
| 16 |
Correct |
2 ms |
328 KB |
# of queries: 195 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
344 KB |
# of queries: 2635 |
| 2 |
Correct |
31 ms |
352 KB |
# of queries: 2643 |
| 3 |
Correct |
33 ms |
356 KB |
# of queries: 2871 |
| 4 |
Correct |
34 ms |
328 KB |
# of queries: 2753 |
| 5 |
Correct |
41 ms |
336 KB |
# of queries: 2892 |
| 6 |
Correct |
37 ms |
340 KB |
# of queries: 2987 |
| 7 |
Correct |
39 ms |
336 KB |
# of queries: 2841 |
| 8 |
Correct |
24 ms |
448 KB |
# of queries: 2642 |
| 9 |
Correct |
40 ms |
332 KB |
# of queries: 2765 |
| 10 |
Correct |
13 ms |
352 KB |
# of queries: 1684 |
| 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: 109 |
| 16 |
Correct |
2 ms |
328 KB |
# of queries: 195 |
| 17 |
Correct |
378 ms |
352 KB |
# of queries: 19821 |
| 18 |
Correct |
283 ms |
484 KB |
# of queries: 19719 |
| 19 |
Incorrect |
313 ms |
608 KB |
Unexpected end of file - token expected |
| 20 |
Halted |
0 ms |
0 KB |
- |
