#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;
int vis[1005];
void build(int x,int pa)
{
vis[x]=1;
ans.push_back(x+1);
for(int i:adj[x])
if(!vis[i]) build(i,x);
}
void Solve(int N)
{
if(N==1)
{Answer({1});return;}
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);}
else break;
}
//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 |
62 ms |
248 KB |
# of queries: 3315 |
| 2 |
Correct |
66 ms |
376 KB |
# of queries: 3291 |
| 3 |
Correct |
53 ms |
472 KB |
# of queries: 3487 |
| 4 |
Correct |
70 ms |
432 KB |
# of queries: 3477 |
| 5 |
Correct |
46 ms |
340 KB |
# of queries: 3471 |
| 6 |
Correct |
60 ms |
356 KB |
# of queries: 3485 |
| 7 |
Correct |
45 ms |
344 KB |
# of queries: 3467 |
| 8 |
Correct |
63 ms |
356 KB |
# of queries: 3321 |
| 9 |
Correct |
63 ms |
432 KB |
# of queries: 3447 |
| 10 |
Correct |
39 ms |
424 KB |
# of queries: 2049 |
| 11 |
Correct |
2 ms |
380 KB |
# of queries: 0 |
| 12 |
Correct |
2 ms |
376 KB |
# of queries: 3 |
| 13 |
Correct |
2 ms |
248 KB |
# of queries: 7 |
| 14 |
Correct |
2 ms |
376 KB |
# of queries: 17 |
| 15 |
Correct |
3 ms |
252 KB |
# of queries: 139 |
| 16 |
Correct |
5 ms |
252 KB |
# of queries: 301 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
248 KB |
# of queries: 3315 |
| 2 |
Correct |
66 ms |
376 KB |
# of queries: 3291 |
| 3 |
Correct |
53 ms |
472 KB |
# of queries: 3487 |
| 4 |
Correct |
70 ms |
432 KB |
# of queries: 3477 |
| 5 |
Correct |
46 ms |
340 KB |
# of queries: 3471 |
| 6 |
Correct |
60 ms |
356 KB |
# of queries: 3485 |
| 7 |
Correct |
45 ms |
344 KB |
# of queries: 3467 |
| 8 |
Correct |
63 ms |
356 KB |
# of queries: 3321 |
| 9 |
Correct |
63 ms |
432 KB |
# of queries: 3447 |
| 10 |
Correct |
39 ms |
424 KB |
# of queries: 2049 |
| 11 |
Correct |
2 ms |
380 KB |
# of queries: 0 |
| 12 |
Correct |
2 ms |
376 KB |
# of queries: 3 |
| 13 |
Correct |
2 ms |
248 KB |
# of queries: 7 |
| 14 |
Correct |
2 ms |
376 KB |
# of queries: 17 |
| 15 |
Correct |
3 ms |
252 KB |
# of queries: 139 |
| 16 |
Correct |
5 ms |
252 KB |
# of queries: 301 |
| 17 |
Incorrect |
603 ms |
632 KB |
Wrong Answer [3] |
| 18 |
Execution timed out |
3088 ms |
14084 KB |
Time limit exceeded |
| 19 |
Incorrect |
633 ms |
472 KB |
Wrong Answer [3] |
| 20 |
Execution timed out |
3065 ms |
15120 KB |
Time limit exceeded |
| 21 |
Correct |
536 ms |
380 KB |
# of queries: 19359 |
| 22 |
Incorrect |
583 ms |
516 KB |
Wrong Answer [3] |
| 23 |
Incorrect |
631 ms |
628 KB |
Wrong Answer [3] |
| 24 |
Correct |
235 ms |
376 KB |
# of queries: 10241 |
| 25 |
Execution timed out |
3020 ms |
13864 KB |
Time limit exceeded |
| 26 |
Execution timed out |
3074 ms |
15616 KB |
Time limit exceeded |
| 27 |
Correct |
219 ms |
376 KB |
# of queries: 10201 |
| 28 |
Incorrect |
608 ms |
568 KB |
Wrong Answer [3] |
| 29 |
Incorrect |
618 ms |
480 KB |
Wrong Answer [3] |
| 30 |
Incorrect |
606 ms |
476 KB |
Wrong Answer [3] |
