QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#673440#8783. Cherry PickingmalkovskyWA 16ms10740kbPython31.9kb2024-10-24 22:23:322024-10-24 22:23:33

Judging History

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

  • [2024-10-24 22:23:33]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:10740kb
  • [2024-10-24 22:23:32]
  • 提交

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__()

详细

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'