| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1225232 | ansori | Library (JOI18_library) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include<library.h>
using namespace std;
int n;
int Query(const std::vector<int>& M);
void Answer(const std::vector<int>& res);
int ask(vector<int> v){
vector<int> q(n , 0);
for(auto to : v) q[to - 1] = 1;
// for(auto to : q) cout << to << ' ';
// cout << '\n';
return Query(q);
}
void Solve(int N)
{
n = N;
vector<int> ans;
vector<deque<int>> b;
for(int i = 1;i <= n; ++ i){
vector<int> q;
for(int j = 1;j <= i; ++ j) q.push_back(j);
int y = ask(q);
//cout << y << ' ';
if(y == b.size() + 1){
b.push_back({i});
continue ;
}
int l = -1;
int r = b.size() - 1;
while(l + 1 < r){
int mid = (l + r) / 2;
vector<int> f;
for(int j = 0;j <= mid; ++ j){
for(auto to : b[j]) f.push_back(to);
}
f.push_back(i);
if(ask(f) <= mid + 1) r = mid;
else l = mid;
}
int p = r;
vector<int> qu = {b[p].back() , i};
if(ask(qu) == 1) b[p].push_back(i);
else b[p].push_front(i);
if(y == b.size()) continue ;
deque<int> qq = b[p];
//for(auto to : qq) cout << to << ' ';
b.erase(b.begin() + p , b.begin() + p + 1);
l = 0;
r = b.size() - 1;
while(l + 1 < r){
int mid = (l + r) / 2;
vector<int> f;
for(int j = 0;j <= mid; ++ j){
for(auto to : b[j]) f.push_back(to);
}
for(auto to : qq) f.push_back(to);
if(ask(f) <= mid + 1) r = mid;
else l = mid;
}
//for(auto to : b[r]) cout << to << ' ';
qu = {qq.back() , b[r].front() , b[r].back()};
if(ask(qu) == 1){
if(ask({qq.back() , b[r].front()}) == 1) reverse(qq.begin() , qq.end());
for(auto to : qq) b[r].push_front(to);
}
else{
if(ask({b[r].back() , qq.back()}) == 1) reverse(qq.begin() , qq.end());
for(auto to : qq) b[r].push_back(to);
}
}
// cout << '\n';
for(auto to : b[0]) ans.push_back(to);
// for(auto to : ans) cout << to << ' ';
Answer(ans);
}