QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#544448#7678. The Gameucup-team2179#WA 6ms3872kbC++204.4kb2024-09-02 16:48:082024-09-02 16:48:08

Judging History

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

  • [2024-09-02 16:48:08]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3872kb
  • [2024-09-02 16:48:08]
  • 提交

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;
}

详细

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)