PythonでJOI難易度6を埋める #10

ioi - 国際情報オリンピック (IOI)

沼った．途中のACはちゃんと解いてないやつ．

• score = 与えられる各選手の得点
• final_score = 自分以外の選手が残りの問題を完答したときの得点() を昇順でsort
• sort_score = 与えられる得点を昇順でsort
• limit_num = 金メダルがもらえる人数
• index_final = final_scoreに二分探索(right)でscore[i]を挿入したときのindex
• index_sort = sort_scoreに二分探索(right)でscore[i]を挿入したときのindex

のときは，final_score = sort_scoreになることに注意
基本的な指針は，

• 自分以外の選手が残りの問題を完答しても(final_score)，自分の最初の点数がlimit_num以内 → 確定で貰える
• 自分だけが残りの問題を完答すれば，limit_num以内 → 可能性がある

．

score[i]がfinal_scoreに追加されるとき，されるので，の場合以外はscore[i]よりも大きい値が追加されることになる．なので，index_finalは自分が残りの問題を完答したときの得点も追加されてある状態でのindexなので，は，index_final - 1が順位となる．

これをすべての得点で行なえばよい．

from math import ceil
from bisect import bisect_right

k, n, m = map(int, input().split())
score = [int(input()) for _ in range(k)]

limit_num = ceil(k / 12)

sort_score = sorted(score)
now_rate = []
final_socre = []

for i in range(k):
    rate = bisect_right(sort_score, score[i])
    now_rate.append([i, k - rate])
    final_socre.append(score[i] + 100 * (n - m))

now_rate.sort()
final_socre.sort()

check = set([])
for i in range(k):
    if n == m:
        if k - bisect_right(final_socre, score[i]) < limit_num:
            print(i + 1)
    if n != m:
        if k - bisect_right(final_socre, score[i]) <= limit_num:
            print(i + 1)

print('--------')

for i in range(k):
    if bisect_right(sort_score, score[i] + 100 * (n - m)) > k - limit_num:
        print(i + 1)