QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#511484 | #7678. The Game | pandapythoner | RE | 0ms | 3524kb | C++23 | 2.7kb | 2024-08-09 22:54:15 | 2024-08-09 22:54:16 |
Judging History
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: 3524kb
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...