#include "library.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
int n;
int vquery(vi v) {
vi res(n);
for(auto i : v) res[i]=1;
return Query(res);
}
void Solve(int N)
{
n=N;
vi special(n);
{
int num=0;
for(int i=0;i<n;++i) {
special[i]=1;
num++;
if(Query(special)!=num) {
special[i]=0;
num--;
}
}
}
vvi comps;
for(int i=0;i<n;++i) if(special[i]) {
comps.push_back({i});
}
auto merge = [&](vi old, vi nw) {
if(vquery({old[0],nw[0]})!=1) {
reverse(all(old));
}
reverse(all(nw));
nw.insert(nw.end(),all(old));
return nw;
};
auto addCmp = [&]( vi cmp) {
auto check = [&](int i) {
vi res(n);
for(auto& v : cmp) res[v]=1;
for(int j=0;j<=i;++j) {
for(auto v : comps[j]) res[v]=1;
}
return Query(res);
};
if(check(comps.size()-1)>comps.size()) {
return cmp;
}
int l = 0, r = comps.size()-1;
while(l<r) {
int mid = (l+r)/2;
// check prefix, what then?
// if found component, check on which side
// merge it.
// remove this component for now,
// add it back.
if(check(mid)>mid+1) {
l = mid+1;
} else {
r = mid;
}
}
// found place to insert
auto old = comps[l];
comps.erase(comps.begin()+l);
return merge(old,cmp);
};
for(int i=0;i<n;++i) if(!special[i]) {
vi cmp = {i};
// find where it belongs
cmp = addCmp(cmp);
cmp = addCmp(cmp);
comps.push_back(cmp);
}
assert(comps.size()==1);
for(auto& i : comps[0]) ++i;
Answer(comps[0]);
}
Compilation message
library.cpp: In lambda function:
library.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | if(check(comps.size()-1)>comps.size()) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
208 KB |
# of queries: 1597 |
| 2 |
Correct |
19 ms |
288 KB |
# of queries: 1579 |
| 3 |
Correct |
21 ms |
292 KB |
# of queries: 1677 |
| 4 |
Correct |
22 ms |
336 KB |
# of queries: 1658 |
| 5 |
Correct |
31 ms |
284 KB |
# of queries: 1660 |
| 6 |
Correct |
28 ms |
296 KB |
# of queries: 1665 |
| 7 |
Correct |
20 ms |
288 KB |
# of queries: 1666 |
| 8 |
Correct |
18 ms |
288 KB |
# of queries: 1593 |
| 9 |
Correct |
17 ms |
208 KB |
# of queries: 1650 |
| 10 |
Correct |
14 ms |
288 KB |
# of queries: 995 |
| 11 |
Correct |
0 ms |
208 KB |
# of queries: 1 |
| 12 |
Correct |
1 ms |
212 KB |
# of queries: 5 |
| 13 |
Correct |
1 ms |
208 KB |
# of queries: 9 |
| 14 |
Correct |
1 ms |
208 KB |
# of queries: 12 |
| 15 |
Correct |
1 ms |
208 KB |
# of queries: 73 |
| 16 |
Correct |
2 ms |
300 KB |
# of queries: 152 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
208 KB |
# of queries: 1597 |
| 2 |
Correct |
19 ms |
288 KB |
# of queries: 1579 |
| 3 |
Correct |
21 ms |
292 KB |
# of queries: 1677 |
| 4 |
Correct |
22 ms |
336 KB |
# of queries: 1658 |
| 5 |
Correct |
31 ms |
284 KB |
# of queries: 1660 |
| 6 |
Correct |
28 ms |
296 KB |
# of queries: 1665 |
| 7 |
Correct |
20 ms |
288 KB |
# of queries: 1666 |
| 8 |
Correct |
18 ms |
288 KB |
# of queries: 1593 |
| 9 |
Correct |
17 ms |
208 KB |
# of queries: 1650 |
| 10 |
Correct |
14 ms |
288 KB |
# of queries: 995 |
| 11 |
Correct |
0 ms |
208 KB |
# of queries: 1 |
| 12 |
Correct |
1 ms |
212 KB |
# of queries: 5 |
| 13 |
Correct |
1 ms |
208 KB |
# of queries: 9 |
| 14 |
Correct |
1 ms |
208 KB |
# of queries: 12 |
| 15 |
Correct |
1 ms |
208 KB |
# of queries: 73 |
| 16 |
Correct |
2 ms |
300 KB |
# of queries: 152 |
| 17 |
Correct |
176 ms |
320 KB |
# of queries: 10618 |
| 18 |
Correct |
171 ms |
320 KB |
# of queries: 10484 |
| 19 |
Correct |
162 ms |
440 KB |
# of queries: 10621 |
| 20 |
Correct |
152 ms |
316 KB |
# of queries: 9949 |
| 21 |
Correct |
172 ms |
316 KB |
# of queries: 9335 |
| 22 |
Correct |
156 ms |
332 KB |
# of queries: 10639 |
| 23 |
Correct |
121 ms |
316 KB |
# of queries: 10651 |
| 24 |
Correct |
59 ms |
296 KB |
# of queries: 4956 |
| 25 |
Correct |
147 ms |
312 KB |
# of queries: 10380 |
| 26 |
Correct |
156 ms |
428 KB |
# of queries: 9719 |
| 27 |
Correct |
68 ms |
312 KB |
# of queries: 4961 |
| 28 |
Correct |
157 ms |
628 KB |
# of queries: 10479 |
| 29 |
Correct |
123 ms |
400 KB |
# of queries: 10475 |
| 30 |
Correct |
152 ms |
448 KB |
# of queries: 10479 |
