QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303768#7678. The GameDetachWA 3ms3576kbC++174.0kb2024-01-12 23:21:172024-01-12 23:21:17

Judging History

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

  • [2024-01-12 23:21:17]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3576kb
  • [2024-01-12 23:21:17]
  • 提交

answer

#include <bits/stdc++.h>
// #include <algorithm>
// #include <queue>
// #include <map>
// #include <iostream>
// #include <string>
// #include <set>
#define endl '\n'

using namespace std;

using LL = long long;
using PII = pair<int, int>;
using i128 = __int128_t;
using ULL = unsigned long long;

const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, N = 1e6 + 5;
const LL LINF = 0x3f3f3f3f3f3f3f3f;

struct node
{
    int val, idx;

    bool operator < (const struct node & W) const
    {
        if(val != W.val) return val < W.val;
        return idx > W.idx;
    }

    bool operator > (const struct node & W) const
    {
        if(val != W.val) return val > W.val;
        return idx < W.idx;
    }
}node;

void solve()
{
    int n, m;
    cin >> n >> m;

    if(n < m)
    {
        cout << -1 << endl;
        return;
    }
    
    vector<int> f(n - m), g(m), b(m);
    multiset<int> S;
    for(int i = 0; i < n - m; i ++ )
    {
        cin >> f[i];
        S.insert(f[i]);
    }
    for(int i = 0; i < m; i ++ ) cin >> g[i];
    for(int i = 0; i < m; i ++ ) cin >> b[i];

    // sort(g.begin(), g.end());
    // sort(b.begin(), b.end());

    LL sum = 0;
    int idx = -1;
    for(int i = 0; i < m; i ++ ) 
    {
        if(g[i] > b[i])
        {
            cout << -1 << endl;
            return;
        }

        if(idx == -1 and b[i] != g[i]) idx = i;
        sum += b[i] - g[i];
    }

    if(sum > n - m)
    {
        cout << -1 << endl;
        return;
    }

    priority_queue<struct node, vector<struct node>, greater<struct node> > q;
    for(int i = 0; i < m; i ++ )
    {
        if(g[i] < b[i]) q.push({g[i], i});
    }

    // cout << sum << endl;
    vector<int> ans;
    int cnt = 0;
    int num = S.size();
    for(auto it = S.begin(); ; it = next(it))
    {
        if(it != S.begin() and (cnt >= n - m - sum or it == S.end()))
        {
            S.erase(prev(it));
            break;
        }

        bool ok = true;
        if(*it >= b[0])
        {
            cout << -1 << endl;
            return;
        }
        auto nxt = next(it);

        if((!q.empty() and *it == q.top().val) or (nxt != S.end() and *nxt == *it))
        {
            if(!q.empty() and *it + 1 > q.top().val)
            {
                ok = false;
                if(q.empty())
                {
                    cout << -1 << endl;
                    return;
                }               
                auto [val, idx] = q.top();
                q.pop();
                
                // cout << "hh" << val << endl;
                ans.push_back(val);
                g[idx] ++ ;
                if(g[idx] < b[idx]) q.push({g[idx], idx});
                
                cnt -- ;
            }
            else
            {
                S.erase(nxt);
                S.insert(*it + 1);
            }
        }

        if(ok) ans.push_back(*it);
        cnt ++ ;
        if(it != S.begin())
        {
            S.erase(prev(it));
        }
        num -- ;
        // for(auto j : S) cout << j << ' ';cout << endl;cout << *it << endl;
    }

    // cout << "----" << endl;// return;
    
    int sz = S.size();
    
    while(!S.empty())
    {
        // if(q.empty())
        // {
        //     cout << -1 << endl;
        //     return;
        // }
        
        auto [val, idx] = q.top();
        // cout << "hh" << val << ' ' << idx << endl;
        q.pop();
        
        ans.push_back(val);
        g[idx] ++ ;
        if(g[idx] < b[idx]) q.push({g[idx], idx});
        S.erase(S.begin());
        sz -- ;
    }
    
    cout << n - m << endl;
    for(auto it : ans) cout << it << ' ';
    cout << endl;
    // cout << "----" << endl;
}   

int main()
{
    // freopen("galactic.in", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1; 
    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: 3520kb

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: 3576kb

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

result:

wrong answer Jury has answer but participant has not (test case 2)