QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#544448 | #7678. The Game | ucup-team2179# | WA | 6ms | 3872kb | C++20 | 4.4kb | 2024-09-02 16:48:08 | 2024-09-02 16:48:08 |
Judging History
answer
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
struct D{
int m=0;
multiset<int> low;
multiset<int> high;
ll s= 0;
void add(int u){
high.insert(u);
s += u;
if((int)high.size()>m){
int mi = *high.begin();
s -= mi;
low.insert(mi);
high.erase(high.find(mi));
}
}
void del(int u){
if(*high.begin()<=u){
int k = *high.begin();
s -= k;
high.erase(high.find(k));
if(!low.empty()){
int mx = *low.rbegin();
low.erase(low.find(mx));
high.insert(mx);
s += mx;
}
}
else low.erase(low.find(u));
}
void init(){
low.clear();
high.clear();
m = 0;
s = 0;
}
}myset;
multiset<int> a, b;
void solve(){
int n, m;
cin >> n >> m;
a.clear();
b.clear();
vector<int> av;
vector<int> bv;
ll sumb = 0;
myset.init();
myset.m = m;
for (int i = 0; i < n;i++){
int u;
cin >> u;
myset.add(u);
av.pb(u);
a.insert(u);
}
for (int i = 0; i < m;i++){
int u;
cin >> u;
sumb += u;
bv.pb(u);
b.insert(u);
}
// cout << a.size() << " " << b.size() << "\n";
sort(av.begin(), av.end(),greater<int>());
sort(bv.begin(), bv.end(),greater<int>());
ll sum = 0;
int flag = 1;
for (int i = 0; i < m;i++)
{
if(av[i]>bv[i])flag=0;
else
sum += bv[i] - av[i];
}
if(sum>n-m)
flag = 0;
if(flag==0){
cout << -1<<'\n';
return;
}
vector<int> ans;
int lastcnt = 0;
for (int i = 0; i < n - m;i++){
if(sumb-myset.s<0){
cout << -1<<'\n';
return;
}
if(sumb-myset.s<n-m-i){
int k = *a.begin();
ans.pb(k);
a.erase(a.find(k));
a.insert(k + 1);
myset.del(k);
myset.add(k + 1);
k = *a.begin();
a.erase(a.find(k));
myset.del(k);
}
else {
lastcnt = n - m - i;
break;
}
if(sumb-myset.s<0){
cout << -1<<'\n';
return;
}
}
vector<int> res;
for (auto p:myset.high)
res.pb(p);
sort(res.begin(), res.end(), greater<int>());
for (int i = 0; i < m;i++){
for (int j = res[i]; j < bv[i];j++)
ans.pb(j);
}
// for (int i = 0; i < lastcnt;i++){
// assert(!a.empty());
// int uk = *a.rbegin();
// while(b.count(uk)){
// a.erase(a.find(uk));
// b.erase(b.find(uk));
// if(a.empty())
// break;
// uk = *a.rbegin();
// }
// int k = *a.rbegin();
// ans.pb(k);
// a.erase(a.find(k));
// a.insert(k+1);
// a.erase(a.begin());
// k = *a.rbegin();
// while(b.count(k)){
// b.erase(b.find(k));
// a.erase(a.find(k));
// if(a.empty())
// break;
// k = *a.rbegin();
// }
// }
cout << ans.size() << '\n';
for (auto p : ans)
cout << p << " ";
cout << '\n';
// if (a.size())
// {
// int k = *a.rbegin();
// while (b.count(k))
// {
// b.erase(b.find(k));
// a.erase(a.find(k));
// if (a.empty())
// break;
// k = *a.rbegin();
// }
// }
// if (a.empty() && b.empty())
// {
// cout << ans.size() << '\n';
// for (auto p : ans)
// cout << p << " ";
// cout << '\n';
// }
// else
// cout << "-1\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3872kb
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: 0
Accepted
time: 6ms
memory: 3644kb
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: 5ms
memory: 3808kb
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 3 1 1 2 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 3 1 1 3 2 3 4 -1 -1 -1 2 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 ...
result:
wrong answer Wrong answer, number of operation is not correct (test case 31)