QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548855#6400. Game: Celestepandapythoner#RE 35ms472700kbC++233.4kb2024-09-05 21:35:522024-09-05 21:35:52

Judging History

你现在查看的是最新测评结果

  • [2024-09-05 21:35:52]
  • 评测
  • 测评结果:RE
  • 用时:35ms
  • 内存:472700kb
  • [2024-09-05 21:35:52]
  • 提交

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...

output:


result: