Problem:


Score : 600 points

Problem Statement

Takahashi has N balls with positive integers written on them. The integer written on the i-th ball is A_i.
He would like to form some number of pairs such that the sum of the integers written on each pair of balls is a power of 2.
Note that a ball cannot belong to multiple pairs.
Find the maximum possible number of pairs that can be formed.

Here, a positive integer is said to be a power of 2 when it can be written as 2^t using some non-negative integer t.

Constraints

1 \leq N \leq 2\times 10^5

1 \leq A_i \leq 10^9

A_i is an integer.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible number of pairs such that the sum of the integers written on each pair of balls is a power of 2.

Sample Input 1

3
1 2 3

Sample Output 1

1

We can form one pair whose sum of the written numbers is 4 by pairing the first and third balls.
Note that we cannot pair the second ball with itself.

Sample Input 2

5
3 11 14 5 13

Sample Output 2

2



Sample input:
3
1 2 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
import itertools

N = int(raw_input())
n = map(int, raw_input().split())
number = 0

done_values=[]
for x,y in itertools.combinations(n, 2):
    if (x + y) % 2 == 0:
        if x not in done_values and y not in done_values:
            number +=1
            done_values.append(x)
            done_values.append(y)

print number

Submission status: Wrong Answer

Solution code:
#AGC030 B - Powers of two
import collections
import math
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
cnter=collections.Counter(A)
ans=0
for a in A:
    inv=2**(int(math.log2(a))+1)
    if cnter[a]==0:
        continue
    if cnter[a]>=2 and a==inv//2:
        cnter[a]=cnter[a]-2
        ans=ans+1
        continue
    if inv-a in cnter:
        cnter[inv-a]=cnter[inv-a]-1
        ans=ans+1
print(ans)

Submission status: Wrong Answer

Solution code:
#AGC030 B - Powers of two
import collections
import math
beki=[]
for i in range(1,32):
    beki.append(2**i)#bekiは２のべき乗の配列
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
cnter=collections.Counter(A)
ans=0
for a in A:
    inv=2**(int(math.log2(a))+1)
    if cnter[a]==0:
        continue
    if inv-a in cnter:
        cnter[inv-a]=cnter[inv-a]-1
        ans=ans+1
print(ans)

Submission status: Wrong Answer

Solution code:
#AGC030 B - Powers of two
beki=[]
for i in range(1,32):
    beki.append(2**i)#bekiは２のべき乗の配列
N=int(input())
A=input().split()
for i in range(N):
    A[i]=int(A[i])
for i in (reversed(beki)):
    B=A
    for j in B:
        if i//2<j<i:
            if i-j in B:
                A.remove(i-j)
                A.remove(j)
        if j==i//2:
            if B.count(j)>=2:
                A.remove(j)
                A.remove(j)
print((N-len(A))//2)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import Counter

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


def find(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return None


two_bekis = []
tmp = 1
while tmp < 2*10**9:
    two_bekis.append(tmp)
    tmp *= 2

ans = 0
cnt = Counter(A)
for i, a in enumerate(reversed(A)):
    idx = bisect.bisect_right(two_bekis, a)
    two_beki = two_bekis[idx]
    tmp = find(A, two_beki-a)
    if tmp is not None:
        if A[tmp] == a and cnt[A[tmp]] >= 2:
            ans += 1
            cnt[A[tmp]] -= 2
        elif A[tmp] != a and cnt[A[tmp]] >= 1:
            ans += 1
            cnt[A[tmp]] -= 1
            cnt[a] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import Counter

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


def find(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return None


two_bekis = []
tmp = 1
while True:
    if tmp > 2*10**9:
        break
    two_bekis.append(tmp)
    tmp *= 2

used = [False] * N
ans = 0
cnt = Counter(A)
for i, a in enumerate(reversed(A)):
    #if used[N-1-i]:
    #    continue
    idx = bisect.bisect_right(two_bekis, a)
    two_beki = two_bekis[idx]
    tmp = find(A, two_beki-a)
    if tmp is not None and not used[tmp] and tmp != N-i-1:
        if A[tmp]==a and cnt[A[tmp]]>=2:
            ans += 1
            cnt[A[tmp]] -= 2
        elif cnt[A[tmp]]>=1:
            ans += 1
            cnt[A[tmp]] -= 1
            cnt[a] -= 1
            #used[tmp] = True
            #used[N-i-1] = True
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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


def find(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return None


two_bekis = set()
tmp = 1
while True:
    if tmp > 2*10**9:
        break
    two_bekis.add(tmp)
    tmp *= 2

used = [False] * N
ans = 0
for i, a in enumerate(reversed(A)):
    for two_beki in two_bekis:
        tmp = find(A, two_beki-a)
        if tmp is not None and not used[tmp] and tmp != N-i-1:
            ans += 1
            used[tmp] = True
            used[N-i-1] = True
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
A = list(map(int, input().split()))
#N = 5
#A = [3, 11, 14, 5, 13]
A.sort()
#A = range(100000, 0, -1)

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return None


two_bekis = set()
tmp = 1
while True:
    if tmp>2*10**9:
        break
    two_bekis.add(tmp)
    tmp *= 2

used = [False] * N
ans = 0
for i, a in enumerate(reversed(A)):
    for two_beki in two_bekis:
        tmp = index(A, two_beki-a)
        if tmp is not None and not used[tmp]:
            ans += 1
            used[tmp] = True
            used[N-i-1] = True

        #print(two_beki, a, tmp)

#print(two_bekis)
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    data = sorted(list(map(int, input().split())),reverse=True)
    flag = [0 for _ in range(N)]
    ans=0
    for i in range(N):
        if flag[i] == 1:
            continue
        a = data[i]
        for j in range(i+1, N):
            tmp = data[i] + data[j]
            if not(tmp & (tmp-1)):
                ans+=1
                flag[j]=1
        flag[i]=1


    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    data = sorted(list(map(int, input().split())),reverse=True)
    flag = [0 for _ in range(N)]
    ans=0
    rep = int(N/2) + 1
    for i in range(rep):
        if flag[i] == 1:
            continue
        a = data[i]

        for j in range(1, N-i):
            tmp = data[i] + data[-j]
            if not(tmp & (tmp-1)):
                ans+=1
                flag[-j]=1
        flag[i]=1


    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    data = sorted(list(map(int, input().split())),reverse=True)
    flag = [0 for _ in range(N)]
    ans=0
    for i in range(N):
        if flag[i] == 1:
            continue
        a = data[i]
        for j in range(1, N-i):
            tmp = data[i] + data[-j]
            if not(tmp & (tmp-1)):
                ans+=1
                flag[-j]=1
        flag[i]=1


    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
b = []
for i in range(2):
  b += input('').split()
n = int(b[0])
l = b[1:]
l = [int(i) for i in l]
c = 0
for i in range(n):
  for j in range(n):
    if i>=j:
      pass
    else:
      a = float(l[i]+l[j])
      while a > 1.0:
        a /= 2
      if a == 1.0:
        c += 1
      else:
        pass
print(c)

Submission status: Wrong Answer

Solution code:
b = []
for i in range(2):
  b += input('').split()
n = int(b[0])
l = b[1:]
l = [int(i) for i in l]
c = 0
for i in range(n):
  for j in range(n):
    if i>=j:
      pass
    else:
      a = l[i]+l[j]
      while a > 1:
        a /= 2
      if a == 1:
        c += 1
      else:
        pass
print(c)

Submission status: Wrong Answer

Solution code:
import math
a=int(input())
o = []
e = []
x = list(map(int, input().split()))
for i in x:
    if i%2 ==0:e.append(i)
    else:o.append(i)
e.sort()
o.sort()
e = e[::-1]
o = o[::-1]
def cal(k):
    r=0
    p = 0
    l = len(k)
    if l <2:return 0
    else:
        i = 0
        while p!=l:
            for j in range(i+1,len(k)):
                lo = math.log2(k[i] + k[j])
                #print(lo,int(lo))
                #print(k[j],k[i])
                if lo == int(lo):
                    r+=1
                    #print(k[j],k[i])
                    #k.remove(k[j])
                    k.remove(k[i])
                    p+=1
                    #i -=1
                    break
            i+=1
            p+=1
    return r
print(cal(o)+cal(e))

Submission status: Wrong Answer

Solution code:
import math
a=int(input())
o = []
e = []
x = list(map(int, input().split()))
for i in x:
    if i%2 ==0:e.append(i)
    else:o.append(i)
e.sort()
o.sort()
e[::-1]
o[::-1]
def cal(k):
    r=0
    l = len(k)
    if l <2:return 0
    else:
        for i in range(l):
            for j in range(i,l):
                lo = math.log2(k[i] + k[j])
                #print(lo,int(lo))
                if lo == int(lo):
                    r+=1
                    break
    return r
print(cal(o)+cal(e))

Submission status: Wrong Answer

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

def is_even(N):
    if N%2 != 0:
        return False
    elif N // 2 == 1:
        return True
    else:
        return is_even(N // 2)

import itertools

list_combi = list(itertools.combinations(A_list,2))

import numpy as np

list_combi = np.array(list_combi).reshape(-1,2)

count = 0 
for i in list_combi:
    N = int(i[0])+int(i[1])
    
    if is_even(N) is True:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
count = 0
reg = 1
now = 0
for a in A:
    now = a
    a = -1
    if now == -1:
        continue
    reg = 1
    for j in reversed(range(0, 32)):
        reg *= 2
        if reg < now:
            continue
        else:
            try:
                A[A.index(reg - now)] = -1
                count += 1
                break
            except:
                break
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
count = 0
i = 0
reg = 1
while True:
    if i >= N - 1:
        break
    now = A.pop()
    if now == -1:
        continue
    reg = 1
    for j in range(0, 32, -1):
        reg *= 2
        if reg <= now:
            continue
        else:
            try:
                A[A.index(reg - now)] = -1
                count += 1
                i += 1
                break
            except:
                break
    i += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
count = 0
i = 0
reg = 1
while True:
    if i >= N - 1:
        break
    now = A.pop()
    if now == -1:
        continue
    reg = 1
    for j in range(32):
        reg *= 2
        if reg <= now:
            continue
        else:
            count += 1
            i += 1
    i += 1
print(count)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
numberList = []
numberList = list(map(int, input().split(" ")))
numberList.sort(reverse=True)
numberDict = {}

for number in numberList:
    if number not in numberDict:
        numberDict[number] = 0
    numberDict[number] += 1

ret = 0

for number in numberList:
    if numberDict[number] > 0:
#        print(number)
#        print(math.log(number,2))
        gap = 2 ** (int(math.log(number, 2)) + 1) - number
        if gap in numberDict and numberDict[gap] > 0:
            numberDict[gap] -= 1
            numberDict[number] -= 1
            ret += 1

print(ret)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
numberList = []
numberList = list(map(int, input().split(" ")))
numberList.sort(reverse=True)
numberDict = {}

for number in numberList:
    if number not in numberDict:
        numberDict[number] = 0
    numberDict[number] += 1

ret = 0

for number in numberList:
    if numberDict[number] > 0:
        gap = 2 ** (int(math.log(number, 2))) - number
        if gap in numberDict and numberDict[gap] > 0:
            numberDict[gap] -= 1
            numberDict[number] -= 1
            ret += 1

print(ret)

Submission status: Wrong Answer

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

def chk(n):
    for i in range(1, 31):
        if n / 2**i == 1:
            return True
    return False

ans = 0
trash = []
for i in range(N-1):
    if i in trash:
        continue
    for j in range(i+1, N):
        if j in trash:
            continue
        if (A[i] + A[j]) % 2 == 0:
            if chk(A[i] + A[j]) :
                ans += 1
                trash.append(j)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def solve(N, a):
    a.sort(reverse=True)
    da = defaultdict(int)
    for k in a:
        da[k] += 1
    i = 0
    c = 0
    for t in range(30, -1, -1):
        low = 2 ** (t - 1)
        high = 2 ** t
        while i < N and a[i] >= low:
            if a[i] in da and high - a[i] in da:
                v0 = da[a[i]]
                v1 = da[high - a[i]]
                c += min(v0, v1)
                v0 -= min(v0, v1)
                v1 -= min(v0, v1)
                da[a[i]] = v0
                da[high - a[i]] = v1
                if v0 == 0:
                     del da[a[i]]
                else:
                    da[a[i]] = v0
                if v1 == 0:
                     del da[high - a[i]]
                else:
                     da[high - a[i]] = v1
            i += 1
    return c

def test():
    import random
    N = 10**5
    #a = [random.randint(1, 10**9) for i in range(N)]
    a = [[3,5][i%2] for i in range(N)]
    print(solve(N, a))

if __name__ == '__main__':
    N = int(input())
    a = list(map(int, input().split()))
    print(solve(N, a))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
cnt = 0
l = []
flag = False
for i in range(N):
  #print("check:", A[i])
  if not A[i] & (A[i]-1):
    cnt += 1
  else:
    for j in l:
      if not (A[i]+j) & (A[i]+j-1):
        #print(A[i], j)
        l.remove(j)
        cnt += 1
        flag = True
        break
    if flag == False:
      l.append(A[i])
    else:
      flag = False

print(cnt)
#print(l)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().strip().split()))
cnt=0
for i in range(len(a)):
    for x in range(len(a)):
        if i==x:
            continue
        if a[i]==0 or a[x]==0:
            continue
        if not ((a[i]*a[x]) & (a[i]*a[x]-1))==0:
            a[i]=0
            a[x]=0
            cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import collections

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
c=collections.Counter(A)

pairCounter=0

beki=29
nibeki=2**beki

for i in range(N):
  target = A[i]
  if c[target] < 1:
    continue
    c[target]-= 1

    while (nibeki > target):
      beki-=1
      nibeki=2**beki

      pair = nibeki * 2 - target
      if pair in c.keys() and c[pair] > 0:
        c[pair]-= 1
        pairCounter+=1

        print(pairCounter)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
inputs = [int(i) for i in input().split()]

inputs.sort(reverse=True)
counter_inputs = Counter(inputs)
ans = 0

for item in inputs:
    counter_inputs[item] -= 1
    
    beki_max = 30
    while 2 ** beki_max > item:
        other = 2 ** beki_max - item
        if other in counter_inputs and counter_inputs[other] > 0:
            counter_inputs[other] -= 1
            ans += 1
        beki_max -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N=input()
A=map(int,raw_input().split())
import math
Result=[]

A.sort(reverse=True)
A_2=[int(math.log(a,2)) for a in A]
for i in range(N):
    if i in Result:
        continue
    for j in range(1,N):
        if j in Result:
            continue
        if A[i]+A[j]==2**(A_2[i]+1):
            Result.append(i)
            Result.append(j)

print len(Result)/2

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N = d_in()
A_list = np.array(ds_in())
A_list.sort()
EPSILON = 10**(-6)

cand_A = 2 ** (np.log2(A_list + EPSILON).astype(int) + 1) - A_list
idx = np.searchsorted(A_list, cand_A)
flag = np.zeros(N, dtype=int)

ans = 0
for i in range(N-1, -1, -1):
    if flag[i]:
        continue
    if idx[i] == i:
        continue
    if A_list[idx[i]] == cand_A[i]:
        ans += 1
        flag[idx[i]] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N = d_in()
A_list = np.array(ds_in())
A_list.sort()
EPSILON = 10**(-6)

cand_A = 2 ** (np.log2(A_list + EPSILON).astype(int) + 1) - A_list
idx = np.searchsorted(A_list, cand_A)
flag = np.zeros(N, dtype=int)

ans = 0
for i in range(N-1, -1, -1):
    print(flag)
    if flag[i]:
        continue
    if idx[i] == i:
        continue
    if A_list[idx[i]] == cand_A[i]:
        ans += 1
        flag[idx[i]] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
from bisect import bisect_left

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N = d_in()
A_list = ds_in()
A_list.sort()

ans = 0
while len(A_list) > 1:
    max_a = A_list.pop()
    binary = bin(max_a)
    if (1 << (len(binary)-3)) == A_list[-1]:
        del A_list[-1]
        ans += 1
    else:
        cand = (1 << (len(binary)-2)) - max_a
        idx = bisect_left(A_list, cand)
        if (idx < len(A_list)) and (cand == A_list[idx]):
            del A_list[idx]
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
from bisect import bisect_left

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N = d_in()
A_list = ds_in()
A_list.sort()

ans = 0
while len(A_list) > 1:
    max_a = A_list.pop()
    if max_a == A_list[-1]:
        del A_list[-1]
        ans += 1
    else:
        binary = bin(max_a)
        cand = (1 << (len(binary)-2)) - max_a
        idx = bisect_left(A_list, cand)
        if (idx < len(A_list)) and (cand == A_list[idx]):
            del A_list[idx]
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
from bisect import bisect_left

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N = d_in()
A_list = ds_in()

A_list.sort()

ans = 0
while len(A_list) > 0:
    max_a = A_list.pop()
    if bin(max_a)[3:].find('1') == -1:
        if max_a in A_list:
            ans += 1
    else:
        cand = 2 ** len(bin(max_a)[2:]) - max_a
        if cand in A_list:
            A_list.pop(bisect_left(A_list, cand))
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
A = [int(i) for i in input().split()]
A.sort()

res = []
for i in range(N-1, 0, -1):
    a = A[i]
    if a in res:
        continue
    k = len(bin(a)) - 2
    se = 2**k - a
    ind = bisect.bisect_left(A, se)
    if ind <= i - 1 and A[ind] == se:
        res.append(A[ind])

print(len(set(res)))

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
A = [int(i) for i in input().split()]
A.sort()

res = []
for i in range(N-1, 0, -1):
    a = A[i]
    k = len(bin(a)) - 2
    se = 2**k - a
    ind = bisect.bisect_left(A, se)
    if ind <= i - 1 and A[ind] == se:
        res.append(A[ind])
        
print(len(set(res)))

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
A = [int(i) for i in input().split()]
A.sort()

res = []
for i in range(N-1, 0, -1):
    a = A[i]
    k = len(bin(a)) - 2
    se = 2**k - a
    L = A[:i]
    ind = bisect.bisect_left(L, se)
    try:
        res.append(L[ind])
    except:
        continue

print(len(set(res)))

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
A = [int(i) for i in input().split()]
A.sort()

cc = 0
while True:
    if A:
        a = A.pop()
    else:
        break
    if not A:
        break
    for i in range(30):
        if a < 2 ** i:
            break
    se = 2**i - a
    res = bisect.bisect_left(A, se)
    try:
        if A[res] == se:
            A.pop(res)
            cc += 1
    except:
        pass

print(cc)

Submission status: Wrong Answer

Solution code:
N = int(input().rstrip())
A = [int(s) for s in input().rstrip().split()]
A.sort()

squared = [2]
tmp = 2
while tmp < 2 * 10**9:
    tmp *= 2
    squared.append(tmp)

cnt = 0
while A:
    max_num = A.pop()    
    for i in range(len(A)):
        summation = max_num + A[i]
        if summation in squared:
            cnt += 1
            A.pop(i)
            squared = squared[squared.index(summation):] 
            break

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

def getComplement(val):
	target = 1
	while target <= val:
		target <<= 1
	return target - val

def lowerBound(c, values, left, right):
	if left+1 > right:
		return None
	if left+1 == right:
		return left
	middle = (left + right) // 2
	if c > values[middle]:
		return lowerBound(c, values, left, middle)
	else: # c <= values[middle]
		return lowerBound(c, values, middle, right)

def maximumPairCount(values):
	n = len(values)
	values.sort(reverse=True)
	count = 0
	used = [False] * n
	for i in range(n):
		if used[i]:
			continue
		c = getComplement(values[i])
		cur = lowerBound(c, values, i+1, n)
		if cur is None or values[cur] != c:
			continue
		used[cur] = True
		count += 1
	return count

n = int(input())
values = list(map(int, input().split()))
print(maximumPairCount(values))

Submission status: Wrong Answer

Solution code:
import sys

def getComplement(val):
	target = 1
	while target < val:
		target <<= 1
	return target - val

def lowerBound(c, values, left, right):
	if left+1 > right:
		return None
	if left+1 == right:
		return left
	middle = (left + right + 1) // 2
	if c > values[middle]:
		return lowerBound(c, values, left, middle)
	else:
		return lowerBound(c, values, middle, right)

def maximumPairCount(values):
	n = len(values)
	values.sort(reverse=True)
	count = 0
	used = [False] * n
	for i in range(n):
		if used[i]:
			continue
		c = getComplement(values[i])
		cur = lowerBound(c, values, i+1, n)
		if cur is None or values[cur] != c:
			continue
		used[cur] = True
		count += 1
	return count

n = int(input())
values = list(map(int, input().split()))
print(maximumPairCount(values))

Submission status: Wrong Answer

Solution code:
import sys

def getComplement(val):
	target = 1
	while target < val:
		target <<= 1
	return target - val

def lowerBound(c, values, left, right):
	if left+1 > right:
		return None
	if left+1 == right:
		return left
	middle = (left + right) // 2
	if c > values[middle]:
		return lowerBound(c, values, left, middle)
	else:
		return lowerBound(c, values, middle, right)

def maximumPairCount(values):
	n = len(values)
	values.sort(reverse=True)
	count = 0
	used = [False] * n
	for i in range(n):
		if used[i]:
			continue
		c = getComplement(values[i])
		cur = lowerBound(c, values, i+1, n)
		if cur is None or values[cur] != c:
			continue
		used[cur] = True
		count += 1
	return count

n = int(input())
values = list(map(int, input().split()))
print(maximumPairCount(values))

Submission status: Wrong Answer

Solution code:
import sys

def getComplement(val):
	target = 1
	while target < val:
		target <<= 1
	return target - val

def lowerBound(c, values, left, right):
	if left+1 > right:
		return None
	if left+1 == right:
		return left
	middle = (left + right) // 2
	if values[middle] >= c:
		return lowerBound(c, values, middle, right)
	else:
		return lowerBound(c, values, left, middle)

def maximumPairCount(values):
	n = len(values)
	values.sort(reverse=True)
	count = 0
	used = [False] * n
	for i in range(n):
		if used[i]:
			continue
		c = getComplement(values[i])
		cur = lowerBound(c, values, i+1, n)
		if cur is None or values[cur] != c:
			continue
		used[cur] = True
		count += 1
	return count

n = int(input())
values = list(map(int, input().split()))
print(maximumPairCount(values))

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
A = sorted(list(map(int, input().split())))

ans = 0
for k in range(N-1,-1,-1):
    if A[k]==int(A[k]):
        b = 1
        while b < A[k]:
            b *= 2
        p = bisect.bisect_left(A,b-A[k])
        if p != k and A[p]+A[k] == b:
            ans += 1
            A[k] += 0.5
            A[p] -= 0.5
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
ball=[int(i) for i in input().split()]
ball.sort()
list1=[[]for i in range(n)]
count_list=[[0,i] for i in range(n)]
ans=0
for i in range(n-1):
    k=0
    for j in range(i+1,n):
        while 2**k<ball[i]+ball[j]:
            k+=1
        if 2**k==ball[i]+ball[j]:
            list1[i].append(j)
            list1[j].append(i)
            count_list[i][0]+=1
            count_list[j][0]+=1
while count_list!=[]:
    count_list.sort()
    while count_list[0][0]==0 and count_list!=[]:
        count_list.pop(0)
        if count_list==[]:
            break
    if count_list==[]:
        break
    cul=count_list[0][1]
    cul2=list1[count_list[0][1]][0]
    for i in range(len(list1)):
        if cul in list1[i]:
            list1[i].remove(cul)
            for j in range(len(count_list)):
                if count_list[j][1]==i:
                    count_list[j][0]-=1
                    break
        if cul2 in list1[i]:
            list1[i].remove(cul2)
            for j in range(len(count_list)):
                if count_list[j][1]==i:
                    count_list[j][0]-=1
                    break
    ans+=1
    count_list.pop(0)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
import math

n=int(input())
lst=list(map(int,input().split()))
lst.sort()
use=[False]*n
ans=0
for i in range(n-1,0,-1):
  if use[i]: continue 
  x=lst[i]
  diff=2**x.bit_length()-x
  j=bisect_right(lst,diff,0,i)
  if j!=0 and lst[j-1]==diff and not use[j-1]:
    ans+=1
    use[j-1]=True
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import math

n=int(input())
lst=list(map(int,input().split()))
lst.sort()
use=[False]*n
ans=0
for i in range(n-1,0,-1):
  if use[i]: continue 
  x=lst[i]
  diff=2**x.bit_length()-x
  j=bisect_left(lst,diff,0,i)
  if j!=0 and lst[j-1]==diff and not use[j-1]:
    ans+=1
    use[j-1]=True
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import math

n=int(input())
lst=list(map(int,input().split()))
lst.sort()
use=[False]*n
ans=0
for i in range(n-1,0,-1):
  x=lst[i]
  diff=2**x.bit_length()-x
  j=bisect_left(lst,diff,0,i)
  if j!=i and lst[j]==diff and not use[j]:
    ans+=1
    use[j]=True
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import math

n=int(input())
lst=list(map(int,input().split()))
lst.sort()
use=[False]*n
ans=0
for i in range(n-1,0,-1):
  x=lst[i]
  diff=2**x.bit_length()-x
  j=bisect_left(lst,diff,0,i-1)
  if j!=n and lst[j]==diff and not use[j]:
    ans+=1
    use[j]=True
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split(" "))),reverse=True)
#print(A)
from collections import defaultdict
import math

d = defaultdict(int)

for item in A:
  d[item]+=1
n=0
for item in A:
  remain = math.pow(2,math.floor(math.log2(item))+1)-item
  if remain  != item and d[remain]>0:
    d[remain]-=1
    n+=1
  if remain == item and d[remain]>1:
    d[remain]-=2
    n+=1
print(n)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split(" "))),reverse=True)
#print(A)
from collections import defaultdict
import math

