QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#547944 | #7678. The Game | XiaoretaW | WA | 3ms | 3600kb | C++20 | 2.6kb | 2024-09-05 13:39:23 | 2024-09-05 13:39:23 |
Judging History
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)