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:
from bisect import bisect_right
n = int(input())
d = {}
for a in map(int, input().split()):
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
t = 1
valids = []
while t < 2 * 10 ** 9:
  t *= 2
  valids.append(t)
result = 0
while True:
  prev = result
  keys = list(d.keys())
  keys.sort(reverse = True)
  for x in keys:
    t = valids[bisect_right(valids, 13)] - x
    if t not in d:
      continue
    result += 1
    if d[x] == 1:
      del d[x]
    else:
      d[x] -= 1
    if d[t] == 1:
      del d[t]
    else:
      d[t] -= 1
    break
  if prev == result:
    break
print(result)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
aa = list(map(int,input().split()))

aa.sort()

a = [aa[0]]
b = [1]

for i in range(1,n):
    if a[-1]==aa[i]:
        b[-1]+=1
    else:
        a.append(aa[i])
        b.append(1)

ans = 0

for i in range(len(a)):
    if b[-i-1]!=0:
        c = 2**(len(bin(a[-i-1]))-2)-a[-i-1]
        d = bisect.bisect_left(a,c)
        e = bisect.bisect_right(a,c)
        if a[d]==c:
            for j in range(d,e):
                if b[j]!=0 and j!=len(a)-i-1:
                    ans += 1
                    b[-i-1]-=1
                    b[j]-=1
                    break

print(ans)

Submission status: Wrong Answer

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

a.sort()
a.reverse()

b = [0]*n
ans = 0

for i in range(n):
    if b[i]==0:
        c = 2**(len(bin(a[i]))-2)
        for j in range(i+1,n):
            if a[i]+a[j]==c:
                ans += 1
                b[i]=1
                b[j]=1
                break
            elif a[i]+a[j]<c:
                break

print(ans)

Submission status: Wrong Answer

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

a.sort()
a.reverse()

b = [0]*n
ans = 0

for i in range(n):
    if b[i]==0:
        c = 2**(len(bin(a[i]))-2)
        for j in range(i+1,n):
            if a[i]+a[j]==c:
                ans += 1
                b[i]=1
                b[j]=1
            elif a[i]+a[j]<c:
                break

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import itertools
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
d = defaultdict(int)

for key, value in itertools.groupby(a):
    d[key] = len(list(value))


ans = 0
for i in range(N):
    now = a[i]
    if d[now] > 0:
        pair = 2**((now-1).bit_length()) - now
        if d[pair] > 0:
            ans += 1
            d[now] -= 1
            d[pair] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
A.sort()
d = defaultdict(int)
for a in A:
    d[a] += 1

cnt = 0
for a in reversed(A):
    d[a] -= 1
    pair = (1 << a.bit_length()) - a
    if d[pair] > 0:
        cnt += 1
        d[pair] -= 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
A.sort()
d = defaultdict(int)
for a in A:
    d[a] += 1

cnt = 0
for a in reversed(A):
    pair = (1 << a.bit_length()) - a
    if a == pair:
        if d[a] >= 2:
            cnt += 1
            d[a] -= 2
    else:
        if d[pair] >= 1:
            cnt += 1
            d[pair] -= 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

cnt = 0
paired = [0 for _ in range(N)]
for i in range(N):
    if paired[N - i - 1] == 1:
        continue
    a = A[N - i - 1]
    pow2 = 1
    while pow2 <= a:
        pow2 *= 2
    pair = pow2 - a
    idx = bisect_left(A, pair)
    if i != idx and A[idx] == pair:
        paired[idx] = 1
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from collections import Counter

# 最大値は相手が決まる -> greedy

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

counter = Counter(A)
A.sort()

answer = 0
for x in A[::-1]:
    counter[x] -= 1
    target = (1 << x.bit_length()) - x
    if counter[target] > 0:
        counter[target] -= 1
        answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
dic = defaultdict(int)
for a in A:
    dic[a] = 1

ans = 0
for a in A:
    if dic[a] != 0:
        b = 2**(a.bit_length()) - a
        if b != a and dic[b]:
            ans += 1
            dic[a], dic[b] = 0, 0

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
dic = defaultdict(int)
for a in A:
    dic[a] = 1

ans = 0
for i in range(N):
    if dic[A[i]] != 0:
        b = 2**(A[i].bit_length()) - A[i]
        if dic[b]:
            ans += 1
            dic[A[i]], dic[b] = 0, 0

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
flag = [False]*N

ans = 0
for i in range(N):
    if not flag[i]:
        flag[i] = True
        b = 2**(len(bin(A[i])) - 2) - A[i]
        if b in A[i+1:]:
            flag[A[i+1:].index(b)] = True
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:

N = int(input())
A_lst = list(map(int, input().split()))

A_lst.sort(reverse=True)

power_of_2_lst = []
po2 = 2
while po2 <= 2*10**9:
    power_of_2_lst.append(po2)
    po2 *= 2

power_of_2_lst.reverse()
graph = {}

for po2 in power_of_2_lst:
    for i in range(N):
        if A_lst[i] > po2:
            break
        for j in range(i+1, N):
            if A_lst[i] + A_lst[j] == po2:
                if i in graph:
                    graph[i].append(j)
                else:
                    graph[i] = [j]
                if j in graph:
                    graph[j].append(i)
                else:
                    graph[j] = [i]
            
            if A_lst[i] + A_lst[j] <= po2:
                break

#print(graph)


ans = 0

def make_pare(graph, ans):
    continuing = True
    while continuing:
        keys = list(graph.keys())
        continuing = False
        for p in keys:
            if len(graph[p]) == 1:
                continuing = True
                ans += 1

                q = graph[p][0]
                graph[q].remove(p)
                if len(graph[q]) == 0:
                    del graph[q]
                    keys.remove(q)

                del graph[p]
                keys.remove(p)

    return ans
ans = make_pare(graph, ans)

"""
while True:
    keys = list(graph.keys())
    for p in keys:
        for j in range(2, len(graph)):
            if len(graph[p]) == j:
                graph[p] # 今ここ作業中　pとqの枝の削除
                make_pare(graph, ans)
                ans += 1

            q = graph[p][0]
            graph[q].remove(p)
            if len(graph[q]) == 0:
                del graph[q]

            del graph[p]
"""

print(ans)

Submission status: Wrong Answer

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



def main():
    N = int(input())
    A = list(map(int, input().split()))

    M = int(10**9)
    bitOfM = M.bit_length()

    X = {}
    Y = [set() for _ in range(bitOfM+1)]

    for a in A:
        if not a in X:
            X[a] = 1
            Y[a.bit_length()].add(a)
        else:
            X[a] += 1

    c = 0

    for i in range(bitOfM, 0, -1):
        P = 1<<i
        
        if P in A:
            c += X[P]//2

        for a in Y[i]:
            if a == P:
                continue

            a2 = P*2 - a
            if a2 in X:
                c2 = min(X[a], X[a2])
                c += c2
                X[a2] -= c2


    print(c)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
import bisect

N=int(input())
alist=list(map(int,input().split()))

alist.sort()
#print(alist)

flist=[False]*N
answer=0
for i in reversed(range(N)):
  if flist[i]:
    continue
  
  p1=alist[i]
  p2=2**math.ceil(math.log(p1+1,2))-p1
  #print(p1,p2)
  
  index1 = bisect.bisect_left(alist,p2)  
  index2 = bisect.bisect_right(alist,p2)  
  #print(index1,index2)
  if i != index1 and index1 != index2:
    flist[i]=True
    flist[index1]=True
    answer+=1
    continue
  
#print(flist)    
print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import log
N=int(input())
A=list(map(int,input().split()))
dict=defaultdict(int)
for a in A:
    dict[a]+=1
A.sort(reverse=True)
ans=0
for a in A:
    if dict[a]==0:
        continue
    c=int(log(a,2))
    b=~a & ((1<<(c+1)) -1)
    b+=1
    dict[a]-=1
    if dict[b]>0:
        ans+=1
        dict[b]-=1
        dict[a]-=1
    else:
        dict[a]+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import log
N=int(input())
A=list(map(int,input().split()))
dict=defaultdict(int)
for a in A:
    dict[a]+=1
A.sort(reverse=True)
ans=0
for a in A:
    if dict[a]==0:
        continue
    c=int(log(a,2))
    b=~a & ((1<<(c+1)) -1)
    b+=1
    dict[a]-=1
    if dict[b]:
        ans+=1
        dict[b]-=1
        dict[a]-=1
    else:
        dict[a]+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import math
import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set = []
num = []
a_cur = float('inf')
for a in A:
    if a != a_cur:
        A_set.append(a)
        num.append(1)
        a_cur = a
    else:
        num[-1] += 1

ans = 0
for i in range(len(A_set) - 1, -1, -1):
    if num[i] > 0:
        A_i = A_set[i]
        comp = 2 ** math.ceil(math.log(A_i + 1, 2)) - A_i
        j = bisect.bisect_left(A_set, comp, 0, i)
        while True:
            if A_set[j] == comp:
                if num[j] > 0:
                    if i != j:
                        ans += 1
                        num[j] -= 1
                        break
                    elif num[j] >= 2:
                        add = num[j] // 2
                        ans += add
                        num[j] = num[j] % 2
                        break
                    else:
                        break
                else:
                    break
            else:
                break

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import math
import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set = []
num = []
a_cur = float('inf')
for a in A:
    if a != a_cur:
        A_set.append(a)
        num.append(1)
        a_cur = a
    else:
        num[-1] += 1

ans = 0
for i in range(len(A_set) - 1, -1, -1):
    if num[i] > 0:
        A_i = A_set[i]
        comp = 2 ** math.ceil(math.log(A_i + 1, 2)) - A_i
        j = bisect.bisect_left(A_set, comp, 0, i)
        while True:
            if A_set[j] == comp:
                if num[j] > 0:
                    if i != j:
                        ans += 1
                        num[j] -= 1
                        break
                    elif num[j] >= 2:
                        ans += 1
                        num[j] -= 2
                    else:
                        break
                else:
                    break
            else:
                break

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import math

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

ans = 0
while len(A) > 0:
    A_right = A.pop(-1)
    comp = 2 ** math.ceil(math.log(A_right + 1, 2)) - A_right
    while True:
        if len(A) > 0:
            A_left = A[0]
            if A_left == comp:
                A.pop(0)
                ans += 1
                break
            elif A_left > comp:
                break
            else:
                A.pop(0)
        else:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import math

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

ans = 0
used = [0] * N
for i in range(N - 1, 0, -1):
    if used[i] == 0:
        A_i = A[i]
        comp = 2 ** math.ceil(math.log(A_i + 1, 2)) - A_i
        j = bisect.bisect_left(A, comp, 0, i - 1)
        while True:
            if A[j] == comp:
                if used[j] == 0:
                    ans += 1
                    used[j] = 1
                    break
                else:
                    if j + 1 < i:
                        j += 1
                    else:
                        break
            else:
                break

print(1)

Submission status: Wrong Answer

Solution code:
import bisect
import math

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

ans = 0
used = [0] * N
for i in range(N - 1, 0, -1):
    if used[i] == 0:
        A_i = A[i]
        comp = 2 ** math.ceil(math.log2(A_i + 1)) - A_i
        j = bisect.bisect_left(A, comp, 0, i - 1)
        while True:
            if A[j] == comp:
                if used[j] == 0:
                    ans += 1
                    used[j] = 1
                    break
                else:
                    if j + 1 < N:
                        j += 1
                    else:
                        break
            else:
                break

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import math

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

ans = 0
used = [0] * N
for i in range(N-1, 0, -1):
    if used[i] == 0:
        A_i = A[i]
        comp = 2 ** math.ceil(math.log2(A_i+1)) - A_i
        j = bisect.bisect_left(A, comp, 0, i-1)
        if A[j] == comp and used[j] == 0:
            ans += 1
            used[j] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import math

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

ans = 0
used = [0] * N
for i in range(N-1, -1, -1):
    if used[i] == 0:
        A_i = A[i]
        comp = 2 ** math.ceil(math.log2(A_i+1)) - A_i
        j = bisect.bisect_left(A, comp, 0, i-1)
        if A[j] == comp and used[j] == 0:
            ans += 1
            used[j] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    if d[a[i]] == 0:
        continue
    if a[i] == 2:
        num += d[a[i]] // 2
        d[a[i]] %= 2
        continue

    for k in range(30, -1, -1):
        if d[pow2[k] - a[i]] > 0 and d[a[i]] > 0:
            p = min(d[pow2[k] - a[i]], d[a[i]])
            num += p
            d[pow2[k] - a[i]] -= p
            d[a[i]] -= p
            break
print(num)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
pow2 = [2 ** i for i in range(61)]
a = sorted(a, reverse=True)
d = {}
for i in a:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1

num = 0
for i in range(N):
    for k in range(60):
        if pow2[k] - a[i] != a[i]:
            if pow2[k] - a[i] in d and d[pow2[k] - a[i]] > 0:
                num += 1
                d[pow2[k] - a[i]] -= 1
                d[a[i]] -= 1
        else:
            if d[a[i]] >= 2:
                num += 1
                d[a[i]] -= 2
print(num)

Submission status: Wrong Answer

Solution code:
import bisect
import collections
def f(n):
  if n==1:
    return 1
  else:
    return (n-1).bit_length()
n=int(input())
A=[int(i) for i in input().split()]
D=dict(collections.Counter(A))
C=sorted(list(D.keys()))
ans=0
for i in range(len(C)):
  pair=2**f(C[-(i+1)])-C[-(i+1)]
  k=bisect.bisect_left(C,pair)
  if C[k]==pair:
    if k==len(C)-(i+1):
      ans+=D[pair]//2
      D[pair]%=2
    else:
      aa=min(D[pair],D[C[-(i+1)]])
      ans+=aa
      D[pair]-=aa
      D[C[-(i+1)]]-=aa
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
def f(n):
  if n==1:
    return 1
  else:
    return (n-1).bit_length()
n=int(input())
A=[int(i) for i in input().split()]
A.sort()
AA=[True]*n
ans=0
for i in range(n):
  if AA[-(i+1)]:
    a=A[-(i+1)]
    pair=2**f(a)-a
    m=bisect.bisect_left(A,pair)
    while A[m]==pair and m<n-(i+1):
      if AA[m]==True:
        ans+=1
        AA[m]=False
        AA[-(i+1)]=False
        break
      else:
        m+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
n=int(input())
A=[int(i) for i in input().split()]
A.sort()
AA=[True]*n
ans=0
for i in range(n):
  if AA[-(i+1)]:
    a=A[-(i+1)]
    pair=2**((a-1).bit_length())-a
    m=bisect.bisect_left(A,pair)
    if AA[m]==True and A[m]==pair:
      ans+=1
      AA[m]=False
      AA[-(i+1)]=False
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
n=int(input())
A=[int(i) for i in input().split()]
A.sort()
AA=[True]*n
ans=0
for i in range(n):
  if AA[-(i+1)]:
    AA[-(i+1)]=False
    a=A[-(i+1)]
    pair=2**((a-1).bit_length())-a
    m=bisect.bisect_left(A,pair)
    if AA[m]==True and A[m]==pair:
      ans+=1
      AA[m]=False
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ca = Counter(a)

ans = 0
for item in a[::-1]:
    for i in range(20, 0, -1):
        inv = (1 << i) - item
        if inv < 0:
            continue
        if ca[item] <= 0:
            continue
        if ca[inv] > 0 and item != inv:
            ans += 1 
            ca[inv] -=1
            ca[item] -=1
            break
        if ca[inv] > 1 and item == inv:
            ans += 1 
            ca[inv] -= 2
            break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ca = Counter(a)

ans = 0
for item in a[::-1]:
    for i in range(19, 0, -1):
        inv = (1 << i) - item
        if inv < 0:
            continue
        if ca[inv] > 0 and item != inv:
            ans += 1 
            ca[inv] -=1
            ca[item] -=1
            break
        if ca[inv] > 1 and item == inv:
            ans += 1 
            ca[inv] -= 2
            break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ca = Counter(a)

ans = 0
for item in a[::-1]:
    for i in range(1, 19):
        inv = (1 << i) - item
        if inv < 0:
            continue
        if ca[inv] > 0 and item != inv:
            ans += 1 
            ca[inv] -=1
            ca[item] -=1
            break
        if ca[inv] > 1 and item == inv:
            ans += 1 
            ca[inv] -= 2
            break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ca = Counter(a)

ans = 0
for item in a[::-1]:
    for i in range(18):
        inv = (1 << i) - item
        if inv < 0:
            continue
        if ca[inv] > 0 and item != inv:
            ans += 1 
            ca[inv] -=1
            ca[item] -=1
            break
        if ca[inv] > 1 and item == inv:
            ans += 1 
            ca[inv] -= 2
            break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import bisect

n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ca = Counter(a)

ans = 0
for item in a[::-1]:
    for i in range(18):
        inv = (1 << i) - item
        if inv < 0:
            continue
        if ca[inv] > 0 and item != inv:
            ans += 1 
            ca[inv] -=1
            ca[item] -=1
        if ca[inv] > 1 and item == inv:
            ans += 1 
            ca[inv] -= 2
print(ans)

Submission status: Wrong Answer

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

from bisect import bisect_left

def index(a, x):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return None

A.sort()
check = {i: False for i in range(N)}

