#include "library.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
using namespace std;
int query(vi x){
int num = 0;
for(int i = 0; i < x.size(); ++i) num += x[i] != 0;
if(num == 0) return 0;
return Query(x);
}
void Solve(int n)
{
vector<int> X(n);
if(n == 1){
Answer(vi{1});
return;
}
vector<vi> has(n);
vi go(n, -1);
for(int i = 0; i < n; ++i){
int l = 0, r = n - 1, fine = -1;
while(l <= r){
int mid = l+r>>1;
for(int j = 0; j < n; ++j) X[j] = (j <= mid ? 1 : 0);
for(int y: has[i]) X[y] = 0;
X[i] = 0;
int num = query(X);
X[i] = 1;
int num2 = query(X);
if(num + 1 != num2){
fine = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
if(fine == -1){
continue;
}
go[i] = fine;
has[go[i]].pb(i);
}
vector<vi> g(n);
for(int i = 0; i < n; ++i){
if(go[i] == -1) continue;
g[go[i]].pb(i);
g[i].pb(go[i]);
}
int root = 0;
for(int i = 0; i < n; ++i) if(g[i].size() == 1) root = i;
int v = root;
vi res;
res.pb(root);
int last = -1;
for(int i = 1; i < n; ++i){
if(g[v][0] == last){
last = v;
v = g[v][1];
}else{
last = v;
v = g[v][0];
}
res.pb(v);
}
// for(int x: res) cerr << x + 1 << ' ';
// cerr << '\n';
// for(int i = 1; i <= n; ++i){
// cerr << go[i - 1] << ' ';
// }
for(int &x: res) ++x;
Answer(res);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |