Problem:


Score : 1200 points

Problem Statement

Let M be a positive integer.

You are given 2 N integers a_1, a_2, \ldots, a_{2 N}, where 0 \leq a_i < M for each i.

Consider dividing the 2 N integers into N pairs.
Here, each integer must belong to exactly one pair.

We define the ugliness of a pair (x, y) as (x + y) \mod M.
Let Z be the largest ugliness of the N pairs. Find the minimum possible value of Z.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq M \leq 10^9

0 \leq a_i < M

Input

Input is given from Standard Input in the following format:

N M
a_1 a_2 \cdots a_{2N}

Output

Print the minimum possible value of Z, where Z is the largest ugliness of the N pairs.

Sample Input 1

3 10
0 2 3 4 5 9

Sample Output 1

5

One solution is to form pairs (0, 5), (2, 3) and (4, 9), with ugliness 5, 5 and 3, respectively.

Sample Input 2

2 10
1 9 1 9

Sample Output 2

0

Pairs (1, 9) and (1, 9) should be formed, with ugliness both 0.



Sample input:
3 10
0 2 3 4 5 9


Sample output:
5

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = sorted([int(x) for x in input().split()])

if n == 1:
    print(sum(a) % m)
    exit()


def chk(x):
    for i in range(2*x, 2*n):
        if i != 2*n - 1 - (i - 2*x) and a[i] + a[2*n-1-(i-2*x)] < m:
            return False
    for i in range(2*x):
        if i != 2*x-1-i and a[i] + a[2*x-1-i] >= m:
            return False
    return True


bottom = -1
top = n

while top - bottom > 1:
    mid = (top + bottom)//2
    if chk(mid):
        top = mid
    else:
        bottom = mid
    if top == 0:
        break

ans = -1

for i in range(2*top, 2*n):
    ans = max(ans, (a[i]+a[2*n-1-(i-2*top)]) % m)
for i in range(2*top):
    ans = max(ans, (a[i] + a[2*top-1-i]) % m)

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = sorted([int(x) for x in input().split()])

if n == 1:
    print(sum(a) % m)
    exit()


def chk(x):
    for i in range(2*x, 2*n):
        if i != 2*n - 1 - (i - 2*x) and a[i] + a[2*n-1-(i-2*x)] < m:
            return False
    for i in range(2*x):
        if i != 2*x-1-i and a[i] + a[2*x-1-i] >= m:
            return False
    return True


bottom = -1
top = n+1

while top - bottom > 1:
    mid = (top + bottom)//2
    if chk(mid):
        top = mid
    else:
        bottom = mid
    if top == 0:
        break
    if bottom == n:
        top = n
        break

ans = -1

for i in range(2*top, 2*n):
    ans = max(ans, (a[i]+a[2*n-1-(i-2*top)]) % m)
for i in range(2*top):
    ans = max(ans, (a[i] + a[2*top-1-i]) % m)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from itertools import combinations
from itertools import permutations

### 方針
### 実行時間は最大でも2N!で収まる気がする
### 最悪全ての組み合わせの数列に対して、上から2桁ずつ足し算してあまりを求め続けてその時の最大値を全部とって比較すればいい
### 流石に↑は嘘っぽいので、ひとつの数列を作成したい気がする


### a[0]:N a[1]:M
a = list(map(int,input().split()))
input = list(map(int,input().split()))

min=4
for i in permutations(input,len(input)):
    max=0
    for j in range(0,len(i),2):
        mod = (i[j]+i[j+1])%a[1]
        if max < mod:
            max=mod
    if min > max:
        min = max
print(min)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from itertools import combinations
from itertools import permutations

### 方針
### 実行時間は最大でも2N!で収まる気がする
### 最悪全ての組み合わせの数列に対して、上から2桁ずつ足し算してあまりを求め続けてその時の最大値を全部とって比較すればいい
### 流石に↑は嘘っぽいので、ひとつの数列を作成したい気がする


input=[1,9,1,9]

min=4
for i in permutations(input,len(input)):
    max=0
    for j in range(0,len(i),2):
        mod = (i[j]+i[j+1])%10
        if max < mod:
            max=mod
    if min > max:
        min = max
print(min)

Submission status: Wrong Answer

Solution code:
#22問行ったやつ

n, m = map(int, input().split())
a_ = [int(i) for i in input().split()]
med = m / 2
a = [i if (i < med) else (i - m) for i in a_]
a_med = [i for i in a_ if i == med]
ans = []
if len(a_med) % 2 != 0:
    a.append(med)
a = sorted(a)
for i in range(n):
    temp = a[i] + a[-i-1]
    ans.append(temp)
