QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#240364	#7678. The Game	ucup-team1198^#	WA	6ms	3476kb	C++20	2.5kb	2023-11-05 14:57:22	2023-11-05 14:57:24

Judging History

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

[2023-11-05 14:57:24]
评测

测评结果：WA
用时：6ms
内存：3476kb

查看

[2023-11-05 14:57:22]
提交

answer

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

void solve() {
    int n, m;
    cin >> n >> m;
    vector<long long> A(n);
    for (int i = 0; i < n; ++i)
        cin >> A[i];
    vector<long long> B(m);
    for (int i = 0; i < m; ++i)
        cin >> B[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    int steps = n - m;
    long long diff = 0;
    for (int i = 0; i < m; ++i) {
        if (A[steps + i] > B[i]) {
            cout << -1 << '\n';
            return;
        }
        diff += B[i] - A[steps + i];
    }
    if (diff > steps) {
        cout << -1 << '\n';
        return;
    }
    long long rest = steps - diff;
    vector<long long> deltas(n);
    for (int i = 0; i < m; ++i) {
        deltas[steps + i] = B[i] - A[steps + i];
    }
    vector<long long> ans;
    set<int> less_than_next;
    for (int i = 0; i + 1 < n - m; ++i) {
        if (A[i] < A[i + 1])
            less_than_next.emplace(i);
    }
    int j = 0;
    while (j < n - m && rest && !less_than_next.empty()) {
        int id = *less_than_next.begin();
        ans.emplace_back(A[id]);
        ++A[id];
        if (A[id] == A[id + 1])
            less_than_next.erase(id);
        if (id - 1 >= j && A[id - 1] < A[id])
            less_than_next.emplace(id - 1);
        less_than_next.erase(j);
        --rest;
        ++j;
    }
    for (int i = n - m; i < n; ++i) {
        for (int k = 0; k < deltas[i]; ++k) {
            ans.emplace_back(A[i] + k);
        }
        A[i] += deltas[i];
        j += deltas[i];
    }
    if (!rest) {
        cout << ans.size() << '\n';
        for (long long x : ans)
            cout << x << ' ';
        cout << '\n';
        return;
    }
    if (A[n - m] > A[n - m - 1])
        less_than_next.emplace(n - m - 1);
    while (j < n - m && rest && !less_than_next.empty()) {
        int id = *less_than_next.begin();
        ans.emplace_back(A[id]);
        ++A[id];
        if (A[id] == A[id + 1])
            less_than_next.erase(id);
        if (id - 1 >= j && A[id - 1] < A[id])
            less_than_next.emplace(id - 1);
        less_than_next.erase(j);
        --rest;
        ++j;
    }
    if (rest) {
        cout << -1 << '\n';
        return;
    }
    cout << ans.size() << '\n';
    for (long long x : ans)
        cout << x << ' ';
    cout << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3404kb

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:

result:

ok ok (6 test cases)

Test #2:

score: 0

Accepted

time: 3ms

memory: 3368kb

input:

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
2 
-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:

ok ok (7056 test cases)

Test #3:

score: 0

Accepted

time: 0ms

memory: 3424kb

input:

output:

-1
-1
2
1 2 
-1
-1
-1
-1
2
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
2
2 3 
-1
-1
-1
2
1 1 
2
1 2 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
3 4 
-1
-1
-1
2
1 1 
2
1 3 
-1
-1
-1
2
1 2 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok ok (5880 test cases)

Test #4:

score: 0

Accepted

time: 2ms

memory: 3436kb

input:

output:

result:

ok ok (2640 test cases)

Test #5:

score: 0

Accepted

time: 6ms

memory: 3476kb

input:

output:

-1
-1
2
1 2 
-1
-1
-1
2
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
2
2 3 
-1
-1
-1
2
1 2 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
1 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok ok (14112 test cases)

Test #6:

score: -100

Wrong Answer

time: 3ms

memory: 3432kb

input:

output:

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

result:

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