#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int n,x,y;
void search(vector<int> &st, vector<int>&rest, int r){
if(st.size() == 1){
if(x==-1) x=st[0];
else y=st[0];
return;
}
vector<int> v1(n,0),v2(n,0);
int m = st.size() / 2;
for(int i=0;i<m;i++){
v1[st[i]]=1;
}
for(int i=m;i<st.size();i++){
v2[st[i]]=1;
}
for(int i : rest) v2[i]=1;
int a1 = Query(v1), a2 = Query(v2);
if(r==2){
if(a1 == a2){
vector<int> n1, n2, rest1=rest, rest2=rest;
for(int i= 0;i<m;i++){
n1.push_back(st[i]); rest2.push_back(st[i]);
}
for(int i=m;i<st.size();i++){
n2.push_back(st[i]); rest1.push_back(st[i]);
}
search(n1,rest1,1);
search(n2,rest2,1);
}
else if(a2 > a1){
vector<int> st0;
for(int i= 0;i<m;i++) rest.push_back(st[i]);
for(int i=m;i<st.size();i++) st0.push_back(st[i]);
search(st0,rest,2);
}
else{
vector<int> st0;
for(int i= 0;i<m;i++) st0.push_back(st[i]);
for(int i=m;i<st.size();i++) rest.push_back(st[i]);
search(st0,rest,2);
}
}
else{
if(a1 >= a2){
vector<int> st0;
for(int i= 0;i<m;i++) st0.push_back(st[i]);
for(int i=m;i<st.size();i++) rest.push_back(st[i]);
search(st0,rest,1);
}
else{
vector<int> st0;
for(int i= 0;i<m;i++) rest.push_back(st[i]);
for(int i=m;i<st.size();i++) st0.push_back(st[i]);
search(st0,rest,1);
}
}
}
void Solve(int N){
n=N;
set<int> st;
for(int i = 0; i<n;i++) st.insert(i);
vector<int> res(n);
while(st.size() > 1){
x=y=-1;
vector<int> vec,rest;
for(int i : st) vec.push_back(i);
search(vec,rest,2);
if(st.size() == n){
res[0] = x;
res[n-1] = y;
}
else{
int u = (n - st.size()) / 2;
vector<int> m(n,0); m[x]=1; m[res[u-1]]=1;
if(Query(m) == 1){
res[u]=x; res[n-u-1]=y;
}
else{
res[u]=y; res[n-u-1]=x;
}
}
st.erase(st.find(x));
st.erase(st.find(y));
}
if(st.size() == 1) res[n/2] = *st.begin();
for(int&i:res)i++;
Answer(res);
}
Compilation message
library.cpp: In function 'void search(std::vector<int>&, std::vector<int>&, int)':
library.cpp:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i=m;i<st.size();i++){
| ~^~~~~~~~~~
library.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i=m;i<st.size();i++){
| ~^~~~~~~~~~
library.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i=m;i<st.size();i++) st0.push_back(st[i]);
| ~^~~~~~~~~~
library.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=m;i<st.size();i++) rest.push_back(st[i]);
| ~^~~~~~~~~~
library.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=m;i<st.size();i++) rest.push_back(st[i]);
| ~^~~~~~~~~~
library.cpp:56:26: 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=m;i<st.size();i++) st0.push_back(st[i]);
| ~^~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:72:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | if(st.size() == n){
| ~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
972 KB |
# of queries: 2109 |
| 2 |
Correct |
17 ms |
968 KB |
# of queries: 2122 |
| 3 |
Correct |
17 ms |
964 KB |
# of queries: 2249 |
| 4 |
Correct |
21 ms |
1224 KB |
# of queries: 2217 |
| 5 |
Correct |
21 ms |
488 KB |
# of queries: 2225 |
| 6 |
Correct |
18 ms |
720 KB |
# of queries: 2231 |
| 7 |
Correct |
20 ms |
1220 KB |
# of queries: 2223 |
| 8 |
Correct |
21 ms |
956 KB |
# of queries: 2177 |
| 9 |
Correct |
21 ms |
948 KB |
# of queries: 2218 |
| 10 |
Correct |
10 ms |
700 KB |
# of queries: 1263 |
| 11 |
Correct |
0 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
344 KB |
# of queries: 2 |
| 13 |
Correct |
0 ms |
596 KB |
# of queries: 4 |
| 14 |
Correct |
0 ms |
344 KB |
# of queries: 9 |
| 15 |
Correct |
1 ms |
440 KB |
# of queries: 66 |
| 16 |
Correct |
1 ms |
344 KB |
# of queries: 152 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
972 KB |
# of queries: 2109 |
| 2 |
Correct |
17 ms |
968 KB |
# of queries: 2122 |
| 3 |
Correct |
17 ms |
964 KB |
# of queries: 2249 |
| 4 |
Correct |
21 ms |
1224 KB |
# of queries: 2217 |
| 5 |
Correct |
21 ms |
488 KB |
# of queries: 2225 |
| 6 |
Correct |
18 ms |
720 KB |
# of queries: 2231 |
| 7 |
Correct |
20 ms |
1220 KB |
# of queries: 2223 |
| 8 |
Correct |
21 ms |
956 KB |
# of queries: 2177 |
| 9 |
Correct |
21 ms |
948 KB |
# of queries: 2218 |
| 10 |
Correct |
10 ms |
700 KB |
# of queries: 1263 |
| 11 |
Correct |
0 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
344 KB |
# of queries: 2 |
| 13 |
Correct |
0 ms |
596 KB |
# of queries: 4 |
| 14 |
Correct |
0 ms |
344 KB |
# of queries: 9 |
| 15 |
Correct |
1 ms |
440 KB |
# of queries: 66 |
| 16 |
Correct |
1 ms |
344 KB |
# of queries: 152 |
| 17 |
Correct |
250 ms |
828 KB |
# of queries: 15803 |
| 18 |
Correct |
241 ms |
836 KB |
# of queries: 15561 |
| 19 |
Correct |
253 ms |
576 KB |
# of queries: 15717 |
| 20 |
Correct |
224 ms |
816 KB |
# of queries: 14690 |
| 21 |
Correct |
217 ms |
580 KB |
# of queries: 13725 |
| 22 |
Correct |
262 ms |
764 KB |
# of queries: 15715 |
| 23 |
Correct |
259 ms |
828 KB |
# of queries: 15838 |
| 24 |
Correct |
81 ms |
732 KB |
# of queries: 7109 |
| 25 |
Correct |
232 ms |
744 KB |
# of queries: 15338 |
| 26 |
Correct |
208 ms |
1016 KB |
# of queries: 14214 |
| 27 |
Correct |
73 ms |
752 KB |
# of queries: 7044 |
| 28 |
Correct |
257 ms |
504 KB |
# of queries: 16473 |
| 29 |
Correct |
265 ms |
508 KB |
# of queries: 16454 |
| 30 |
Correct |
251 ms |
500 KB |
# of queries: 16473 |