ans = [i % m for i in ans]
print(max(ans))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
med = m / 2
a_plus = [i for i in a if (i <= med)]
a_minus = [(i - m) for i in a  if (i > med)]
num = min(len(a_plus), len(a_minus))
a_plus.reverse()
a_minus.reverse()
ans = []
for i in range(num):
    ans.append(a_plus[i] + a_minus[i])
if len(a_plus) > num:
    a_temp = a_plus[num:]
elif len(a_minus) > num:
    a_temp = a_minus[num:]
else:
    a_temp = []
if len(a_temp) > 0:
    for i in range(0, int(len(a_temp)/2)):
        temp = a_temp[i] + a_temp[-i-1]
        ans.append(temp)
ans = [i % m for i in ans]
print(max(ans))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
med = m / 2
a = [i if (i <= med) else (i - m) for i in a]
a = sorted(a)
ans = []
for i in range(n):
    temp = a[i] + a[-i-1]
    ans.append(temp)
ans = [i % m for i in ans]
print(max(ans))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
med = m / 2
a = [i if (i <= med) else (i - m) for i in a]
a = sorted(a)
ans = []
for i in range(n):
    temp = a[i] + a[-i-1]
    ans.append(temp)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from itertools import combinations
from itertools import permutations

### 方針
### 実行時間は最大でも2N!で収まる気がする
### 最悪全ての組み合わせの数列に対して、上から2桁ずつ足し算してあまりを求め続けてその時の最大値を全部とって比較すればいい
### 流石に↑は嘘っぽいので、ひとつの数列を作成したい気がする


### a[0]:N a[1]:M
a = list(map(int,input().split()))
input = list(map(int,input().split()))

min=a[1]
for i in permutations(input,len(input)):
    max=0
    for j in range(0,len(i),2):
        mod = (i[j]+i[j+1])%a[1]
        if max < mod:
            max=mod
    if min > max:
        min = max
print(min)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = sorted([int(x) for x in input().split()])


def chk(x):
    for i in range(2*x, 2*n):
        if i != 2*n - 1 - (i - 2*x) and a[i] + a[2*n-1-(i-2*x)] < m:
            return False
    return True


bottom = -1
top = n

while top - bottom > 1:
    mid = (top + bottom)//2
    if chk(mid):
        top = mid
    else:
        bottom = mid

ans = -1

for i in range(2*top, 2*n):
    ans = max(ans, (a[i]+a[2*n-1-(i-2*top)]) % m)
for i in range(2*top):
    ans = max(ans, (a[i] + a[2*top-1-i]) % m)

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,M = map(int,readline().split())
A = np.array(read().split(),np.int64)

A.sort()

def test(n):
    if n >= N:
        return True
    # 左から 2n 個をペア、右から 2N - 2n 個をペア。
    # 右側がすべて M 以上ならTrue
    R = A[n+n:]
    return np.min(R + R[::-1]) >= M

right = N # True
left = -1
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

n = right
L = A[:n+n]
R = A[n+n:]
x = np.concatenate([L + L[::-1], R + R[::-1]])

answer = np.max(x % M)
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,M = map(int,readline().split())
A = np.array(read().split(),np.int64)

A.sort()

def test(n):
    if n >= N:
        return True
    # 左から 2n 個をペア、右から 2N - 2n 個をペア。
    # 右側がすべて M 以上ならTrue
    R = A[n+n:]
    return np.min(R + R[::-1]) >= M

right = N # True
left = -1
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

n = right
L = A[:n+n]
R = A[n+n:]
x = np.concatenate([L + L[::-1], R + R[::-1]])

answer = np.max(x % M)
print(answer)

Submission status: Accepted

Solution code:
def modulo_pairing(N: int, M: int, A: list)->int:
    A.sort()

    def check(n: int)->bool:
        '''2*n の位置を区切りとして、右側が全て赤のペアになることを確認する。
        '''
        for i in range(2*n, N+n):
            if A[i] + A[2*N+2*n-i-1] < M:
                return False
        return True

    l, r = -1, N+1
    while r - l > 1:
        m = (l + r) // 2
        if check(m):
            r = m
        else:
            l = m

    blue = [A[i]+A[2*r-i-1] for i in range(r)]
    red = [A[i]+A[2*N+2*r-i-1]-M for i in range(2*r, N+r)]

    return max(blue + red)


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = [int(s) for s in input().split()]

    ans = modulo_pairing(N, M, A)
    print(ans)

Submission status: Accepted

