#include <bits/stdc++.h>
#include <cassert>
#include "library.h"
using namespace std;
typedef int ll;
vector<ll> asdf;
vector<ll> chk;
vector<ll> p, e, memo;
vector<ll> rs, s;
ll n;
void randp(ll N) {
p.clear();
p.resize(N);
ll i;
for (i = 0; i < N; i++) p[i] = i + 1;
for (i = N - 1; i >= 1; i--) {
if ((rand() % (i + 1))) {
ll a;
a = rand() % i;
swap(p[i], p[a]);
}
}
}
ll cnt = 0;
ll query(vector<ll> v) {
ll i;
for (i = 0; i < v.size(); i++) v[i] = s[v[i]];
cnt++;
vector<ll> a;
a.resize(n);
for (auto x : v) a[x - 1] = 1;
return Query(a);
}
void Solve(int N) {
n = N;
s.resize(1);
rs.resize(N + 1);
randp(N);
for (auto x : p) s.push_back(x);
srand(time(NULL));
chk.resize(N + 1);
ll i, a;
for (i = 1; i <= N; i++) rs[s[i]] = i;
ll sz = N;
while (1) {
asdf.clear();
for (ll i = 1; i <= N; i++) if (!chk[i]) asdf.push_back(i);
sz = asdf.size();
if (!sz) break;
if (asdf.size() <= 2) {
e.push_back(asdf[0]);
chk[asdf[0]] = 1;
continue;
}
vector<ll> q1, q2;
if (memo.empty()) {
do {
randp(sz);
q1.clear();
q2.clear();
for (i = 0; i < sz; i++) {
if (p[i] <= sz / 2) q1.push_back(asdf[i]);
else q2.push_back(asdf[i]);
}
} while ((query(q1) + query(q2)) % 2);
//memo = q2;
}
else {
vector<ll> aasdf;
aasdf.resize(N + 1);
for (i = 1; i <= N; i++) aasdf[i] = chk[i];
for (auto x : memo) aasdf[x] = 1;
q1 = memo;
for (i = 1; i <= N; i++) if (!aasdf[i]) q2.push_back(i);
memo.clear();
}
ll l, r;
l = 0, r = q1.size() - 1;
vector<ll> v1, v2;
while (l < r) {
v1 = q1;
v2 = q2;
ll mid = (l + r) / 2;
for (ll k = mid + 1; k < q1.size(); k++) v2.push_back(v1[k]);
for (ll k = mid + 1; k < q1.size(); k++) v1.pop_back();
if ((query(v1) + query(v2)) % 2) l = mid + 1;
else r = mid;
}
e.push_back(q1[r]);
chk[q1[r]] = 1;
swap(q1, q2);
l = 0, r = q1.size() - 1;
v1.clear();
v2.clear();
while (l < r) {
v1 = q1;
v2 = q2;
ll mid = (l + r) / 2;
for (ll k = mid + 1; k < q1.size(); k++) v2.push_back(v1[k]);
for (ll k = mid + 1; k < q1.size(); k++) v1.pop_back();
if ((query(v1) + query(v2)) % 2) l = mid + 1;
else r = mid;
}
e.push_back(q1[r]);
chk[q1[r]] = 1;
}
deque<ll> d;
for (i = N - 1; i >= 0; i--) {
if (d.empty()) {
d.push_back(e[i]);
continue;
}
ll b = d.back();
vector<ll> v;
v.push_back(b);
v.push_back(e[i]);
if (query(v) == 1) d.push_back(e[i]);
else d.push_front(e[i]);
}
vector<ll> ans;
while (!d.empty()) {
ans.push_back(d.back());
d.pop_back();
}
for (i = 0; i < N; i++) ans[i] = s[ans[i]];
Answer(ans);
}
Compilation message
library.cpp: In function 'll query(std::vector<int>)':
library.cpp:31:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (i = 0; i < v.size(); i++) v[i] = s[v[i]];
| ~~^~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:89:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (ll k = mid + 1; k < q1.size(); k++) v2.push_back(v1[k]);
| ~~^~~~~~~~~~~
library.cpp:90:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (ll k = mid + 1; k < q1.size(); k++) v1.pop_back();
| ~~^~~~~~~~~~~
library.cpp:105:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (ll k = mid + 1; k < q1.size(); k++) v2.push_back(v1[k]);
| ~~^~~~~~~~~~~
library.cpp:106:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for (ll k = mid + 1; k < q1.size(); k++) v1.pop_back();
| ~~^~~~~~~~~~~
library.cpp:47:8: warning: unused variable 'a' [-Wunused-variable]
47 | ll i, a;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
200 KB |
# of queries: 2589 |
| 2 |
Correct |
49 ms |
200 KB |
# of queries: 2522 |
| 3 |
Correct |
49 ms |
432 KB |
# of queries: 2671 |
| 4 |
Correct |
52 ms |
432 KB |
# of queries: 2713 |
| 5 |
Correct |
42 ms |
304 KB |
# of queries: 2751 |
| 6 |
Correct |
58 ms |
316 KB |
# of queries: 2735 |
| 7 |
Correct |
54 ms |
432 KB |
# of queries: 2673 |
| 8 |
Correct |
53 ms |
304 KB |
# of queries: 2624 |
| 9 |
Correct |
56 ms |
320 KB |
# of queries: 2716 |
| 10 |
Correct |
25 ms |
200 KB |
# of queries: 1620 |
| 11 |
Correct |
0 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
200 KB |
# of queries: 1 |
| 13 |
Correct |
1 ms |
200 KB |
# of queries: 6 |
| 14 |
Correct |
1 ms |
200 KB |
# of queries: 9 |
| 15 |
Correct |
2 ms |
200 KB |
# of queries: 90 |
| 16 |
Correct |
4 ms |
200 KB |
# of queries: 206 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
200 KB |
# of queries: 2589 |
| 2 |
Correct |
49 ms |
200 KB |
# of queries: 2522 |
| 3 |
Correct |
49 ms |
432 KB |
# of queries: 2671 |
| 4 |
Correct |
52 ms |
432 KB |
# of queries: 2713 |
| 5 |
Correct |
42 ms |
304 KB |
# of queries: 2751 |
| 6 |
Correct |
58 ms |
316 KB |
# of queries: 2735 |
| 7 |
Correct |
54 ms |
432 KB |
# of queries: 2673 |
| 8 |
Correct |
53 ms |
304 KB |
# of queries: 2624 |
| 9 |
Correct |
56 ms |
320 KB |
# of queries: 2716 |
| 10 |
Correct |
25 ms |
200 KB |
# of queries: 1620 |
| 11 |
Correct |
0 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
200 KB |
# of queries: 1 |
| 13 |
Correct |
1 ms |
200 KB |
# of queries: 6 |
| 14 |
Correct |
1 ms |
200 KB |
# of queries: 9 |
| 15 |
Correct |
2 ms |
200 KB |
# of queries: 90 |
| 16 |
Correct |
4 ms |
200 KB |
# of queries: 206 |
| 17 |
Correct |
606 ms |
472 KB |
# of queries: 18119 |
| 18 |
Correct |
609 ms |
480 KB |
# of queries: 17970 |
| 19 |
Correct |
564 ms |
600 KB |
# of queries: 18161 |
| 20 |
Correct |
549 ms |
616 KB |
# of queries: 16945 |
| 21 |
Correct |
488 ms |
492 KB |
# of queries: 15956 |
| 22 |
Correct |
577 ms |
456 KB |
# of queries: 18299 |
| 23 |
Correct |
615 ms |
704 KB |
# of queries: 18188 |
| 24 |
Correct |
214 ms |
464 KB |
# of queries: 8328 |
| 25 |
Correct |
537 ms |
480 KB |
# of queries: 17738 |
| 26 |
Correct |
529 ms |
604 KB |
# of queries: 16474 |
| 27 |
Correct |
228 ms |
352 KB |
# of queries: 8248 |
| 28 |
Correct |
575 ms |
596 KB |
# of queries: 18221 |
| 29 |
Correct |
609 ms |
448 KB |
# of queries: 18148 |
| 30 |
Correct |
615 ms |
332 KB |
# of queries: 18197 |
