QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#556457#7678. The GamepotentialWA 15ms5900kbC++203.0kb2024-09-10 18:36:112024-09-10 18:36:12

Judging History

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

  • [2024-09-10 18:36:12]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:5900kb
  • [2024-09-10 18:36:11]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
# define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
# define int long long
# define lowbit(x) (x & (-x))
# define fi first
# define se second
// # define endl '\n'

inline int Read();

typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 1e6 + 10;

map <int, int> mp;
// vector <int> v;

int a[N], b[N];
void Solve(){
    priority_queue <int, vector <int>, greater <int>> q;
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++){
        cin >> a[i];
        q.push(a[i]);
    }
    for(int i = 0; i < m; i ++){
        cin >> b[i];
    }
    sort(a, a + n);
    sort(b, b + m);
    if(n < m){
        cout << "-1\n";
        return;
    }
    int k = n - m;//总的
    int sum = 0;//需要的
    for(int i = 0; i < m; i ++){
        if(a[n - 1 - i] > b[m - 1 - i]){
            cout << "-1\n";
            return;
        }
        sum += - a[n - 1 - i] + b[m - 1 - i];
    }
    if(k < sum){
        cout << "-1\n";
        return;
    }
    int t = k - sum;//浪费的
    // cout << k <<"\n";
    vector <int> ans;
    for(int i = 0; i < t; i ++){
        int u = q.top(); q.pop();
        ans.push_back(u); u ++;
        // cout << u - 1 <<" ";
        q.push(u);
        q.pop();
    }  
    // cout << "********\n";
    vector <int> v;
    while(q.size()) {
        v.push_back(q.top());
        q.pop();
    }
    int s = 0;
    for(int i = 0, j = m - 1, l = (int)v.size() - 1; sum != 0; i ++){
        while(v[l] < b[j]&&sum != 0){
            // cout << v[l] <<"*";
            ans.push_back(v[l]);
            v[l] += 1;
            sum--;
            s ++;
        }
        // cout << v[l] <<' ' << b[j] <<"\n";
        l --;
        j --;
        if(l < 0 || j < 0) break;
    }
    // cout << sum <<"\n";
    priority_queue <int, vector <int>, greater <int>> p;
    for(int i = s; i < v.size(); i ++){
        p.push(v[i]);
    }
    int ff = 0;
    while(sum != 0){
        ff = 1;
        int u = p.top(); p.pop();
        ans.push_back(u);
        u ++;
        p.push(u);
        sum --;
        p.pop();
    }
    int kk = v.size() - 1;
    if(ff == 1){
        while(p.size()){
            v[kk] = p.top();
            // cout << p.top() <<"****\n";
            p.pop();
            kk --;
        }
    }
    int f=0;
    for(int i = m - 1, j = (int)v.size() - 1; i >= 0; i --, j --){
        if(b[i] != v[j]){
            f = 1;
            break;
        }
    }
    if(f) cout << "-1\n";
    else{
        cout << k <<"\n";
        for(auto x : ans){
            cout << x <<" "; 
        }
        cout <<'\n';
    }
}
signed main(){
    // IOS;
    int T = 1;
    cin >> T;
    while (T--) 
        Solve();
    return 0;
}
inline int Read(){
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9'){ if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5664kb

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 2 3 2 
2
1 1 
-1

result:

ok ok (6 test cases)

Test #2:

score: 0
Accepted
time: 15ms
memory: 5660kb

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: 8ms
memory: 5900kb

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

result:

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