// ~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 wrong = 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) 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 == 1000){
cout << 1 / 0 << endl;
return;
}
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:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i = 0; i < out.size(); i++)
| ~~^~~~~~~~~~~~
library.cpp: In function 'void parti()':
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: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:61:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | if(per[i] <= (av.size() - 1) / 2)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
library.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 0; i < av.size(); i++)
| ~~^~~~~~~~~~~
library.cpp:73:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if(per[i] > (av.size() - 1) / 2)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:111:13: warning: division by zero [-Wdiv-by-zero]
111 | cout << 1 / 0 << endl;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
360 KB |
# of queries: 2669 |
| 2 |
Correct |
35 ms |
356 KB |
# of queries: 2706 |
| 3 |
Correct |
32 ms |
336 KB |
# of queries: 2621 |
| 4 |
Correct |
41 ms |
448 KB |
# of queries: 2786 |
| 5 |
Correct |
36 ms |
356 KB |
# of queries: 2901 |
| 6 |
Correct |
36 ms |
336 KB |
# of queries: 2866 |
| 7 |
Correct |
46 ms |
348 KB |
# of queries: 2665 |
| 8 |
Correct |
34 ms |
356 KB |
# of queries: 2612 |
| 9 |
Correct |
51 ms |
340 KB |
# of queries: 2799 |
| 10 |
Correct |
22 ms |
328 KB |
# of queries: 1675 |
| 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: 7 |
| 15 |
Correct |
2 ms |
328 KB |
# of queries: 100 |
| 16 |
Correct |
4 ms |
328 KB |
# of queries: 247 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
360 KB |
# of queries: 2669 |
| 2 |
Correct |
35 ms |
356 KB |
# of queries: 2706 |
| 3 |
Correct |
32 ms |
336 KB |
# of queries: 2621 |
| 4 |
Correct |
41 ms |
448 KB |
# of queries: 2786 |
| 5 |
Correct |
36 ms |
356 KB |
# of queries: 2901 |
| 6 |
Correct |
36 ms |
336 KB |
# of queries: 2866 |
| 7 |
Correct |
46 ms |
348 KB |
# of queries: 2665 |
| 8 |
Correct |
34 ms |
356 KB |
# of queries: 2612 |
| 9 |
Correct |
51 ms |
340 KB |
# of queries: 2799 |
| 10 |
Correct |
22 ms |
328 KB |
# of queries: 1675 |
| 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: 7 |
| 15 |
Correct |
2 ms |
328 KB |
# of queries: 100 |
| 16 |
Correct |
4 ms |
328 KB |
# of queries: 247 |
| 17 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 4 |
| 18 |
Halted |
0 ms |
0 KB |
- |
