QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#556457 | #7678. The Game | potential | WA | 15ms | 5900kb | C++20 | 3.0kb | 2024-09-10 18:36:11 | 2024-09-10 18:36:12 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
# define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
# define int long long
# define lowbit(x) (x & (-x))
# define fi first
# define se second
// # define endl '\n'
inline int Read();
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 1e6 + 10;
map <int, int> mp;
// vector <int> v;
int a[N], b[N];
void Solve(){
priority_queue <int, vector <int>, greater <int>> q;
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i ++){
cin >> a[i];
q.push(a[i]);
}
for(int i = 0; i < m; i ++){
cin >> b[i];
}
sort(a, a + n);
sort(b, b + m);
if(n < m){
cout << "-1\n";
return;
}
int k = n - m;//总的
int sum = 0;//需要的
for(int i = 0; i < m; i ++){
if(a[n - 1 - i] > b[m - 1 - i]){
cout << "-1\n";
return;
}
sum += - a[n - 1 - i] + b[m - 1 - i];
}
if(k < sum){
cout << "-1\n";
return;
}
int t = k - sum;//浪费的
// cout << k <<"\n";
vector <int> ans;
for(int i = 0; i < t; i ++){
int u = q.top(); q.pop();
ans.push_back(u); u ++;
// cout << u - 1 <<" ";
q.push(u);
q.pop();
}
// cout << "********\n";
vector <int> v;
while(q.size()) {
v.push_back(q.top());
q.pop();
}
int s = 0;
for(int i = 0, j = m - 1, l = (int)v.size() - 1; sum != 0; i ++){
while(v[l] < b[j]&&sum != 0){
// cout << v[l] <<"*";
ans.push_back(v[l]);
v[l] += 1;
sum--;
s ++;
}
// cout << v[l] <<' ' << b[j] <<"\n";
l --;
j --;
if(l < 0 || j < 0) break;
}
// cout << sum <<"\n";
priority_queue <int, vector <int>, greater <int>> p;
for(int i = s; i < v.size(); i ++){
p.push(v[i]);
}
int ff = 0;
while(sum != 0){
ff = 1;
int u = p.top(); p.pop();
ans.push_back(u);
u ++;
p.push(u);
sum --;
p.pop();
}
int kk = v.size() - 1;
if(ff == 1){
while(p.size()){
v[kk] = p.top();
// cout << p.top() <<"****\n";
p.pop();
kk --;
}
}
int f=0;
for(int i = m - 1, j = (int)v.size() - 1; i >= 0; i --, j --){
if(b[i] != v[j]){
f = 1;
break;
}
}
if(f) cout << "-1\n";
else{
cout << k <<"\n";
for(auto x : ans){
cout << x <<" ";
}
cout <<'\n';
}
}
signed main(){
// IOS;
int T = 1;
cin >> T;
while (T--)
Solve();
return 0;
}
inline int Read(){
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9'){ if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5664kb
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 2 3 2 2 1 1 -1
result:
ok ok (6 test cases)
Test #2:
score: 0
Accepted
time: 15ms
memory: 5660kb
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 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: -100
Wrong Answer
time: 8ms
memory: 5900kb
input:
5880 4 2 1 1 1 1 1 1 4 2 1 1 1 1 1 2 4 2 1 1 1 1 1 3 4 2 1 1 1 1 1 4 4 2 1 1 1 1 1 5 4 2 1 1 1 1 1 6 4 2 1 1 1 1 1 7 4 2 1 1 1 1 2 2 4 2 1 1 1 1 2 3 4 2 1 1 1 1 2 4 4 2 1 1 1 1 2 5 4 2 1 1 1 1 2 6 4 2 1 1 1 1 2 7 4 2 1 1 1 1 3 3 4 2 1 1 1 1 3 4 4 2 1 1 1 1 3 5 4 2 1 1 1 1 3 6 4 2 1 1 1 1 3 7 4 2 1 1...
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 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 2 3 4 -1 -1 -1 -1 2 3 1 -1 -1 -1 2 1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2...
result:
wrong answer Jury has answer but participant has not (test case 65)