Problem:


Score : 500 points

Problem Statement

There are N cards. The i-th card has an integer A_i written on it.
For any two cards, the integers on those cards are different.

Using these cards, Takahashi and Aoki will play the following game:

Aoki chooses an integer x.

Starting from Takahashi, the two players alternately take a card. The card should be chosen in the following manner:

Takahashi should take the card with the largest integer among the remaining card.

Aoki should take the card with the integer closest to x among the remaining card. If there are multiple such cards, he should take the card with the smallest integer among those cards.

The game ends when there is no card remaining.

You are given Q candidates for the value of x: X_1, X_2, ..., X_Q.
For each i (1 \leq i \leq Q), find the sum of the integers written on the cards that Takahashi will take if Aoki chooses x = X_i.

Constraints

2 \leq N \leq 100 000

1 \leq Q \leq 100 000

1 \leq A_1 < A_2 < ... < A_N \leq 10^9

1 \leq X_i \leq 10^9 (1 \leq i \leq Q)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 ... A_N
X_1
X_2
:
X_Q

Output

Print Q lines. The i-th line (1 \leq i \leq Q) should contain the answer for x = X_i.

Sample Input 1

5 5
3 5 7 11 13
1
4
9
10
13

Sample Output 1

31
31
27
23
23

For example, when x = X_3(= 9), the game proceeds as follows:

Takahashi takes the card with 13.

Aoki takes the card with 7.

Takahashi takes the card with 11.

Aoki takes the card with 5.

Takahashi takes the card with 3.

Thus, 13 + 11 + 3 = 27 should be printed on the third line.

Sample Input 2

4 3
10 20 30 40
2
34
34

Sample Output 2

70
60
60



Sample input:
5 5
3 5 7 11 13
1
4
9
10
13


Sample output:
31
31
27
23
23

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    # from pickle import dumps
    # from queue import PriorityQueue, Queue


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def main():
    n, q = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))

    alt_sum_1 = [0]
    alt_sum_2 = [0]
    pref_sums = [0]
    for i in range(n):
        if i % 2 == 0:
            alt_sum_1.append(alt_sum_1[-1] + a[i])
        else:
            alt_sum_2.append(alt_sum_2[-1] + a[i])
        pref_sums.append(pref_sums[-1] + a[i])

    for _ in range(q):
        x = int(input())
        lo, hi = 0, 10**9 + 1
        while lo < hi:
            mi = (lo + hi) // 2
            left, right = bisect_left(a, x - mi), bisect_left(a, x + mi)

            if right - left >= len(a) - right - (n % 2):
                hi = mi
            else:
                lo = mi + 1

        left, right = bisect_left(a, x - lo), bisect_left(a, x + lo)
        x = pref_sums[-1] - pref_sums[right]

        if right - left == len(a) - right:
            if left % 2 == 0:
                x += alt_sum_2[left // 2]
            else:
                x += alt_sum_1[(left - 1) // 2 + 1]
        else:
            if left % 2 == 0:
                x += alt_sum_1[left // 2]
            else:
                x += alt_sum_2[(left - 1) // 2]

        print(x)


if __name__ == '__main__':
    sync_with_stdio(False)
    main()

Submission status: Wrong Answer

Solution code:
N, Q = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
SA = [0] * (N+1)
KA = [0] * (N+1)
KA[0] = A[0]
KA[1] = A[1]

for i in range(N):
    SA[i+1] = SA[i] + A[i]
for i in range(N-2):
    KA[i+2] = KA[i] + A[i+2]

B = [0] * ((N+1)//2)
Su =  [0] * ((N+1)//2)
Su[0] = SA[N] - SA[N - (N+1)//2]
for i in range(2, (N+1)//2+1):
    border = (A[N-i] + A[N -2*i+1] + 1)//2
    sums = SA[N] - SA[N-i] + KA[N-2*i+1]

    B[(N+1)//2-i-1] = border
    Su[(N+1)//2-i-1] = sums

import bisect

B = B[1:]
print(B,Su)
for i in range(Q):
    x = int(input())
    a = bisect.bisect_left(B, x)
    print(Su[a])

Submission status: Wrong Answer

Solution code:
def sa(num,x):
    return abs(num-x)

N,Q=(int(i) for i in input().split())
Atmp=[int(i) for i in input().split()]
X = [int(input()) for i in range(Q)]
for i in range(Q):
    taka = 0
    A=[[]for i in range(N)]
    for j in range(N):
        A[j]=Atmp[j]

    for j in range(int((N+1)/2)-1):
        #高橋君の番
        taka += A.pop(A.index(max(A)))
        #青木君の番
        # X[i]に最も近い数を求める
        s=A[0]
        t=A[0]
        flag=0
        #
        for k in range(len(A)):
            if A[k] >= X[i] and flag==0:
                t=A[k]
                s=A[k-1]
                flag=1
        
        #
        if X[i]-s > t-X[i]:
            A.pop(A.index(s))
        else:
            A.pop(A.index(t))
    taka+=A.pop(A.index(max(A)))
    print(taka)

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy

N, Q = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
A.sort()
X = []
for i in range(Q):
    X.append(int(input().strip()))

for i in range(Q):
    ans = 0
    a = np.array(A)
    a = a - X[i]
    a_ = np.absolute(a)
    a_ = a_.tolist()
    b = A
    
    for j in range(N):
        c = copy.copy(a_)
        d = copy.copy(b)
        if j%2 == 0:
            ans += max(d)
            x = max(d)
            d.remove(x)
            c.remove(c[len(c)-1])
        else:
            y = min(c)
            d.remove(d[c.index(y)])
            c.remove(y)

    print(ans)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
A = list(map(int,input().split()))
X = []
for i in range(Q):
    X.append(int(input()))

# 高橋君が右から最大とれる数
max_cnt = (N+1)//2
# 配列
taka = [0]*max_cnt
for i in range(1,max_cnt):
    # この値より
    taka[i] = (A[N-1-i] + A[N-1-i*2])/2

# 右からの累積和
S = [0]*N
S[N-1] = A[N-1]
for i in range(1,N):
    S[N-1-i] = S[N-i]+ A[N-1-i]
T = [0]*N
if N%2==0:
    T[0]=A[1]
    T[1]=A[1]
    for i in range(1,N//2):
        T[i*2] = T[i*2-1] + A[i*2]
        T[i*2+1] = T[i*2-1] + A[i*2]
else:
    T[0]=A[0]
    T[1]=A[0]
    for i in range(1,N//2):
        T[i*2] = T[i*2-1] + A[i*2+1]
        T[i*2+1] = T[i*2-1] + A[i*2+1]


for i in range(Q):
    getr = 0
    for j in range(1,len(taka)):
        if X[i] > taka[j]:
            getr = j
            break
    if getr==0:
        print(S[N-max_cnt])
    else:
        print(S[N-j],T[N-1-j*2])

Submission status: Wrong Answer

Solution code:
def binsearch(A, x):
    left = 0
    right = len(A) - 1
    while left < right:
        center = (left + right) // 2
        if x <= A[center]:
            right = center
        else:
            left = center + 1
    return left


def emulate(A, x, tmp, cumsum, cumsum_skip):
    if A[-2] < x:
        return cumsum_skip[len(A) - 1]
    small = 0
    big = A[-1] - x
    b = 0
    e = 0
    while small < big:
        mid = (small + big) // 2
        b = binsearch(A, x-mid)
        e = binsearch(A, x+mid)
        if A[e] > x+mid:
            e -= 1
        b = min(b, e)
        if b <= e and e-b+1 == len(A)-e-1 or e-b+1 == len(A)-e-1 - 1:
            break
        if e-b+1 < len(A)-e-2:
            small = mid + 1
        else:
            big = mid
    retval = 0
    if b >= 1:
        retval += cumsum_skip[b-1]
    retval += cumsum[len(A)-1] - cumsum[e]
    return retval


def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    tmp = sum(A[-1::-2])
    cumsum = [0] * N
    cumsum_skip = [0] * N
    cumsum[0] = A[0]
    cumsum_skip[0] = A[0] if N % 2 == 1 else 0
    for i in range(1, N):
        cumsum[i] = cumsum[i-1] + A[i]
        if (N - i) % 2 == 1:
            cumsum_skip[i] = cumsum_skip[i-1] + A[i]
        else:
            cumsum_skip[i] = cumsum_skip[i-1]
    for _ in range(Q):
        x = int(input())
        print(emulate(A, x, tmp, cumsum, cumsum_skip))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
A = list(map(int,input().split()))
X = []
for i in range(Q):
    X.append(int(input()))

# 高橋君が右から最大とれる数
max_cnt = (N+1)//2
# 配列
taka = [0]*max_cnt
for i in range(1,max_cnt):
    # この値より
    taka[i] = (A[N-1-i] + A[N-1-i*2])/2

# 右からの累積和
S = [0]*N
S[N-1] = A[N-1]
for i in range(1,N):
    S[N-1-i] = S[N-i]+ A[N-1-i]
T = [0]*N
if N%2==0:
    T[0]=A[1]
    T[1]=A[1]
    for i in range(1,N//2):
        T[i*2] = T[i*2-1] + A[i*2]
        T[i*2+1] = T[i*2-1] + A[i*2]
else:
    T[0]=A[0]
    T[1]=A[0]
    for i in range(1,N//2):
        T[i*2] = T[i*2-1] + A[i*2+1]
        T[i*2+1] = T[i*2-1] + A[i*2+1]


for i in range(Q):
    getr = 0
    for j in range(1,len(taka)):
        if X[i] > taka[j]:
            getr = j
            break
    if getr==0:
        print(S[N-max_cnt])
    else:
        print(S[N-j],T[N-1-j*2])
print(T)

Submission status: Wrong Answer

Solution code:
import bisect
n,q= (int(i) for i in input().split())
a = list(int(i) for i in input().split())
x = [int(input()) for i in range(q)] 
ans = []
if n %2 == 0:
 judgeb = (n//2)-1 
 judgea = n//2
 for i in range(q):
  if abs(x[i]-a[judgeb]) <= abs(x[i]-a[judgea]):
   print(sum(a[judgea::]))
  else:
   print(sum(a[judgea::])+a[judgeb]-a[judgea])

else:
 judgeb = (n//2)-1 
 judgea = n//2 
 judgec = judgea+1
 for i in range(q):
  if abs(x[i]-a[judgeb]) <= abs(x[i]-a[judgea]):
   print (sum(a[judgea::]))
  elif abs(x[i]-a[judgeb]) > abs(x[i]-a[judgea]) and abs(x[i]-a[judgec]) >= abs(x[i]-a[judgea]):
   print (sum(a[judgea::])+2*(a[judgeb]-a[judgea]))
  else:
   print (sum(a[judgea::])+2*(a[judgea]-a[judgec]))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect, bisect_left
n, q = map(int, input().split())
a = list(map(int, input().split()))
s = [0] 
#i~jの和: s[j+1]-s[i]
for p in a:
	s.append(s[-1] + p)
oe = [a[0], a[1]]
#oe[i]: range(i, -1, -2)の和
for i in range(2, n):
	oe.append(oe[-2]+a[i])
if n == 2:
	for _ in range(q):
		print(a[1])
	sys.exit()
elif n <= 4:
	for _ in range(q):
		x = int(input())
		if x <= (a[n-2]+a[n-3])/2:
			print(a[-1]+a[-2])
		else:
			print(oe[n-1])
	sys.exit()

def search(k):
	k_ind = bisect_left(a, x - abs(x - a[n-1-k]))
	if n-1-k - k_ind + 1 <= k:
		return True
	else:
		return False

for _ in range(q):
	x = int(input())
	if x > (a[n-2]+a[n-3])/2:
		print(oe[n-1])
	elif x > (a[n-3]+a[n-4])/2:
		print(a[-1]+a[-2]+oe[n-5])
	else:
		x_ind = bisect_left(a, x)
		l, r = 0, n-x_ind
		m = (l+r)//2
		while True:
			if search(m) == True:
				r = m
				m = (l+r)//2
			elif search(m+1) == False:
				#if m+1 == M:
					#m = -1
					#break
				l = m+1
				m = (l+r)//2
			else:
				break
		ans = s[n]-s[n-m-1]
		if m+1 < (n+1)//2:
			ans += oe[n-(2*m+2)]
		print(ans)

Submission status: Wrong Answer

Solution code:
n,q=(int(i) for i in input().split())
a=[int(i) for i in input().split()]
x=[int(input()) for i in range(q)] 
#print(n,q,a,x)
a.reverse()
#print(a)

cnt=-(-len(a)//2)

for k in range(len(x)):
    anst=a[0]
    j=0
    for i in range(cnt-1):
        j+=1               
        if x[k] < a[j]:
            anst+=a[j]    
        else:
            j+=1
            anst+=a[j]            
    print(anst)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    # from pickle import dumps
    # from queue import PriorityQueue, Queue


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def main():
    n, q = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))

    alt_sum_1 = [0]
    alt_sum_2 = [0]
    pref_sums = [0]
    for i in range(n):
        if i % 2 == 0:
            alt_sum_1.append(alt_sum_1[-1] + a[i])
        else:
            alt_sum_2.append(alt_sum_2[-1] + a[i])
        pref_sums.append(pref_sums[-1] + a[i])

    for _ in range(q):
        x = int(input())
        lo, hi = 0, 10**9 + 1
        while lo < hi:
            mi = (lo + hi) // 2
            left, right = bisect_left(a, x - mi), bisect_left(a, x + mi)

            if right - left >= len(a) - right - (n % 2):
                hi = mi
            else:
                lo = mi + 1

        left, right = bisect_left(a, x - lo), bisect_left(a, x + lo)
        x = pref_sums[-1] - pref_sums[right]

        if right - left == len(a) - right:
            if left % 2 == 0:
                x += alt_sum_2[left // 2]
            else:
                x += alt_sum_1[(left + 1) // 2]
        else:
            if left % 2 == 0:
                x += alt_sum_1[left // 2]
            else:
                x += alt_sum_2[left // 2]

        print(x)


if __name__ == '__main__':
    sync_with_stdio(False)
    main()

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


N, Q = il()
A_ = il()
X = imi(Q)
min_pos = []
for x in X:
    aoki = [abs(a - x) for a in A_[:-1]]
    min_pos.append(np.argmin(aoki))
table = {m: 0 for m in min_pos}

for i, x in enumerate(X):
    if table[min_pos[i]] != 0:
        print(table[min_pos[i]])
        continue
    takahashi = 0
    A = A_[:]
    while A:
        takahashi += A.pop()
        if A:
            aoki = [abs(a - x) for a in A]
            A.remove(A[np.argmin(aoki)])
    table[min_pos[i]] = takahashi
    print(takahashi)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    # from pickle import dumps
    # from queue import PriorityQueue, Queue


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def main():
    n, q = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))

    alt_sum_1 = [0]
    alt_sum_2 = [0]
    pref_sums = [0]
    for i in range(n):
        if i % 2 == 0:
            alt_sum_1.append(alt_sum_1[-1] + a[i])
        else:
            alt_sum_2.append(alt_sum_2[-1] + a[i])
        pref_sums.append(pref_sums[-1] + a[i])

    for _ in range(q):
        x = int(input())
        lo, hi = 0, 10**9 + 1
        while lo < hi:
            mi = (lo + hi) // 2
            left, right = bisect_left(a, x - mi), bisect_left(a, x + mi)

            if right - left >= len(a) - right - (n % 2):
                hi = mi
            else:
                lo = mi + 1

        left, right = bisect_left(a, x - lo), bisect_left(a, x + lo)
        x = pref_sums[-1] - pref_sums[right]

        if right - left == len(a) - right:
            if left % 2 == 0:
                x += alt_sum_2[left // 2]
            else:
                x += alt_sum_1[(left + 1) // 2]
        else:
            if left % 2 == 0:
                x += alt_sum_1[(left + 1) // 2]
            else:
                x += alt_sum_2[left // 2]

        print(x)


if __name__ == '__main__':
    sync_with_stdio(False)
    main()

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
A = [int(x) for x in input().split()]
B = [a for a in A]
for i in range(N - 2, -1, -1):
  B[i] += B[i + 1]
C = [a for a in A]
for i in range(2, N):
  C[i] += C[i - 2]
D = [0 for i in range(N)]
for i in range(1, N + 1):
  if N - 1 - 2 * i < 0:
    break
  D[N - i] = -(-(A[N - 1 - i] + A[N - 1 - 2 * i]) // 2)
E = [b for b in B]
for i in range(1, N + 1):
  if N - 2 * i - 1 < 0:
    break
  E[N - i] += C[N - 2 * i - 1]
def binsearch(upper, lower, x):
  if x > D[upper]:
    return upper
  if upper - lower == 1:
    return lower
  else:
    mid = (upper + lower) // 2
    if D[mid] < x:
      return binsearch(upper, mid, x)
    else:
      return binsearch(mid, lower, x)
for q in range(Q):
  x = int(input())
  print(E[binsearch(N - 1, 0, x)])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    # from pickle import dumps
    # from queue import PriorityQueue, Queue


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def main():
    n, q = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))

    alt_sum_1 = [0]
    alt_sum_2 = [0]
    pref_sums = [0]
    for i in range(n):
        if i % 2 == 0:
            alt_sum_1.append(alt_sum_1[-1] + a[i])
        else:
            alt_sum_2.append(alt_sum_2[-1] + a[i])
        pref_sums.append(pref_sums[-1] + a[i])

    for _ in range(q):
        x = int(input())
        lo, hi = 0, 10**9 + 1
        while lo < hi:
            mi = (lo + hi) // 2
            left, right = bisect_left(a, x - mi), bisect_left(a, x + mi)

            if right - left >= len(a) - right - (n % 2):
                hi = mi
            else:
                lo = mi + 1

        left, right = bisect_left(a, x - lo), bisect_left(a, x + lo)
        x = pref_sums[-1] - pref_sums[right]

        if right - left == len(a) - right:
            if left % 2 == 0:
                x += alt_sum_2[left // 2]
            else:
                x += alt_sum_1[(left + 1) // 2]
        else:
            if left % 2 == 0:
                x += alt_sum_1[left // 2]
            else:
                x += alt_sum_2[(left + 1) // 2]

        print(x)


if __name__ == '__main__':
    sync_with_stdio(False)
    main()

Submission status: Wrong Answer

Solution code:
import copy

N, Q = map(int, input().split())
master_A = list(map(int, input().split()))

X = [int(input()) for _ in range(Q)]


for x in X:
    # start game
    A = copy.copy(master_A)

    takashi = 0

    aoki_pointer = 0
    for a in range(len(A)):
        if A[a] > x:
            break
        aoki_pointer = a

    while len(A) > 0:
        # takaeshi turn
        takashi += A[-1]
        del A[-1]

        # aoki turn
        if len(A) > 0:
            del_target = min(len(A) - 1, aoki_pointer)
            del A[del_target]

    print(takashi)

Submission status: Wrong Answer

Solution code:
import bisect
n,q=map(int,input().split())
a=list(map(int,input().split()))
x=[0]*q
ans=[0]*q
for i in range(q):
    x[i]=int(input())

aa=0
k=a[n//2:]
aa=sum(k)
    
bb=0
c=list(a)
while len(c)>0:
    bb+=c[len(c)-1]
    c.pop()
    if len(c)>0:
        c.pop()

for i in range(q):
    b=list(a)
    xx=x[i]
    sum=0
    ll=bisect.bisect_left(b, xx)-1
    if ll<=len(b)//4:
        ans[i]=aa
    elif ll>len(b)//2+len(b)//4+1:
        ans[i]=bb
    else:
        while len(b)>0:
            sum+=b[len(b)-1]
            b.pop()
            if len(b)>0:
                ll=bisect.bisect_left(b, xx)-1
                rr=ll+1
                if ll>=len(b)-1:
                    b.pop()
                elif abs(b[rr]-xx)<abs(b[ll]-xx):
                    b.pop(rr)    
                else:
                    b.pop(ll)
        ans[i]=sum
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import bisect
n,q=map(int,input().split())
a=list(map(int,input().split()))
x=[0]*q
ans=[0]*q
for i in range(q):
    x[i]=int(input())

aa=0
k=a[n//2:]
aa=sum(k)
    
bb=0
c=list(a)
while len(c)>0:
    bb+=c[len(c)-1]
    c.pop()
    if len(c)>0:
        c.pop()

for i in range(q):
    b=list(a)
    xx=x[i]
    sum=0
    ll=bisect.bisect_left(b, xx)-1
    if ll<=len(b)//4:
        ans[i]=aa
    elif ll>=len(b)//2+len(b)//4:
        ans[i]=bb
    else:
        while len(b)>0:
            sum+=b[len(b)-1]
            b.pop()
            if len(b)>0:
                ll=bisect.bisect_left(b, xx)-1
                rr=ll+1
                if ll>=len(b)-1:
                    b.pop()
                elif abs(b[rr]-xx)<abs(b[ll]-xx):
                    b.pop(rr)    
                else:
                    b.pop(ll)
        ans[i]=sum
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import copy

N, Q = map(int, input().split())
Alist = list(map(int, input().split()))

Xlist = []
sumT = 0


for i in range(Q):
    Xtmp = int(input())
    Xlist.append(Xtmp)


for i in range(Q):
    Tlist = 0
    A = copy.deepcopy(Alist)
    Adifflist = []


    if Xlist[i] <= A[0]:
        a = len(A)//2
        print(sum(A[a:]))

    elif A[-1] <= Xlist[i]:
        for s in range(len(A)):
            if s % 2 == 0:
                sumT += A[len(A)-1-s]
        print(sumT)

    
    else:
        Acount = 0

        for j in range(len(A)):
            Adifflist.append([abs(A[j]-Xlist[i]), A[j]])

        Adifflist.sort(reverse=False)
            
        while 1:
            Ttmp = A.pop(-1)
            Tlist += Ttmp

            if A == []:
                print(Tlist)
                break

            Adifflist.remove([abs(Ttmp-Xlist[i]), Ttmp])

            Atmp = Adifflist[Acount][1]
            Acount += 1
            A.remove(Atmp)

            if A == []:
                print(Tlist)
                break

Submission status: Wrong Answer

Solution code:
import numpy as np
N,Q = map(int,input().split())
Alist_z = np.array(list(map(int,input().split())))
Qlist = np.array([int(input()) for _ in range(Q)])

for q in Qlist:
    TAKA = []
    Alist = Alist_z
    kais = N//2
    for i in range(kais):
        max = Alist.max()
        TAKA.append(max)
        Alist = Alist[~(Alist==max)]
        sa = abs(Alist-q).min()
        min = sa.min()
        ind = np.where(sa == min)
        Atest = list(Alist)
        Atest.remove(Alist[ind[0][0]])
        Alist = np.array(Atest)
    if N%2 != 0:
        TAKA.append(Alist[0])
    print(sum(TAKA))

Submission status: Wrong Answer

Solution code:
N, Q = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
for i in range(Q):
  B = A.copy()
  X = int(input())
  ans = 0
  riv = 0
  for j in range(N):
    if len(B) < 1:
      break
    ans += B.pop(-1)
    if len(B) < 2:
      break
    ak = 0
    if abs(B[-1]-X) < abs(B[0]-X):
      ak = len(B)-1
    for l in range(len(B)-1):
      if B[l+1] - X > 0:
        if (X - B[l]) > (B[l+1] - X):
          ak = l+1
        else:
          ak = l
    del B[ak]
  print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
n,q = map(int, input().split())
a = list(map(int, input().split()))
x=[]
for i in range(0,q):
  x.append(int(input()))
x.sort()

def findinx(l,n):
  idx=0
  v=1000000
  for i in range(0,len(l)):
    if v > abs(l[i]-n):
      idx=i
      v = abs(l[i]-n)
  return idx
    
for xii in range(0,q):
  xi=x[xii]
  y=a.copy()
  r=0
  while len(y)>0:
    val=y.pop()
    r=r+val
    if len(y)==0:
      break
    index = findinx(y,xi)
    y.pop(index)
  print(r)

Submission status: Wrong Answer

Solution code:
import bisect

N, Q = map(int, input().split())

A = list(map(int, input().split()))

A.sort()

ansers = []
for i in range(Q):
    ans = 0
    X = int(input())
    near_X = bisect.bisect_left(A, X)
    a = A[0:near_X]
    b = A[near_X:N]
    while((len(a) > 0) or (len(b) > 0)):
        if len(b) > 0:
            ans += b[-1]
            b.pop(-1)
        else:
            ans += a[-1]
            a.pop(-1)

        if(len(a) <= 0 and len(b) <= 0):
            break

        if len(b) > 0:
            if len(a) > 0 and X - a[-1] <= b[-1] - X:
                a.pop(-1)
            else:
                b.pop(0)
        else:
            a.pop(-1)

    ansers.append(ans)

for i in range(Q):
    print(ansers[i])