QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#667428	#7678. The Game	Martian148^#	WA	1ms	5824kb	C++20	2.6kb	2024-10-22 22:56:12	2024-10-22 22:56:22

Judging History

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

[2024-10-22 22:56:22]
评测

测评结果：WA
用时：1ms
内存：5824kb

查看

[2024-10-22 22:56:12]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 3e5 + 5;
ll Tex, n, m, a[MAXN], b[MAXN];
void AC(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    for(int i = n - m + 1; i <= n; i ++){
        cin >> b[i];
    }
    sort(a + 1, a + n + 1); sort(b + (n - m) + 1, b + n + 1);
    ll sum = 0, mn = a[n - m + 1], bmn = b[n - m + 1];
    multiset<ll> st_mn;
    multiset<pair<ll, ll>> st_mx;
    for(int i = n - m + 1; i <= n; i ++){
        if(b[i] < a[i]){
            cout << -1 << "\n";
            return;
        }
        sum += b[i] - a[i];
        if(b[i] - a[i]) st_mx.insert({a[i], b[i]});
    }
    if(sum > n - m){
        cout << -1 << "\n";
        return;
    }
    for(int i = 1; i <= n - m; i ++){
        st_mn.insert(a[i]);
    }
    vector<ll> ans;
    while(st_mn.size()){
        if(sum == st_mn.size()){
            while(st_mx.size()){
                pair<ll, ll> it_mx = ((*st_mx.begin()));
                st_mx.erase((st_mx.begin()));
                ans.push_back(it_mx.first);
                it_mx.first ++;
                sum --;
                st_mn.erase((st_mn.begin()));
                if(it_mx.first != it_mx.second) st_mx.insert(it_mx);
            }
            st_mn.clear();
            break;
        }
        while(st_mn.size() && (*st_mn.begin()) >= mn){
            if(st_mx.size() == 0) break;
            pair<ll, ll> it_mx = ((*st_mx.begin()));
            st_mx.erase((st_mx.begin()));
            ans.push_back(it_mx.first);
            it_mx.first ++;
            sum --;
            st_mn.erase((st_mn.begin()));
            if(it_mx.first != it_mx.second) st_mx.insert(it_mx);
            if((*st_mx.begin()).first <= bmn) mn = (*st_mx.begin()).first;
        }
        ll it_mn = ((*st_mn.begin()));   
        st_mn.erase((st_mn.begin()));
        ans.push_back(it_mn);
        it_mn ++;
        st_mn.insert(it_mn);
        st_mn.erase((st_mn.begin()));
        // for(auto it : st_mn){
        //     cout << " " << it;
        // }
        // cout << "\n";
        // cout << "\n";
        
        if(st_mn.size() && (*st_mn.begin()) >= mn && st_mx.size() == 0){
            cout << -1 << "\n";
            return;
        }
    }
    cout << ans.size() << "\n";
    for(auto it : ans){
        cout << it << " ";
    }
    cout << "\n";
}
int main(){
    // freopen("in.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> Tex;
    while(Tex --) AC();
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5824kb

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:

result:

ok ok (6 test cases)

Test #2:

score: -100

Wrong Answer

time: 0ms

memory: 5568kb

input:

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
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...

result:

wrong answer Wrong answer, the final sequence does not equal to B (test case 1)