QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#809400#9574. StripsxtqqwqWA 8ms10700kbPython32.2kb2024-12-11 14:50:162024-12-11 14:50:20

Judging History

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

  • [2024-12-11 14:50:20]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:10700kb
  • [2024-12-11 14:50:16]
  • 提交

answer

import sys
input=sys.stdin.readline

T=int(input())
for _t in range(T):
    n,m,k,w = map(int,input().split())
    red = list(map(int,input().split()))
    black = list(map(int,input().split()))

    # Sort red and black cells
    red.sort()
    black.sort()

    # Add boundary black cells
    # We'll treat cell 0 and cell w+1 as boundaries
    # so that we don't need special case for ends.
    black_cells = [0] + black + [w+1]

    intervals = []
    # We'll iterate over gaps formed by consecutive black cells
    # For each gap [black_cells[i]+1 ... black_cells[i+1]-1]
    # we cover the red cells in that range.
    # Use two pointers to handle red cells
    r_idx = 0

    possible = True
    for i in range(len(black_cells)-1):
        G_start = black_cells[i]+1
        G_end = black_cells[i+1]-1
        if G_start > G_end:
            # No gap here
            continue

        # Cover all red cells within this gap
        while r_idx < n and red[r_idx] < G_start:
            r_idx += 1
        # Now r_idx points to first red cell >= G_start

        while r_idx < n and red[r_idx] <= G_end:
            R = red[r_idx]
            # Choose an interval to cover R
            # Intersection for X:
            # X must satisfy:
            # X >= max(G_start, R-k+1)
            # X <= min(G_end-k+1, R)

            low_bound = max(G_start, R-k+1)
            high_bound = min(G_end-k+1, R)

            if low_bound > high_bound:
                # No valid X
                possible = False
                break

            # To maximize coverage of future red cells, choose the largest X in this range
            # That would be X = high_bound
            X = high_bound

            # Interval is [X, X+k-1]
            intervals.append(X)
            cover_end = X+k-1

            # Mark all red cells covered up to cover_end
            while r_idx < n and red[r_idx] <= cover_end:
                r_idx += 1

        if not possible:
            break

    if not possible or r_idx < n:
        # Not all red cells covered
        print(-1)
    else:
        # All red covered
        print(len(intervals))
        print(" ".join(map(str, intervals)) if intervals else "")

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 10700kb

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:

4
2 7 10 14
3
2 6 7
2
1 5
-1

result:

wrong answer There are more than one stripe covering cell 7 (test case 2)