QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#547944#7678. The GameXiaoretaWWA 3ms3600kbC++202.6kb2024-09-05 13:39:232024-09-05 13:39:23

Judging History

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

  • [2024-09-05 13:39:23]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3600kb
  • [2024-09-05 13:39:23]
  • 提交

answer

#include <bits/stdc++.h>

#define debug(...) 42;
#ifdef LOCAL
#include "debug.h"
#endif

using namespace std;
#define V vector
#define fi first
#define se second
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define F(i, l, r) for (int i = l; i < r; ++i)
#define R(i, l, r) for (int i = r-1; i >= l; --i)
typedef long long LL;
typedef double DB;
typedef pair<int, int> PII;
template<typename T> bool setmin(T &a, T b) { return (a > b ? a = b, 1 : 0); }
template<typename T> bool setmax(T &a, T b) { return (a < b ? a = b, 1 : 0); }
// mt19937_64 rng {chrono::steady_clock::now().time_since_epoch().count()};

/* -------------Main code------------- */
void solve() {
    int n, m; cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }

    long long op = 0;
    for (int i = 0; i < m; i++) {
        if (b[i] < a[n - m + i]) {
            cout << -1 << '\n';
            return;
        }
        op += b[i] - a[n - m + i];
    }

    if (op > n - m) {
        cout << -1 << '\n';
        return;
    }

    vector<int> ans; ans.reserve(n - m);
    multiset<int> pre, suf;

    for (int i = 0; i < n - m; i++) {
        pre.insert(a[i]);
    }
    for (int i = n - m; i < n; i++) {
        suf.insert(a[i]);
    }

    int left = n - m;
    while (true) {
        int remove = *pre.begin(); pre.extract(remove);
        ans.push_back(remove);
        remove += 1;
        pre.insert(remove);
        if (!suf.empty()) {
            int head = *suf.begin(), tail = *pre.rbegin();
            if (head < tail) {
                assert(tail - head == 1);
                suf.extract(head); suf.insert(tail); op--;
                pre.extract(tail); pre.insert(head);
            }
        }
        pre.erase(pre.begin());
        --left;
        if (pre.empty() or suf.empty()) break;
        if (left == op) break;
    }

    if (op != left) {
        cout << -1 << '\n';
        return;
    }

    auto cur = vector<int>(all(suf));
    for (int i = 0; i < m; i++) {
        if (cur[i] > b[i]) {
            cout << -1 << '\n';
            return;
        }
        for (int j = 0, d = cur[i]; j < b[i] - cur[i]; j++) {
            ans.push_back(d++);
        }
    }

    assert((int) ans.size() == n - m);
    cout << n - m << '\n';
    for (int i : ans) cout << i << ' ';
    cout << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int tt; cin >> tt;
    while (tt--) solve();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3600kb

input:

6
5 3
1 2 2 3 3
2 3 4
4 2
1 2 2 4
2 4
5 2
2 3 3 4 4
5 5
6 1
1 1 1 1 1 1
4
4 2
1 1 1 2
2 2
4 1
1 1 1 1
2

output:

2
1 3 
-1
3
2 4 4 
5
1 1 1 2 3 
2
1 1 
-1

result:

ok ok (6 test cases)

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 3600kb

input:

7056
4 3
1 1 1 1
1 1 1
4 3
1 1 1 1
1 1 2
4 3
1 1 1 1
1 1 3
4 3
1 1 1 1
1 1 4
4 3
1 1 1 1
1 1 5
4 3
1 1 1 1
1 1 6
4 3
1 1 1 1
1 2 2
4 3
1 1 1 1
1 2 3
4 3
1 1 1 1
1 2 4
4 3
1 1 1 1
1 2 5
4 3
1 1 1 1
1 2 6
4 3
1 1 1 1
1 3 3
4 3
1 1 1 1
1 3 4
4 3
1 1 1 1
1 3 5
4 3
1 1 1 1
1 3 6
4 3
1 1 1 1
1 4 4
4 3
1 1...

output:

-1
1
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1...

result:

wrong answer Jury has answer but participant has not (test case 59)