QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#809400 | #9574. Strips | xtqqwq | WA | 8ms | 10700kb | Python3 | 2.2kb | 2024-12-11 14:50:16 | 2024-12-11 14:50:20 |
Judging History
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)