QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#310792#6400. Game: Celestememset0RE 2ms7692kbC++202.1kb2024-01-21 18:00:402024-01-21 18:00:42

Judging History

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

  • [2024-01-21 18:00:42]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:7692kb
  • [2024-01-21 18:00:40]
  • 提交

answer

#include <bits/stdc++.h>
#ifndef popteam
#define endl '\n'
#endif
#define all(x) begin(x), end(x)
using namespace std;
const int N = 1e6 + 9;
int T, n, xl, xr, x[N], a[N];
struct sequence {
    vector<int> v;
    bool empty() { return v.empty(); }
    bool operator>(const sequence &rhs) const {
        for (size_t i = 0; i < v.size() && i < rhs.v.size(); i++)
            if (v[i] != rhs.v[i]) {
                return v[i] > rhs.v[i];
            }
        return v.size() > rhs.v.size();
    }
    sequence insert(int x) {
        sequence it = *this;
        it.v.push_back(x);
        sort(all(it.v), [&](int x, int y) { return x > y; });
        return it;
    }
} f[N];
deque<pair<int, sequence>> q;
int main() {
#ifdef popteam
    freopen("G.in", "r", stdin);
#endif
    cin.tie(0)->sync_with_stdio(0);
    cin >> T;
    while (T--) {
        cin >> n >> xl >> xr;
        for (int i = 1; i <= n; i++)
            cin >> x[i];
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        q.clear();
        int j = 1;
        for (int i = 1; i <= n; i++) {
            if (i == 1) {
                f[i] = {{a[1]}};
            } else {
                f[i] = {{}};
            }
            while (j < i && x[j] + xl <= x[i] && x[i] <= x[j] + xr) {
                while (q.size() && f[j] > q.back().second) {
                    q.pop_back();
                }
                q.push_back(make_pair(j, f[j]));
                j++;
            }
            // fprintf(stderr, "i=%d\n", i);
            // for (auto x : q)
            //     cerr << x.first << " ";
            // cerr << endl;
            while (q.size() && x[q.front().first] + xl > x[i] || x[q.front().first] + xr < x[i]) {
                q.pop_front();
            }
            if (q.size()) {
                f[i] = q.front().second.insert(a[i]);
            }
        }
        if (f[n].empty()) {
            cout << -1 << endl;
        } else {
            cout << f[n].v.size() << endl;
            for (int i = 0; i < f[n].v.size(); i++)
                cout << f[n].v[i] << " \n"[i + 1 == f[n].v.size()];
        }
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 7692kb

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: