QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#796440	#9574. Strips	ZycK^#	WA	14ms	3816kb	C++14	2.2kb	2024-12-01 18:32:49	2024-12-01 18:32:56

Judging History

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

[2024-12-01 18:32:56]
评测

测评结果：WA
用时：14ms
内存：3816kb

查看

[2024-12-01 18:32:49]
提交

answer

#include <bits/stdc++.h>
#define For(i, l, r) for (int i=l; i<=r; ++i)
using namespace std;
template <typename T>
inline void read(T &x) {
    char c = getchar(); int w = 1; x = 0;
    while (!isdigit(c))
        (c == '-') && (w = -w), c = getchar();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ '0'), c = getchar();
    x *= w;
}

const int N = 100010;
int n, m, k, w, a[N], b[N], pos[N], f[N], g[N], Lst[N], ans;
inline bool solve(int L_limit, int L, int R, int R_limit) {
    int now = L-1;
    f[L-1] = 0, g[L-1] = L_limit;
    For(i, L, R) {
        int l = max(a[i]-k+1, L_limit+1),
            r = min(a[i], R_limit-k);
        if (l > r) return false;
        while (a[now+1] < l) ++ now;
        if (g[now]+1 > r) return false;
        f[i] = f[now] + 1;
        g[i] = g[now] + 1 + k - 1;
        Lst[i] = now;
    }
    int Now = R;
    For(i, 1, f[R]) {
        pos[++ ans] = g[Lst[Now]]+1;
        Now = Lst[Now];
    }
    return true;
}
signed main() {
    int T;
    read(T);
    while (T -- > 0) {
        read(n); read(m); read(k); read(w);
        For(i, 1, n) {
            read(a[i]);
        }
        For(i, 1, m) {
            read(b[i]);
        }
        std :: sort(a + 1, a + n + 1);
        std :: sort(b + 1, b + m + 1);
        int lst = 0, nxt = m+1;
        b[0] = 0; b[m+1] = w+1;
        For(i, 1, m+1) {
            if (b[i] > a[1]) {
                nxt = i; lst = i-1; break;
            }
        }
        bool flag = true;
        int i = 1;
        ans = 0;
        while (i <= n) {
            int l = i;
            while (i <= n && a[i] < b[nxt]) {
                ++ i;
            }
            if (l <= i-1) {
                if (!solve(b[lst], l, i-1, b[nxt])) {
                    flag = false; break;
                }
            }
            ++ lst, ++ nxt;
        }
        if (!flag) {
            puts("-1");
        }
        else {
            printf("%d\n", ans);
            For(i, 1, ans) {
                printf("%d ", pos[i]);
            }
            puts("");
        }
    }
    return 0;
}
/*
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
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3816kb

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: 14ms

memory: 3796kb

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
2 31 
7
3 2 14 21 30 29 28 
3
22 46 63 
8
4 1 20 17 30 35 54 59 
3
3 14 29 
6
7 5 3 1 43 41 
4
8 34 27 47 
2
48 37 
1
18 
1
9 
1
40 
5
10 29 27 48 46 
2
1 19 
3
19 11 29 
3
1 9 31 
3
6 5 42 
3
1 8 50 
4
21 11 1 32 
2
52 50 
3
43 53 63 
3
52 42 78 
1
21 
4
1 8 18 15 
5
1 7 19 17 39 
2
1 43 
2
7 25 ...

result:

wrong answer There is no stripe covering red cell 33 (test case 1)