#include <cstdio>
#include <iostream>
#include <vector>
#include "library.h"
using namespace std;
// Query()
// Answer()
int n;
int query(vector<int> v)
{
vector<int> m(n,0);
for(int i:v) m[i]=1;
return Query(m);
}
int get(int x,vector<int> v)
{
if(v.size()==1)
{
v.push_back(x);
if(query(v)==2)
return -1;
return v[0];
}
vector<int> mm;
for(int i=0;i<v.size()/2;i++)
mm.push_back(v[i]);
int cur=query(mm);
mm.push_back(x);
if(query(mm)<=cur)
{
mm.pop_back();
return get(x,mm);
}
mm.clear();
for(int i=v.size()/2;i<v.size();i++)
mm.push_back(v[i]);
return get(x,mm);
}
vector<int> adj[1005];
vector<int> ans;
void build(int x,int pa)
{
ans.push_back(x+1);
for(int i:adj[x])
if(i!=pa) build(i,x);
}
void Solve(int N)
{
n=N;
vector<int> hv1;
for(int i=0;i<N;i++)
{
vector<int> m(N,1);
m[i]=0;
if(Query(m)==1)
hv1.push_back(i);
}
for(int i=0;i<N;i++)
{
while(true){
if(adj[i].size()==2 || (adj[i].size()==1 && (hv1[0]==i||hv1[1]==i))) break;
vector<int> ss;
for(int j=0;j<N;j++)
{
bool ok=1;
for(int k:adj[i])
ok&=(k!=j);
ok&=(i!=j);
if(ok) ss.push_back(j);
}
int x=get(i,ss);
if(x!=-1) {adj[i].push_back(x); adj[x].push_back(i);}
}
//cout << i+1 << " Found " << x+1 << endl;
}
/*for(int i=0;i<n;i++)
{
cout << i+1 << ": ";
for(int j:adj[i]) cout << j+1 << " ";
cout << endl;
}*/
for(int i=0;i<n;i++)
{
if(adj[i].size()==1)
{
build(i,-1); break;
}
}
Answer(ans);
}
Compilation message
library.cpp: In function 'int get(int, std::vector<int>)':
library.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size()/2;i++)
~^~~~~~~~~~~
library.cpp:38:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=v.size()/2;i<v.size();i++)
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
376 KB |
# of queries: 3315 |
| 2 |
Correct |
60 ms |
352 KB |
# of queries: 3291 |
| 3 |
Correct |
62 ms |
424 KB |
# of queries: 3487 |
| 4 |
Correct |
61 ms |
428 KB |
# of queries: 3477 |
| 5 |
Correct |
64 ms |
348 KB |
# of queries: 3471 |
| 6 |
Correct |
66 ms |
376 KB |
# of queries: 3485 |
| 7 |
Correct |
60 ms |
376 KB |
# of queries: 3467 |
| 8 |
Correct |
57 ms |
352 KB |
# of queries: 3321 |
| 9 |
Correct |
49 ms |
424 KB |
# of queries: 3447 |
| 10 |
Correct |
37 ms |
248 KB |
# of queries: 2049 |
| 11 |
Execution timed out |
3023 ms |
203784 KB |
Time limit exceeded |
| 12 |
Correct |
2 ms |
248 KB |
# of queries: 3 |
| 13 |
Correct |
2 ms |
248 KB |
# of queries: 7 |
| 14 |
Correct |
2 ms |
376 KB |
# of queries: 17 |
| 15 |
Correct |
5 ms |
376 KB |
# of queries: 139 |
| 16 |
Correct |
8 ms |
376 KB |
# of queries: 301 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
376 KB |
# of queries: 3315 |
| 2 |
Correct |
60 ms |
352 KB |
# of queries: 3291 |
| 3 |
Correct |
62 ms |
424 KB |
# of queries: 3487 |
| 4 |
Correct |
61 ms |
428 KB |
# of queries: 3477 |
| 5 |
Correct |
64 ms |
348 KB |
# of queries: 3471 |
| 6 |
Correct |
66 ms |
376 KB |
# of queries: 3485 |
| 7 |
Correct |
60 ms |
376 KB |
# of queries: 3467 |
| 8 |
Correct |
57 ms |
352 KB |
# of queries: 3321 |
| 9 |
Correct |
49 ms |
424 KB |
# of queries: 3447 |
| 10 |
Correct |
37 ms |
248 KB |
# of queries: 2049 |
| 11 |
Execution timed out |
3023 ms |
203784 KB |
Time limit exceeded |
| 12 |
Correct |
2 ms |
248 KB |
# of queries: 3 |
| 13 |
Correct |
2 ms |
248 KB |
# of queries: 7 |
| 14 |
Correct |
2 ms |
376 KB |
# of queries: 17 |
| 15 |
Correct |
5 ms |
376 KB |
# of queries: 139 |
| 16 |
Correct |
8 ms |
376 KB |
# of queries: 301 |
| 17 |
Runtime error |
885 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 18 |
Execution timed out |
3077 ms |
14848 KB |
Time limit exceeded |
| 19 |
Runtime error |
913 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 20 |
Execution timed out |
3034 ms |
15776 KB |
Time limit exceeded |
| 21 |
Correct |
519 ms |
508 KB |
# of queries: 19359 |
| 22 |
Runtime error |
891 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 23 |
Runtime error |
852 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 24 |
Correct |
224 ms |
344 KB |
# of queries: 10241 |
| 25 |
Execution timed out |
3080 ms |
14596 KB |
Time limit exceeded |
| 26 |
Execution timed out |
3101 ms |
17136 KB |
Time limit exceeded |
| 27 |
Correct |
221 ms |
480 KB |
# of queries: 10201 |
| 28 |
Runtime error |
834 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 29 |
Runtime error |
1216 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 30 |
Runtime error |
847 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
