LuoTianyi and the Show (Codeforces 1825C)
Tags: Greedy, sortings

There are $$$n$$$ people taking part in a show about VOCALOID. They will sit in the row of seats, numbered $$$1$$$ to $$$m$$$ from left to right.The $$$n$$$ people come and sit in order. Each person occupies a seat in one of three ways:  Sit in the seat next to the left of the leftmost person who is already sitting, or if seat $$$1$$$ is taken, then leave the show. If there is no one currently sitting, sit in seat $$$m$$$. Sit in the seat next to the right of the rightmost person who is already sitting, or if seat $$$m$$$ is taken, then leave the show. If there is no one currently sitting, sit in seat $$$1$$$. Sit in the seat numbered $$$x_i$$$. If this seat is taken, then leave the show. Now you want to know what is the maximum number of people that can take a seat, if you can let people into the show in any order?

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — the number of people and the number of seats.The second line of each test case contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$-2 \le x_i \le m$$$, $$$x_i \ne 0$$$), the $$$i$$$-th of which describes the way in which the $$$i$$$-th person occupies a seat: If $$$x_i=-1$$$, then $$$i$$$-th person takes the seat in the first way. If $$$x_i=-2$$$, then $$$i$$$-th person takes the seat in the second way. If $$$x_i > 0$$$, then the $$$i$$$-th person takes a seat in the third way, i.e. he wants to sit in the seat with the number $$$x_i$$$ or leave the show if it is occupied.. It is guaranteed that sum of $$$n$$$ and the sum of $$$m$$$ over all test cases don't exceed $$$10^5$$$.

Output: For each test case output a single integer — the maximum number of people who can occupy a seat.

Note: In the first test case, all the people want to occupy the $$$5$$$ seat, so only $$$1$$$ people can occupy the seat.In the second test case, we can let people in order $$$1, 2, 3, 4$$$, then all but the last person can take a seat.In the third test case, we can let people into the show in that order:Let the third person in:–––3––– Let the fourth person in:–––34–– Let the fifth person in:–––345– Let the first person in:––1345– Let the second person in:–21345–Thus, all $$$5$$$ people took seats.In the fifth test case, we can let people into the show in this order:Let the fourth person in:––––4– Let the third person in:–––34– Let the sixth person in, he'll leave the show because he takes the third seat the third way and has to sit in the $$$4$$$ seat, but it's already taken:–––34–Let the fifth person in:––534–Let the first person in:–1534–Let the second person in:21534–Thus, $$$5$$$ of people took seats.In the seventh test case, we can let people into the show in this order:Let the third person in:3––––––Let the fourth person in:34––––– Let the fifth person in:345–––– Let the sixth person in:3456––– Let the first person in:34561––Let the second person in, he will leave the show because he occupies the first way, but the $$$1$$$ seat is taken:34561––Thus, $$$5$$$ people took seats.

Sample Inputs:
10
3 10
5 5 5
4 6
1 -2 -2 1
5 7
-1 -1 4 -2 -2
6 7
5 -2 -2 -2 -2 -2
6 6
-1 1 4 5 -1 4
6 8
-1 -1 -1 3 -1 -2
6 7
5 -1 -2 -2 -2 -2
3 1
-2 -2 1
2 5
5 -2
1 2
-1

Sample Outputs:
1
3
5
6
5
5
5
1
2
1

Solution (Python):
import sys, threading, bisect, heapq, math, copy
from heapq import heappush, heappop
from functools import cmp_to_key as ctk, lru_cache
from collections import defaultdict, deque
readline = sys.stdin.readline
read = lambda : [int(x) for x in readline().split()]
alloc = lambda dfv, *s: len(s) != 1 and [alloc(dfv, *s[1:]) for _ in range(int(s[0]))] or [dfv] * int(s[0])
show = lambda arr: print(' '.join(map(str, arr)))
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    for _wzl_ in range(int(input())):
        (n, m) = read()
        arr = read()
        A = B = 0
        st = set()
        for x in arr:
            if x == -1:
                A += 1
            elif x == -2:
                B += 1
            else:
                st.add(x)
        C = sorted(list(st))
        res = 0
        res = max(res, min(m, A), min(m, B))
        res = max(res, min(m, B + len(C)))
        res = max(res, min(m, A + len(C)))
        for (i, x) in enumerate(C):
            res = max(res, min(x - 1, i + A) + 1 + min(m - x, len(C) - 1 - i + B))
        print(res)
main()

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, m) = readInts()
    (arr, three, tmp) = (readList(), [False] * (m + 1), [])
    one = two = 0
    for i in range(n):
        if arr[i] == -1:
            one += 1
        elif arr[i] == -2:
            two += 1
        else:
            if three[arr[i]]:
                continue
            three[arr[i]] = True
            tmp.append(arr[i])
    tmp.sort()
    ans = n = len(tmp)
    for i in range(n):
        curr = tmp[i]
        (left, right) = (min(one, curr - 1 - i), min(m - curr - (n - 1 - i), two))
        ans = max(ans, n + left + right)
    if one:
        if tmp and tmp[-1] == m:
            r = m - 1 - (n - 1)
            ans = max(min(r, one - 1) + n, ans)
        else:
            r = m - 1 - n
            ans = max(min(r, one - 1) + n + 1, ans)
    if two:
        if tmp and tmp[0] == 1:
            r = m - 1 - (n - 1)
            ans = max(min(r, two - 1) + n, ans)
        else:
            r = m - 1 - n
            ans = max(min(r, two - 1) + n + 1, ans)
    return ans
for _ in range(int(input())):
    print(solve())

Solution (Python):
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    x = list(map(int, input().split()))
    left = x.count(-1)
    right = x.count(-2)
    neutral = [0] * m
    for a in x:
        if a > 0:
            neutral[a - 1] = 1
    mid = neutral.count(1)
    if mid == 0:
        print(min(max(left, right), m))
    elif left == 0:
        print(min(right + mid, m))
    elif right == 0:
        print(min(left + mid, m))
    else:
        ans = mid
        count = 0
        for i in range(m):
            if neutral[i] == 1:
                c = min(left, i - count)
                d = min(right, m - i - (mid - count))
                ans = max(ans, mid + c + d)
                count += 1
        c = min(left + mid, m)
        d = min(right + mid, m)
        print(max(ans, c, d))