1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| #include "C.hpp" #include <vector> using namespace std; #define ep emplace_back typedef vector <int> VI; typedef pair <int, int> PII; VI a, b; vector <PII> work(int n) { a.ep(1); for (int i = 2; i <= n; ++i) { int l = 1, r = i - 1, p = i; while (l <= r) { int mid = l + r >> 1; ask(VI(a.begin(), a.begin() + mid), i) ? (p = mid, r = mid - 1) : (l = mid + 1); } a.insert(a.begin() + p - 1, i); } vector <PII> res; b.ep(1); for (int i = n - 1; i; --i) { int x = a[i]; while (ask(VI(b.begin(), b.end()), x)) { int l = 1, r = b.size() - 1, p = 0; while (l <= r) { int mid = l + r >> 1; ask(VI(b.begin(), b.begin() + mid + 1), x) ? (p = mid, r = mid - 1) : (l = mid + 1); } res.ep(b[p], x), swap(b[p], b.back()), b.pop_back(); } b.ep(x); } for (int i : b) if (i ^ 1) res.ep(i, 1); return res; }
|
Gitalk 加载中 ...