QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#256470#7678. The GameGCnoodlesbotRE 0ms3612kbC++203.3kb2023-11-18 19:33:202023-11-18 19:33:21

Judging History

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

  • [2023-11-18 19:33:21]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3612kb
  • [2023-11-18 19:33:20]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

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

    std::vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        std::cin >> b[i];
    }

    int step = n - m;
    int surplus = 0;
    for (int i = m - 1, j = n - 1; i >= 0; i--, j--) {
        if (a[j] > b[i]) {
            std::cout << "-1\n";
            return;
        }
        surplus += b[i] - a[j];
    }

    // std::cerr << surplus << "\n";
    int wx = step - surplus;
    if (wx < 0) {
        std::cout << "-1\n";
        return;
    }
    // std::cerr << "wx: " << wx << "\n";
    std::multiset<int> set;

    for (int i = 0; i < n; i++) {
        set.emplace(a[i]);
    }

    std::vector<int> preans;
    while (!set.empty() && wx) {
        int x = *set.begin();
        set.extract(x);
        // std::cerr << "x: " << x << "\n";
        preans.push_back(x);
        x += 1;
        set.emplace(x);
        int y = *set.begin();
        set.extract(y);
        wx -= 1;
    }
    // std::cerr << "NO" << "\n";

    // for (auto x : set) {
    //     std::cerr << "x: " << x << "\n";
    // }
    
    std::vector<int> backup(set.begin(), set.end());
    std::reverse(backup.begin(), backup.end());
    // for (auto x : backup) {
    //     std::cerr << x << "\n";
    // }
    backup.resize(m);
    std::reverse(backup.begin(), backup.end());

    int idx = m - 1;
    std::multiset<int> mts;

    while (!set.empty() && idx >= 0) {
        int x = *set.rbegin();
        set.extract(x);

        int v = b[idx] - x;
        idx -= 1;

        // std::cerr << "val: " << surplus << " " << v << "\n";
        if (surplus < v || v < 0) {
            std::cout << "-1\n";
            return;
        } else {
            surplus -= v;
            x += v;
            mts.emplace(x);
        }
    }

    // for (auto x : set) {
    //     std::cerr << x << "\n";
    // }
    // std::cerr << "NO\n";
    while (surplus > 0 && !set.empty()) {
        surplus -= 1;
        int x = *set.begin();
        set.extract(x);
        preans.push_back(x);
        
        x += 1;
        set.emplace(x);
        // set.erase(set.begin());
    }
    if (*set.rbegin() > *mts.begin()) {
        std::cout << "-1\n";
        return;
    }
    // std::cerr << "surplus: " << surplus << "\n";
    std::vector ans(mts.begin(), mts.end());
    // for (int i = 0; i < ans.size(); i++) {
    //     std::cerr << ans[i] << " \n"[i == int(ans.size()) - 1];
    // }

    // std::cerr << preans.size() << "\n";
    for (int i = 0; i < ans.size(); i++) {
        if (ans[i] != b[i]) {
            std::cout << "-1\n";
            return;
        }
    }

    std::cout << step << "\n";
    for (auto x : preans) {
        std::cout << x << " ";
    }
    // std::cerr << "preans: " << preans.size() << "\n";
    for (int i = 0; i < backup.size(); i++) {
        while (backup[i] < ans[i]) {
            std::cout << backup[i] << " ";
            backup[i] += 1;
        }
    }
    std::cout << "\n";

    return;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int t;
    std::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: 3612kb

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
Runtime Error

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:


result: