QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303725#7678. The GameDetachWA 1ms3544kbC++173.1kb2024-01-12 22:17:122024-01-12 22:17:13

Judging History

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

  • [2024-01-12 22:17:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3544kb
  • [2024-01-12 22:17:12]
  • 提交

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;

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

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

    // cout << sum << endl;
    vector<int> ans;
    int cnt = 0;
    int num = S.size();
    for(auto it = S.begin(); ; it = next(it))
    {
        if(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(nxt != S.end() and *nxt == *it)
        {
            if(*it + 1 > g[0])
            {
                ok = false;
                if(idx >= m or g[idx] == b[idx]) 
                {
                    cout << -1 << endl;
                    return;
                }
                
                ans.push_back(num + idx + 1);
                g[idx] ++ ;

                while(idx < n  and g[idx] == b[idx]) idx ++ ;
                cnt -- ;
            }
            else
            {
                S.erase(nxt);
                S.insert(*it + 1);
            }
        }

        if(ok) ans.push_back(1);
        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(idx >= m or g[idx] == b[idx]) 
        {
            cout << -1 << endl;
            return;
        }
        ans.push_back(sz + idx + 1);
        g[idx] ++ ;
        while(idx < n and g[idx] == b[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: 0
Wrong Answer
time: 1ms
memory: 3544kb

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 4 
-1
3
1 3 3 
5
6 1 1 3 2 
2
3 1 
-1

result:

wrong answer Wrong answer, erase a number that does not exist (test case 1)