#include <bits/stdc++.h>
using namespace std;
#include "library.h"
int _N;
int Query(int l, int r, vector<int> include, vector<int> exclude){
vector<int> v(r - l + 1);
for (int i = 0; i <= r - l; i++) v[i] = l+i;
for (auto i: include) v.push_back(i);
for (auto i: exclude){
if (v.empty()) return 0;
int pos = -1;
for (int j = 0; j < (int)v.size(); j++){
if (v[j] == i) pos = j;
}
if (pos >= 0) v.erase(v.begin() + pos);
}
vector<int> qr(_N, 0);
if (v.empty()) return 0;
for (auto i: v) qr[i-1] = 1;
return Query(qr);
}
void Solve(int N){
_N = N;
vector<vector<int>> adj(N+1);
map<pair<int, int>, int> cache;
for (int i = 1; i <= N; i++){
// cout << "i = " << i << "\n";
int l = 1, r = N;
while (r - l){
int mid = (l + r) >> 1;
// cout << l << " " << mid << " " << r << "\n";
// query [l, mid] and [l, mid] ^ i
int q1, q2;
// if (!cache.count({l, mid})) cache[{l, mid}] = Query(l, mid, {}, {});
// q1 = cache[{l, mid}];
q1 = Query(l, mid, {}, adj[i]);
if (l <= i && i <= mid){
vector<int> tmp = adj[i]; tmp.push_back(i);
q2 = Query(l, mid, {}, tmp);
if (q1 > q2) l = mid+1;
else r = mid;
}
else{
q2 = Query(l, mid, {i}, adj[i]);
if (q1 < q2) l = mid+1;
else r = mid;
}
}
if (Query(l, l, {i}, {}) == 1){
// cout << i << " " << l << "\n";
adj[i].push_back(l);
adj[l].push_back(i);
}
}
int root = 0;
for (int i = 1; i <= N; i++){
if ((int)adj[i].size() == 1) root = i;
}
// cout << "root = " << root << "\n";
vector<int> final, a(N+1, 0);
final.push_back(root); a[root] = 1;
int crr = root;
while (true){
int crr2 = 0;
for (auto i: adj[crr]){
if (!a[i]) crr2 = i;
}
if (crr2 == 0) break;
crr = crr2;
// cout << "add " << crr << "\n";
a[crr] = 1;
final.push_back(crr);
}
Answer(final);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
208 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
208 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
