PAST3J

from Third Algorithm Practical Skills Test PAST3J

• The question to answer who takes which number when there are several agents in a row who only take it when the number flowing in is greater than any of those they have taken so far.
• Each agent has a numerical value that it will take if it is greater than this, and it should return "the leftmost agent with a value less than the flowing numerical value x".
  • So this is an efficient search from a sorted array.
  • I looked up the bisect search method in Python and found bisect in the standard library, so I used it for the first time. python

from bisect import bisect_right
N, M = [int(x) for x in input().split()]
XS = [int(x) for x in input().split()]

scores = [0] * N

for x in XS:
    # need to nagate to keep asc. order
    # print("come", x)
    i = bisect_right(scores, -x)
    if i == N:
        print(-1)
    else:
        print(i + 1)
        scores[i] = -x
        # print(scores)

This page is auto-translated from /nishio/PAST3J using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.