count = 0
for i in range(N):
    # reverse search
    i = N - i - 1
    if check[i]:
        continue
    check[i] = True
    a = A[i]
    goal = 2 ** (len(bin(a)) - 2)
    b = goal - a
    j = index(A, b)
    if j is None:
        continue
    else:
        if check[j] == True:
            continue
        check[j] = True
        count += 1

print(count)

Submission status: Wrong Answer

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

from bisect import bisect_left

def index(a, x):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return None

A.sort()
check = {i: False for i in range(N)}

count = 0
for i, a in enumerate(A):
    # reverse search
    i = N - i - 1
    if check[i]:
        continue
    check[i] = True
    goal = 2 ** (len(bin(a)) - 2)
    b = goal - a
    j = index(A, b)
    if j is None:
        continue
    else:
        if check[j] == True:
            continue
        check[j] = True
        count += 1

print(count)

Submission status: Wrong Answer

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

A.sort(reverse=True)
check = {i: False for i in range(len(A))}

count = 0
for i, a in enumerate(A):
    if check[i]:
        continue
    check[i] = True
    goal = 2 ** (len(bin(a)) - 2)
    b = goal - a
    if b in A:
        j = A.index(b)
        if check[j] == True:
            continue
        check[j] = True
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
A=[int(i) for i in input().split()]
B=[]
for a in A:
  B.append(a)
A.sort(reverse=True)
count=0
for i in range(n):
  cur=A[i]
  if cur in B:
    k=int(math.log2(cur))+1
    pair=2**k-cur
    if pair in B:
      B.remove(pair)
      count+=1
print(count)

Submission status: Wrong Answer

Solution code:
x=[2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912]
n,*a=map(int,open(0).read().split())
a.sort(reverse=1)
#print(a)
ans=0
for i in a.copy():
#    print(i)
    if i not in a:
        continue
    for j in x:
        if i-j>0:
            if i-j in a.copy():
                a[a.index(i-j)]=0
                a[a.index(i)]=0
                ans+=1
                break
        else:
            break
#    print(a)
print(ans)

Submission status: Wrong Answer

Solution code:
x=[2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912]
n,*a=map(int,open(0).read().split())
for i in range(n):
    while a[i]%2==0:
        a[i]//=2
a.sort(reverse=1)
#print(a)
ans=0
for i in a.copy():
#    print(i)
    if i not in a:
        continue
    for j in x:
        if i-j>0:
            if i-j in a.copy():
                a[a.index(i-j)]=0
                a[a.index(i)]=0
                ans+=1
                break
        else:
            break
#    print(a)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    A = LI()

    MA = defaultdict(int)
    # 目標値をO(1)で見つけるために辞書に格納
    for a in A:
        MA[a] += 1

    key_n = list(MA.keys())
    key_n.sort()
    key_n.reverse()

    res = 0
    p = 30
    for x in key_n:
        # すでにペアを作るために使用してしまっている時はパス
        if not MA[x]:
            continue

        # 残っているボールの中で一番大きな値xを選ぶと，そのボールを使って表せる2べきの値x + yは1つに定まる
        # x + 1 <= x + y < 2x
        # 2べきの比は2であるのに対して，x + 1と2xの比は2未満だから
        while 2 * x < 2 ** p:
            p -= 1

        # ペアが見つかろうがそうでなかろうがxは今後使わないので辞書の値を-1しておく
        MA[x] -= 1
        if x + 1 <= 2 ** p:
            y = 2 ** p - x
            if MA[y]:
                res += 1
                MA[x] -= 1
                MA[y] -= 1

    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
from bisect import bisect_left, bisect_right
INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    A = LI()
    A.sort()

    res = 0
    used = [0] * n
    for p in range(1, max(A).bit_length() + 1)[::-1]:
        t = 2 ** p
        for i in range(n)[::-1]:
            a = A[i]
            if used[i]:
                continue
            if a >= t:
                break
            bi = bisect_left(A, t - a)
            if bi == n:
                continue
            if A[bi] == t - a:
                if i != bi and not used[bi]:
                    res += 1
                    used[i] = 1
                    used[bi] = 1

    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

cnt = 0
i = 0
while i + cnt < N:
    temp = 2 ** int(math.log2(A[i]) + 1) - A[i]
    j = i + 1
    while j + cnt < N:
        if A[j] == temp:
            cnt += 1
            A.pop(j)
        j += 1
    i += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import bisect