Solution code:
def check(k):
    ret = 0
    b = 2 * k - 1
    for j in range(k):
        t = aaa[j] + aaa[b - j]
        if t >= m:
            return -1
        ret = max(ret, t)
    b = 2 * k
    c = 2 * n - 1
    for j in range(n - k):
        t = aaa[b + j] + aaa[c - j]
        if t < m:
            return -2
        ret = max(ret, t - m)
    return ret


n, m = map(int, input().split())
aaa = sorted(map(int, input().split()))

l, r = 0, n
ans = -1
while l < r:
    mid = (l + r) // 2
    res = check(mid)
    if res == -1:
        r = mid
    elif res == -2:
        l = mid + 1
    else:
        ans = res
        r = mid
if ans == -1:
    ans = check(n)
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = sorted([int(x) for x in input().split()])

if n == 1:
    print(sum(a) % m)
    exit()


def chk(x):
    for i in range(2*x, 2*n):
        if i != 2*n - 1 - (i - 2*x) and a[i] + a[2*n-1-(i-2*x)] < m:
            return False
    for i in range(2*x):
        if i != 2*x-1-i and a[i] + a[2*x-1-i] >= m:
            return False
    return True


bottom = -1
top = n+1

while top - bottom > 1:
    mid = (top + bottom)//2
    if chk(mid):
        top = mid
    else:
        bottom = mid
    if top == 0:
        break

ans = -1

for i in range(2*top, 2*n):
    ans = max(ans, (a[i]+a[2*n-1-(i-2*top)]) % m)
for i in range(2*top):
    ans = max(ans, (a[i] + a[2*top-1-i]) % m)

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = map(int, input().split())
size = 2 * A

MOD_A = []
for a in A:
    MOD_A.append(a % M)

ans = 0
MOD_A.sort(reverse=True)
while len(MOD_A) > 0:
    ma = MOD_A.pop(0)
    diff = M - ma
    lb = 0
    rb = len(MOD_A) - 1
    while rb - lb > 1:
        mid = (lb + rb) / 2
        if MOD_A[mid] > diff:
            rb = mid
        else:
            lb = mid
    ans += (ma + MOD_A[lb]) % M
    MOD_A.pop(lb)
print(ans)

Submission status: Runtime Error

Solution code:
#22問行ったやつ

n, m = map(int, input().split())
a_ = [int(i) for i in input().split()]
med = m / 2
a = [i if (i < med) else (i - m) for i in a_]
a_med = [i for i in a_ if i == med]
ans = []
if len(a_med) % 2 != 0:
    a.append(a_med)
a = sorted(a)
for i in range(n):
    temp = a[i] + a[-i-1]
    ans.append(temp)
ans = [i % m for i in ans]
print(max(ans))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))


def leftSearch(hist, index):
    if index>=len(hist): index=len(hist)-1
    while index>=0:
        if hist[index] > 0:
            return index
        index-=1
    return -1

def rightSearch(hist, index):
    if index<0: index=0
    while index<len(hist):
        if hist[index] > 0:
            return index
        index+=1
    return -1

target = 0

while True:
    couple = []
    max_val = max(a)
    # get hist
    hist = [0]*(max_val+1)
    for it in a:
        hist[it]+=1
    
    # main loop
    for _ in range(N):
        index_r = leftSearch(hist,len(hist))
        if index_r<0:
            break    
        hist[index_r]-=1

        index_l = leftSearch(hist, target+M-index_r)
        if (index_l+index_r)%M>target:
            index_l = leftSearch(hist, target-index_r)

        if index_l<0:
            break
        hist[index_l]-=1
        couple.append((index_l, index_r))
    # end    
    if len(couple) == N:
        #print(couple)
        break
    else:
        target += 1

lev=0
for it in couple:
    if lev < (it[0]+it[1])%M:
        lev =(it[0]+it[1])%M
        
print(lev)

Submission status: Runtime Error

Solution code:
n = int(input())
list = []
a = []
for i in range(n):
  list.append(int(input))

for i in range(1, n):
  for j in range(1, i):
    if list[i] == j:
      a.insert(j, j)

if a == list:
  for i in range(n):
    print(list[i])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
med = m / 2
a_plus = [i for i in a if (i <= med)]
a_minus = [(i - m) for i in a  if (i > med)]
num = min(len(a_plus), len(a_minus))
a_plus.reverse()
a_minus.reverse()
ans = []
for i in range(num):
    ans.append(a_plus[i] + a_minus[i])
if len(a_plus) > num:
    a_temp = a_plus[num:]
elif len(a_minus) > num:
    a_temp = a_minus[num:]
if a_temp:
    for i in range(0, int(len(a_temp)/2)):
        temp = a_temp[i] + a_temp[-i-1]
        ans.append(temp)
ans = [i % m for i in ans]
print(max(ans))