QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #673440 | #8783. Cherry Picking | malkovsky | WA | 16ms | 10740kb | Python3 | 1.9kb | 2024-10-24 22:23:32 | 2024-10-24 22:23:33 |
Judging History
answer
def __main__():
sorted_players = dict()
n, k = map(int, input().split())
ratings = list(map(int, input().split()))
result = input()
left = [i for i in range(n)]
def get_left(i):
while i != left[i]:
i = left[i]
return left[i]
right = [i + 1 for i in range(n)]
size = [1 for i in range(n)]
num_at_least_k = 0
for i in range(0, n):
if i > 0 and result[i] == result[i - 1]:
left[i] = left[i - 1]
right[left[i]] = right[i]
size[left[i]] += 1
if size[left[i]] == k and result[i] == "1":
num_at_least_k += 1
if k == 1:
num_at_least_k += int(result[i])
if ratings[i] not in sorted_players:
sorted_players[ratings[i]] = []
sorted_players[ratings[i]].append(i)
# print(left,right, size)
# print(num_at_least_k)
answer = 0
for r, players in sorted(sorted_players.items(), key=lambda x: x[0]):
if num_at_least_k > 0:
answer = r
# print(num_at_least_k)
for player in players:
seg = get_left(player)
size[seg] -= 1;
if size[seg] == k - 1 and result[seg] == "1":
num_at_least_k -= 1
# print("removed", player, seg, size[seg])
if size[seg] == 0:
if right[seg] < n and seg > 0:
left[right[seg]] = get_left(seg - 1)
right[left[right[seg]]] = right[right[seg]]
size[left[right[seg]]] += size[right[seg]]
# print("Merged", left[right[seg]], right[right[seg]])
if size[left[right[seg]]] >= k and result[left[right[seg]]] == "1":
num_at_least_k += 1
# print(num_at_least_k)
print(answer)
__main__()
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 16ms
memory: 10704kb
input:
5 2 1 2 3 4 5 01101
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 10ms
memory: 10592kb
input:
5 2 3 4 5 2 1 10101
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 10ms
memory: 10572kb
input:
1 1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 15ms
memory: 10704kb
input:
1 1 1 0
output:
0
result:
ok answer is '0'
Test #5:
score: 0
Accepted
time: 16ms
memory: 10580kb
input:
5 3 8 3 5 2 7 10101
output:
5
result:
ok answer is '5'
Test #6:
score: 0
Accepted
time: 6ms
memory: 10636kb
input:
10 3 1 10 2 3 9 3 1 6 9 3 1100110001
output:
0
result:
ok answer is '0'
Test #7:
score: 0
Accepted
time: 15ms
memory: 10704kb
input:
10 1 6 7 2 10 8 4 4 9 7 9 0111011000
output:
10
result:
ok answer is '10'
Test #8:
score: -100
Wrong Answer
time: 15ms
memory: 10740kb
input:
10 2 4 5 9 6 9 10 6 9 2 7 1100010100
output:
10
result:
wrong answer expected '9', found '10'