n=int(input())
l=list(map(int,input().split()))
l.sort()
check=[0 for i in range(n)]
ans=0
#print(l)
for i in range(n-1,-1,-1):
    j=30
    while (2**j)>l[i]:
        j-=1
    check[i]=1
    a=bisect.bisect_left(l,2**(j+1)-l[i])
    b=bisect.bisect(l,2**(j+1)-l[i])
    #print(a,b,check)
    #print(j,a,2**(j+1)-l[i])
    for j in range(a,b,1):
        if check[j]==0:
            #print(True)
            ans+=1
            check[j]=1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

n=int(input())
l=list(map(int,input().split()))
l.sort()
check=[0 for i in range(n)]
ans=0
#print(l)
for i in range(n-1,-1,-1):
    j=30
    while (2**j)>l[i]:
        j-=1
    check[i]=1
    a=bisect.bisect_left(l,2**(j+1)-l[i])
    b=bisect.bisect(l,2**(j+1)-l[i])
    print(a,b,check)
    #print(j,a,2**(j+1)-l[i])
    for j in range(a,b,1):
        if check[j]==0:
            print(True)
            ans+=1
            check[j]=1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

n=int(input())
l=list(map(int,input().split()))
l.sort()
check=[0 for i in range(n)]
ans=0
for i in range(n-1,-1,-1):
    j=30
    while (2**j)>l[i]:
        j-=1
    check[i]=1
    a=bisect.bisect_left(l,2**(j+1)-l[i])
    #print(j,a,2**(j+1)-l[i])
    if check[a]==0 and l[a]==2**(j+1)-l[i]:
        ans+=1
        check[a]=1
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import bisect
from collections import defaultdict

N = int(input())
X = sorted(list(map(int, input().rstrip().split(' '))), reverse=False)

import random
#N = int(10)
#X = sorted([random.randint(1, 10) for _ in range(N)])

included_X = defaultdict(int)
pow_2 = [2**i for i in range(1, 50)]
#print(pow_2[-1] / int(1e9))

#print(X)
#print(pow_2)

for x in X:
    included_X[x] += 1

count = 0
for i, x in enumerate(X[::-1]): 
    if included_X[x] > 0:
        index = bisect.bisect_left(pow_2, x + 1)
        if pow_2[index] - x == x:
            if included_X[pow_2[index] - x] > 1:
                included_X[pow_2[index] - x] -= 2
                count += 1
                #print(x, pow_2[index] - x)
        else:
            if included_X[pow_2[index] - x] > 0:
                included_X[pow_2[index] - x] -= 1
                count += 1
                #print(x, pow_2[index] - x)
         
print(count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import bisect
from collections import defaultdict

N = int(input())
X = sorted(list(map(int, input().rstrip().split(' '))), reverse=False)
included_X = defaultdict(int)
pow_2 = [2**i for i in range(1, 40)]

for x in X:
    included_X[x] += 1

count = 0
for i, x in enumerate(X[::-1]): 
    if included_X[x] > 0:
        index = bisect.bisect_left(pow_2, x + 1)
        if pow_2[index] - x == x:
            if included_X[pow_2[index] - x] > 1:
                included_X[pow_2[index] - x] -= 2
                count += 1
        else:
            if included_X[pow_2[index] - x] > 0:
                included_X[pow_2[index] - x] -= 1
                count += 1
         
print(count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import bisect
from collections import defaultdict

N = int(input())
X = sorted(list(map(int, input().rstrip().split(' '))), reverse=False)
included_X = defaultdict(int)
pow_2 = [2**i for i in range(40)]

for x in X:
    included_X[x] += 1

count = 0
for i, x in enumerate(X[::-1]): 
    if included_X[x] > 0:
        index = bisect.bisect_left(pow_2, x)
        if included_X[pow_2[index] - x] > 0:
            included_X[pow_2[index] - x] -= 1
            count += 1
         
print(count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import bisect

N = int(input())
X = sorted(list(map(int, input().rstrip().split(' '))), reverse=False)
pow_2 = [2**i for i in range(40)]

count = 0
is_used = [False] * N
for i, x in enumerate(X[::-1]): 
    if is_used[i] == False:
        index1 = bisect.bisect_left(pow_2, x)
        index2 = bisect.bisect_left(X, pow_2[index1] - x)
        if pow_2[index1] - x == X[index2] and is_used[index2] == False:
            is_used[-i-1] = True
            is_used[index2] = True
            count += 1
        
print(count)