#include <bits/stdc++.h>
#include "library.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b){a = b; return true;}
return false;
}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b){a = b; return true;}
return false;
}
template <class T>
void printArr(T& a, string separator = " ", string finish = "\n"){
for(auto i: a) cout << i << separator;
cout << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
// namespace Interactor{
// int n;
// vector<int> perm, pos, ans;
// int Query(vector<bool> a){
// // cout << "? "; printArr(a);
// vector<bool> ligma(n+2);
// for(int i=0; i<n; ++i) ligma[pos[i]] = a[i];
// int cnt = 0;
// for(int i = 0; i<=n; ++i) if (ligma[i] == 0 && ligma[i+1] == 1) cnt++;
// // cout << "-> " << cnt << "\n";
// return cnt;
// }
// void Answer(vector<int> a){
// ans = a;
// }
void merge_arr(vector<int> &a, vector<int> b){
for(int i: b) a.push_back(i);
}
void Solve(int n){
vector<vector<int>> sigma(n);
for(int i = 0; i<n; ++i) sigma[i].push_back(i);
for(int i = n-1; i>=0; --i){
int iteration = 2;
while(iteration--){
int l = i + 1, r = sigma.size();
while(l < r){
int mid = (l + r) >> 1;
vector<int> S = sigma[i];
for(int j = i+1; j<=mid; ++j) merge_arr(S, sigma[j]);
vector<int> card(n);
for(int j: S) card[j] = true;
if (Query(card) < mid - i + 1) r = mid;
else l = mid + 1;
}
if (l == sigma.size()) break;
bool found = false;
for(int x = 0; x <= 1; ++x) for(int y = 0; y<=1; ++y) if (!found) {
vector<int> card(n);
if (x == 0) card[sigma[i][0]] = 1;
else card[sigma[i].back()] = 1;
if (y == 0) card[sigma[l][0]] = 1;
else card[sigma[l].back()] = 1;
if (Query(card) == 1){
if (!x) reverse(ALL(sigma[i]));
if (y) reverse(ALL(sigma[l]));
found = true;
break;
}
}
merge_arr(sigma[i], sigma[l]);
sigma.erase(sigma.begin() + l);
}
}
vector<int> ans = sigma[0];
if (ans.size() != n) exit(1);
for(int &i: ans) i++;
Answer(ans);
}
// bool solve(int _n){
// n = _n;
// perm.resize(n); ans.clear();
// for(int i = 0; i<n; ++i) perm[i] = i + 1;
// shuffle(ALL(perm), rng);
// pos.resize(n);
// for(int i = 0; i<n; ++i) pos[perm[i]-1] = i+1;
// Solve(n);
// if (ans != perm) reverse(ALL(ans));
// return ans == perm;
// }
// }
// int main(void){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// int n = 5;
// bool verdict = Interactor::solve(n);
// if (verdict) cout << "AC\n";
// else cout << "WA\n";
// return 0;
// }
Compilation message
library.cpp: In function 'void Solve(int)':
library.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | if (l == sigma.size()) break;
| ~~^~~~~~~~~~~~~~~
library.cpp:112:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
112 | if (ans.size() != n) exit(1);
| ~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
456 KB |
# of queries: 1734 |
| 2 |
Correct |
16 ms |
456 KB |
# of queries: 1778 |
| 3 |
Correct |
15 ms |
712 KB |
# of queries: 1850 |
| 4 |
Correct |
16 ms |
704 KB |
# of queries: 1864 |
| 5 |
Correct |
14 ms |
956 KB |
# of queries: 1836 |
| 6 |
Correct |
18 ms |
700 KB |
# of queries: 1887 |
| 7 |
Correct |
15 ms |
1216 KB |
# of queries: 1868 |
| 8 |
Correct |
18 ms |
704 KB |
# of queries: 1781 |
| 9 |
Correct |
18 ms |
944 KB |
# of queries: 1864 |
| 10 |
Correct |
11 ms |
704 KB |
# of queries: 1073 |
| 11 |
Correct |
0 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
344 KB |
# of queries: 2 |
| 13 |
Correct |
0 ms |
344 KB |
# of queries: 6 |
| 14 |
Correct |
1 ms |
344 KB |
# of queries: 8 |
| 15 |
Correct |
1 ms |
344 KB |
# of queries: 58 |
| 16 |
Correct |
1 ms |
444 KB |
# of queries: 147 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
456 KB |
# of queries: 1734 |
| 2 |
Correct |
16 ms |
456 KB |
# of queries: 1778 |
| 3 |
Correct |
15 ms |
712 KB |
# of queries: 1850 |
| 4 |
Correct |
16 ms |
704 KB |
# of queries: 1864 |
| 5 |
Correct |
14 ms |
956 KB |
# of queries: 1836 |
| 6 |
Correct |
18 ms |
700 KB |
# of queries: 1887 |
| 7 |
Correct |
15 ms |
1216 KB |
# of queries: 1868 |
| 8 |
Correct |
18 ms |
704 KB |
# of queries: 1781 |
| 9 |
Correct |
18 ms |
944 KB |
# of queries: 1864 |
| 10 |
Correct |
11 ms |
704 KB |
# of queries: 1073 |
| 11 |
Correct |
0 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
344 KB |
# of queries: 2 |
| 13 |
Correct |
0 ms |
344 KB |
# of queries: 6 |
| 14 |
Correct |
1 ms |
344 KB |
# of queries: 8 |
| 15 |
Correct |
1 ms |
344 KB |
# of queries: 58 |
| 16 |
Correct |
1 ms |
444 KB |
# of queries: 147 |
| 17 |
Correct |
178 ms |
732 KB |
# of queries: 12894 |
| 18 |
Correct |
168 ms |
752 KB |
# of queries: 12769 |
| 19 |
Correct |
178 ms |
748 KB |
# of queries: 12718 |
| 20 |
Correct |
173 ms |
496 KB |
# of queries: 11974 |
| 21 |
Correct |
144 ms |
1012 KB |
# of queries: 11347 |
| 22 |
Correct |
183 ms |
740 KB |
# of queries: 12901 |
| 23 |
Correct |
166 ms |
1004 KB |
# of queries: 12865 |
| 24 |
Correct |
65 ms |
1216 KB |
# of queries: 5837 |
| 25 |
Correct |
185 ms |
1020 KB |
# of queries: 12591 |
| 26 |
Correct |
154 ms |
740 KB |
# of queries: 11723 |
| 27 |
Correct |
53 ms |
712 KB |
# of queries: 5803 |
| 28 |
Correct |
21 ms |
1020 KB |
# of queries: 1998 |
| 29 |
Correct |
22 ms |
1532 KB |
# of queries: 1996 |
| 30 |
Correct |
26 ms |
1532 KB |
# of queries: 1998 |
