#include <bits/stdc++.h>
using namespace std;
#include "library.h"
int Query(int l, int r, vector<int> include, vector<int> exclude, int N){
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){
if (N == 1){
vector<int> ans = {1};
Answer(ans);
return;
}
vector<vector<int>> adj(N+1);
for (int i = 1; i <= N; i++){
while (true){
// 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], N);
if (l <= i && i <= mid){
vector<int> tmp = adj[i]; tmp.push_back(i);
q2 = Query(l, mid, {}, tmp, N);
if (q1 > q2) l = mid+1;
else r = mid;
}
else{
q2 = Query(l, mid, {i}, adj[i], N);
if (q1 < q2) l = mid+1;
else r = mid;
}
}
if (Query(i, i, {l}, adj[i], N) == 1){
// cout << i << " " << l << "\n";
adj[i].push_back(l);
adj[l].push_back(i);
if (adj[i].size() > 1) break;
int q3 = Query(1, N, {}, {i}, N);
vector<int> tmp = adj[i]; tmp.push_back(i);
int q4 = Query(1, N, {}, tmp, N);
if (q3 > q4) break;
}
else{
break;
}
}
}
int root = 0;
for (int i = 1; i <= N; i++){
if ((int)adj[i].size() == 1) root = i;
}
if (root == 0) return;
// 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);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
208 KB |
# of queries: 4320 |
2 |
Correct |
55 ms |
296 KB |
# of queries: 4206 |
3 |
Correct |
69 ms |
292 KB |
# of queries: 4464 |
4 |
Correct |
41 ms |
208 KB |
# of queries: 4361 |
5 |
Correct |
50 ms |
296 KB |
# of queries: 4414 |
6 |
Correct |
61 ms |
292 KB |
# of queries: 4385 |
7 |
Correct |
58 ms |
292 KB |
# of queries: 4379 |
8 |
Correct |
40 ms |
292 KB |
# of queries: 4209 |
9 |
Correct |
55 ms |
208 KB |
# of queries: 4432 |
10 |
Correct |
38 ms |
304 KB |
# of queries: 2747 |
11 |
Correct |
0 ms |
208 KB |
# of queries: 0 |
12 |
Correct |
1 ms |
208 KB |
# of queries: 5 |
13 |
Correct |
0 ms |
208 KB |
# of queries: 18 |
14 |
Correct |
1 ms |
208 KB |
# of queries: 30 |
15 |
Correct |
3 ms |
208 KB |
# of queries: 181 |
16 |
Correct |
5 ms |
304 KB |
# of queries: 378 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
208 KB |
# of queries: 4320 |
2 |
Correct |
55 ms |
296 KB |
# of queries: 4206 |
3 |
Correct |
69 ms |
292 KB |
# of queries: 4464 |
4 |
Correct |
41 ms |
208 KB |
# of queries: 4361 |
5 |
Correct |
50 ms |
296 KB |
# of queries: 4414 |
6 |
Correct |
61 ms |
292 KB |
# of queries: 4385 |
7 |
Correct |
58 ms |
292 KB |
# of queries: 4379 |
8 |
Correct |
40 ms |
292 KB |
# of queries: 4209 |
9 |
Correct |
55 ms |
208 KB |
# of queries: 4432 |
10 |
Correct |
38 ms |
304 KB |
# of queries: 2747 |
11 |
Correct |
0 ms |
208 KB |
# of queries: 0 |
12 |
Correct |
1 ms |
208 KB |
# of queries: 5 |
13 |
Correct |
0 ms |
208 KB |
# of queries: 18 |
14 |
Correct |
1 ms |
208 KB |
# of queries: 30 |
15 |
Correct |
3 ms |
208 KB |
# of queries: 181 |
16 |
Correct |
5 ms |
304 KB |
# of queries: 378 |
17 |
Runtime error |
349 ms |
452 KB |
Execution killed with signal 13 |
18 |
Halted |
0 ms |
0 KB |
- |