QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#511483#7678. The GamepandapythonerRE 0ms3800kbC++232.7kb2024-08-09 22:54:072024-08-09 23:06:40

Judging History

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

  • [2024-08-09 23:06:40]
  • 管理员手动重测该提交记录
  • 测评结果:RE
  • 用时:0ms
  • 内存:3800kb
  • [2024-08-09 22:54:07]
  • 提交

answer

#include <bits/stdc++.h>


using namespace std;


using ll = long long;

#define rep(i, n) for(int i = 0; i < (n); i += 1)
#define rng(i, start, end, step) for(int i = start; i < end; i += step)
#define len(a) ((int)(a).size())


mt19937 rnd(234);


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int t;
    cin >> t;
    rep(itr, t) {
        int n, m;
        cin >> n >> m;
        vector<ll> a(n), b(m);
        rep(i, n) cin >> a[i];
        rep(j, m) cin >> b[j];
        sort(b.rbegin(), b.rend());
        sort(a.rbegin(), a.rend());
        multiset<ll> right(a.begin(), a.begin() + m), left(a.begin() + m, a.end());
        vector<ll> result;
        bool ok = true;
        ll lsum = accumulate(left.begin(), left.end(), 0);
        ll rsum = accumulate(right.begin(), right.end(), 0);
        ll bsum = accumulate(b.begin(), b.end(), 0);
        if (rsum > bsum or len(left) < bsum - rsum) {
            cout << -1 << "\n";
            continue;
        }
        while (len(left) > bsum - rsum) {
            ll y = *left.begin();
            result.push_back(y);
            left.erase(left.begin());
            lsum -= y;
            right.insert(y + 1);
            rsum += y + 1;
            rsum -= *right.begin();
            lsum += *right.begin();
            left.insert(*right.begin());
            right.erase(right.begin());
            lsum -= *left.begin();
            left.erase(left.begin());
            if (rsum > bsum) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            cout << -1 << "\n";
            continue;
        }
        assert(len(left) == bsum - rsum);
        for (auto x : b) {
            ll y = *prev(right.end());
            if (y > x) {
                ok = false;
                break;
            }
            while (y < x) {
                assert(!left.empty());
                result.push_back(y);
                right.erase(right.find(y));
                y += 1;
                right.insert(y);
                left.erase(left.begin());
            }
            right.erase(prev(right.end()));
        }
        if (!ok) {
            cout << -1 << "\n";
            continue;
        }
        assert(left.empty() and right.empty());
        cout << len(result) << "\n";
        for (auto x : result) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

/*
1
4 2
1 2 2 4
2 4

1
5 3
1 2 2 3 3
2 3 4


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

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Runtime Error

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:


result: