QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#548855 | #6400. Game: Celeste | pandapythoner# | RE | 35ms | 472700kb | C++23 | 3.4kb | 2024-09-05 21:35:52 | 2024-09-05 21:35:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define len(a) int((a).size())
#define all(a) begin(a), end(a)
#define rep(i, n) for (int i = 0; i < (n); i++)
mt19937 rnd(34234);
struct node {
int l = -1, r = -1;
ll hsh = 0;
};
const int maxn = 1e6 + 1000;
int cur_sz = 0;
node *g;
map<ll, ll> hshs;
int add(int v, int i, ll x, ll xhsh) {
int nv = cur_sz++;
if (v == -1) {
g[nv] = node();
} else {
g[nv] = g[v];
}
if (i == 0) {
g[nv].hsh += xhsh;
return nv;
}
if ((x >> i) & 1) {
g[nv].r = add(g[nv].r, i - 1, x, xhsh);
g[nv].hsh += xhsh;
} else {
g[nv].l = add(g[nv].l, i - 1, x, xhsh);
g[nv].hsh += xhsh;
}
return nv;
}
int compare(int u, int v, int i, ll x) {
if (u == -1 and v == -1) {
return 0;
}
if (u == -1) {
return -1;
}
if (v == -1) {
return 1;
}
if (g[u].hsh == g[v].hsh) return 0;
if (i == 0) {
auto it = hshs.find(x);
assert(it != hshs.end());
ll hshx = it->second;
if (g[u].hsh / hshx < g[v].hsh / hshx) return -1;
return 1;
}
int t = compare(g[u].r, g[v].r, i - 1, x | (1 << i));
if (t == 0) {
return compare(g[u].l, g[v].l, i - 1, x);
}
return t;
}
int compare(int u, int v) {
return compare(u, v, 29, 0);
}
int n;
ll L, R;
vector<ll> x, a;
signed main() {
g = new node[maxn * 30];
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
rep(itr, t) {
cur_sz = 0;
g[cur_sz++] = node();
cin >> n >> L >> R;
x.resize(n);
a.resize(n);
rep(i, n) cin >> x[i];
rep(i, n) cin >> a[i];
rep(i, n) hshs[a[i]] = ll(rnd()) + 1;
vector<int> dp(n);
int l = n;
int r = n;
dp[n - 1] = add(-1, 29, a[n - 1], hshs[a[n - 1]]);
deque<pair<int, int>> d;
vector<int> nxt(n, -1);
for (int i = n - 2; i >= 0; i -= 1) {
while (l - 1 > i and x[i] + L <= x[l - 1]) {
l -= 1;
int v = dp[l];
if (v == -2) continue;
while (!d.empty() and compare(d.back().first, v) == -1) d.pop_back();
d.push_back(make_pair(v, l));
}
while (r - 1 > i and x[i] + R < x[r - 1]) {
r -= 1;
if (!d.empty() and d.front().second == r) d.pop_front();
}
if (d.empty()) {
dp[i] = -2;
} else {
dp[i] = add(d.front().first, 29, a[i], hshs[a[i]]);
nxt[i] = d.front().second;
}
}
if (dp[0] == -2) {
cout << -1 << "\n";
} else {
vector<ll> result;
int v = 0;
while (v != -1) {
result.push_back(a[v]);
int oldv = v;
v = nxt[v];
if (v == -1) assert(oldv == n - 1);
}
sort(result.rbegin(), result.rend());
cout << len(result) << "\n";
for (auto x : result) cout << x << " "; cout << "\n";
}
}
return 0;
}
/*
2
5 2 3
1 2 3 4 5
5 2 3 1 4
3 1 2
1 4 7
3 3 3
*/
详细
Test #1:
score: 100
Accepted
time: 35ms
memory: 472700kb
input:
2 5 2 3 1 2 3 4 5 5 2 3 1 4 3 1 2 1 4 7 3 3 3
output:
3 5 4 3 -1
result:
ok 3 lines
Test #2:
score: -100
Runtime Error
input:
10000 57 8 11 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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 11 16 7 7 10 13 9 14 10 1 12 4 8 13 3 20 16 7 16 19 20 8 19 7 16 6 17 13 7 19 17 11 12 17 6 3 7 8 14 2 4 15 5 18 16 7 20 9 1...