d = defaultdict(int)

for item in A:
  d[item]+=1
n=0
for item in A:
  remain = math.pow(2,math.floor(math.log2(item))+1)-item
  if remain  != item  and d[remain]>0:
    d[remain]-=1
    n+=1
print(n)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split(" "))),reverse=True)
#print(A)
from collections import defaultdict
import math

d = defaultdict(int)

for item in A:
  d[item]+=1
n=0
for item in A:
  remain = math.pow(2,math.floor(math.log2(item))+1)-item
  if d[remain]>0:
    d[remain]-=1
    n+=1
print(n)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a = list(map(int,input().split()))

used = collections.Counter(a)
a.sort()
a.reverse()

two = [2]
i = 0
while two[i]*2 <= 2*10**9:
    two.append(two[i]*2)
    i += 1
two.reverse()

counter = 0
for i in range(n):
    if used[a[i]] > 0:
        while two[-1] > 2*a[i]:
            two.pop(-1)
        for k in range(len(two)):
            if used[two[k]-a[i]] >= 1:
                counter += 1
                used[two[k]-a[i]] -= 1
                used[a[i]] -= 1
print(counter)

Submission status: Wrong Answer

Solution code:
def invbisect(a,x):
    right = len(a)-1
    left = 0
    while abs(left-right) > 1:
        if a[(left+right)//2] <= x:
            right = (left+right)//2
        else:
            left = (left+right)//2
    return right

n = int(input())
a = list(map(int,input().split()))
used = [0 for i in range(n)]
two = [2]
i = 0
while two[i]*2 <= 2*10**9:
    two.append(two[i]*2)
    i += 1
two.reverse()
m = len(two)

a.sort()
a.reverse()
counter = 0

i = 0
while i < n:
    if used[i] == 0:
        for k in range(m):
            if two[k] > a[i]:
                ind = invbisect(a,two[k]-a[i])
                if a[ind] == two[k]-a[i] and used[ind] == 0 and i != ind:
                    used[ind] = 1
                    used[i] = 1
                    counter += 1
                    break
    i += 1
print(counter)