QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#733096	#9574. Strips	lqh2024^#	WA	22ms	3888kb	C++20	2.3kb	2024-11-10 17:10:51	2024-11-10 17:10:51

Judging History

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

[2024-11-10 17:10:51]
评测

测评结果：WA
用时：22ms
内存：3888kb

查看

[2024-11-10 17:10:51]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long

void QAQ() {
    int n, m, k, w;
    cin >> n >> m >> k >> w;

    vector<int> a(n + 1), b(m + 2);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    b[0] = 0;
    b[m + 1] = w + 1;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int j = 1, ans = 0;
    vector<int> A;
    for (int i = 1; i <= m + 1; i++) {
        int uj = j;
        while (j <= n && a[j] < b[i]) j++;
        if (uj == j) continue;
        int l = b[i - 1] + 1, r = b[i] - 1;
        
        int now = l - k, res = 0, ret = 0;
        vector<int> R;
        // cout << "[] " << uj << " " << j - 1 << " " << l << " " << r << "\n";
        for (int x = uj; x < j; x++) {
            if (a[x] <= now + k - 1) continue;
            ret += a[x] - (now + k - 1) - 1;
            R.push_back(a[x] - (now + k - 1) - 1);
            ans++;
            A.push_back(a[x]);
            int pos = ans - 1;
            // cout << "? " << i << " " << x << " " << ret << "\n";
            if (a[x] + k - 1 > r) {
                if (ret >= a[x] + k - 1 - r) {
                    int g = a[x] + k - 1 - r;
                    while (g) {
                        if (R.back() <= g) {
                            A[pos] -= R.back();
                            g -= R.back();
                            R.pop_back();
                            pos--;
                        } else {
                            A[pos] -= g;
                            g = 0;
                        }
                    }
                    break;
                } else {
                    cout << "-1\n";
                    return;
                }
            }
            now = A.back();
        }   
    }

    cout << ans << "\n";
    // for (int i = 0, j = 1; i < A.size(); i++) {
    //     while (j <= n && a[j] < A[i]) j++;
    //     cout << a[j] << " \n"[i == ans - 1];
    // }
    for (int i = 0; i < A.size(); i++) {
        cout << A[i] << " \n"[i == ans - 1];
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    cin >> t;
    for (cout << fixed << setprecision(12); t--; QAQ());
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3560kb

input:

4
5 2 3 16
7 11 2 9 14
13 5
3 2 4 11
6 10 2
1 11
2 1 2 6
1 5
3
2 1 2 6
1 5
2

output:

result:

ok ok 4 cases (4 test cases)

Test #2:

score: -100

Wrong Answer

time: 22ms

memory: 3888kb

input:

11000
3 8 2 53
32 3 33
35 19 38 20 1 30 10 6
7 10 1 42
3 14 4 36 28 40 22
17 20 12 41 27 7 1 19 13 9
6 6 13 78
55 76 53 32 54 58
62 45 21 4 7 61
8 7 3 68
9 26 54 31 22 3 38 65
34 16 58 47 52 29 53
5 8 4 33
33 5 30 6 15
27 12 9 28 19 2 13 10
6 1 2 48
8 12 48 1 41 31
40
7 6 7 61
20 19 30 52 49 17 40
3...

output:

2
3 32
7
3 4 14 22 28 36 40
3
32 48 66
8
3 9 22 26 31 38 54 65
3
5 15 30
6
1 8 12 31 41 47
4
17 30 39 49
2
52 67
1
27
1
22
1
62
5
24 33 43 48 60
2
4 31
3
11 20 31
3
3 16 33
3
25 30 42
3
3 17 60
4
1 12 25 33
2
54 66
3
50 59 65
3
50 62 78
1
81
4
2 11 16 23
5
3 7 17 36 49
2
1 45
2
7 25
1
4
4
9 18 29 34...

result:

wrong answer There is at least one stripe covering black cell 31 (test case 18)