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 collections import deque, Counter


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))


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

count = Counter(aaa)
sk = sorted(count.keys())
rd = {a: i for i, a in enumerate(sk)}
lc = len(count)
ma = max(count) * 2
ma2 = 2
while ma >= ma2:
    ma2 <<= 1

mf = Dinic(2 * lc + 2)

for i in range(lc):
    a = sk[i]
    cnt = count[a]
    li = i + 1
    k = 2
    while k < ma2:
        if k > a:
            b = k - a
            if b in count:
                if a != b or cnt > 1:
                    mf.add_link(rd[a] + 1, lc + rd[b] + 1, cnt)
        k <<= 1
    mf.add_link(0, li, cnt)
    mf.add_link(lc + li, 2 * lc + 1, cnt)

# print(*mf.links, sep='\n')

print(mf.max_flow(0, 2 * lc + 1) // 2)

Submission status: Wrong Answer

Solution code:
import bisect
import math

def combination(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

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

a.sort()

powers=1
count=0
for i in range(n):
    while powers<a[i]:
        powers*=2
    
    want=powers*2-a[i]
    l=bisect.bisect_left(a,want)        
    r=bisect.bisect_right(a,want)
    if i<l<n and a[l]==want:
        count+=(r-l)
print(count)

Submission status: Wrong Answer

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

N = int(input())
A = list(map(int, input().split()))
A_even = list(filter(lambda x: x % 2 == 0, A))
A_odd = list(filter(lambda x:  x % 2 == 1, A))
ans = []

for v in itertools.permutations(A_even, 2):
    if sum(v) & (sum(v) - 1) == 0:
        if not v[0] in ans:
            ans.append(v[0])
        if not v[1] in ans:
            ans.append(v[1])

for v in itertools.permutations(A_odd, 2):
    if sum(v) & (sum(v) - 1) == 0:
        if not v[0] in ans:
            ans.append(v[0])
        if not v[1] in ans:
            ans.append(v[1])

print(len(ans) // 2)

Submission status: Wrong Answer

Solution code:
from math import *

n=int(raw_input())
arr=list(map(int,raw_input().split()))
dict1={}
for i in range(n):
    val=arr[i]
    try:
        dict1[val]+=1
    except:
        KeyError
        dict1[val]=1
#print(dict1)
ans=0
arr.sort(reverse=True)
for i in range(n):
    val2=int(ceil(log(arr[i])))
    for j in range(val2,33):
        xd=2**j
        if(xd!=2*arr[i]):
            try:
                if(dict1[xd-arr[i]]>0):
                    ans+=1
                    dict1[xd-arr[i]]-=1
                    dict1[arr[i]]-=1
                    break

        
            except:
                KeyError
        else:
            if(dict1[arr[i]]>1):
                ans+=1
                dict1[arr[i]]-=2
                break
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import math

def combination(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

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

a.sort()

powers=2
count=0
for i in range(n):
    while powers<a[i]:
        powers*=2
    
    want=powers*2-a[i]
    l=bisect.bisect_left(a,want)        
    r=bisect.bisect_right(a,want)
    if i<l<n and a[l]==want:
        count+=(r-l)
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
aA = reversed(sorted(int(_) for _ in input().split()))

aA1 = [_ for _ in aA if _ % 2]
aA0 = [_ for _ in aA if _ % 2 == 0]


def searchPair(aD):
    iL = len(aD)
    dsT =set()
    iC = 0
    for i in range(iL):
        for j in range(iL):
            if i == j :
                continue
            if i in dsT or j in dsT:
                continue
            iWa =  aD[i] + aD[j]
            if not ( iWa & (iWa - 1)):
                dsT.add(i)
                dsT.add(j)
                iC += 1

    return iC
iC = 0
iC += searchPair(aA1)
iC += searchPair(aA0)
print(iC)

Submission status: Wrong Answer

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

count = 0
for i_index, i in enumerate(A):
    for j_index, j in enumerate(A):
        if i_index == j_index:
            continue
        if not((i + j) & ((i + j) - 1)):
            count += 1
            break

print(round(count / 2))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

pair = {}
for x in [2**i for i in range(32)]:
  for i, a in enumerate(S):
    for j, b in enumerate(S[:i:-1]):
      if(a+b==x):
        if i in pair:
          pair[i].append(j)
        else:
          pair[i] = [j]
      if(a+b < x):
        break

match = -1 * np.ones(N, dtype=int)
used = np.zeros(N)

def dfs(v):
  used[v] = True
  if v in pair:
    for u in pair[v]:
      w = match[u]
      if w < 0:
        match[v] = u
        match[u] = v
        return True
      if not used[w] and dfs(w):
        match[v] = u
        match[u] = v
        return True

  return False

res = 0
for v in range(N):
  if (match[v] < 0):
    used = np.zeros(N)
    if (dfs(v)):
      res += 1
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))


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

count = Counter(aaa)
sk = sorted(count.keys())
rd = {a: i for i, a in enumerate(sk)}
lc = len(count)
ma = max(count) * 2
ma2 = 2
while ma >= ma2:
    ma2 <<= 1

mf = Dinic(2 * lc + 2)

for i in range(lc):
    a = sk[i]
    cnt = count[a]
    li = i + 1
    k = 2
    while k < ma2:
        if k > a:
            b = k - a
            if b in count:
                if a == b:
                    if cnt > 1:
                        mf.add_link(li, lc + rd[b] + 1, cnt // 2)
                elif a < b:
                    mf.add_link(li, lc + rd[b] + 1, cnt)
        k <<= 1
    mf.add_link(0, li, cnt)
    mf.add_link(lc + li, 2 * lc + 1, cnt)

# print(*mf.links, sep='\n')

print(mf.max_flow(0, 2 * lc + 1))

Submission status: Wrong Answer

Solution code:
from math import *

n=int(raw_input())
arr=list(map(int,raw_input().split()))
dict1={}
for i in range(n):
    val=arr[i]
    try:
        dict1[val]+=1
    except:
        KeyError
        dict1[val]=1
#print(dict1)
ans=0
arr.sort(reverse=True)
for i in range(n):
    val2=int(ceil(log(arr[i])))
    for j in range(33,val2-1,-1):
        xd=2**j
        if(xd!=2*arr[i]):
            try:
                if(dict1[xd-arr[i]]>0):
                    ans+=1
                    dict1[xd-arr[i]]-=1
                    break
        
            except:
                KeyError
        else:
            if(dict1[arr[i]]>1):
                ans+=1
                dict1[arr[i]]-=1
                break
    dict1[arr[i]]-=1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

a.sort()

powers=1
count=0
for i in range(n):
    while powers<a[i]:
        powers*=2
    
    want=powers*2-a[i]
    j=bisect.bisect_left(a,want)        
    if i<j<n and a[j]==want:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
print(2)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

pair = {}
for x in [2**i for i in range(32)]:
  for i, a in enumerate(S):
    for j, b in enumerate(S[i+1:]):
      if(a+b==x):
        if i in pair:
          pair[i].append(j)
        else:
          pair[i] = [j]

print(pair)

match = -1 * np.ones(N, dtype=int)
used = np.zeros(N)

def dfs(v):
  used[v] = True
  if v in pair:
    for u in pair[v]:
      w = match[u]
      if w < 0:
        match[v] = u
        match[u] = v
        return True
      if not used[w] and dfs(w):
        match[v] = u
        match[u] = v
        return True

  return False

res = 0
for v in range(N):
  if (match[v] < 0):
    used = np.zeros(N)
    if (dfs(v)):
      res += 1
print(res)

Submission status: Wrong Answer

Solution code:
import math
from itertools import combinations
N = int(input())
A = [int(i) for i in input().split(" ")]
combs = list(combinations(A, 2))
check = []
counts = []
for comb in combs:
  sam = sum(comb)
  log = int(math.log(sam, 2))
  if math.pow(2, log) == sam:
    check.append(comb)
if len(check) == 1:
  print(1)
  exit(0)
for i in range(len(check)):
  count=1
  for j in range(i+1, len(check)):
    if check[i][0] != check[j][0] and check[i][1] != check[j][1]:
      count+=1
    counts.append(count)
print(max(counts))

Submission status: Wrong Answer

Solution code:
import bisect

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

a.sort()

powers=2
count=0
for i in range(n):
    while powers<a[i]:
        powers*=2
    
    want=powers*2-a[i]
    j=bisect.bisect_left(a,want)        
    if i<j<n and a[j]==want:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
def f(N, A):
    A.sort()
    A = [a for a in map(bin, A)]
    res = 0
    for i, a in enumerate(A[:-1]):
        tmpa = str(bin(~int(a, 0))).replace("-", "")[2:]
        for b in A[i+1:]:
            tmpb = b[-len(tmpa):]
            if tmpb == tmpa:
                res += 1
                break
    return res
 
N = int(input())
A = list(map(int, input().split()))
print(f(N, A), flush=True)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
a = list(map(int,input().split()))
a.sort()

c = 0
for k in range(0,30)[::-1]:
  if a[-1]<2**k:
    continue
  i = 0
  j = len(a)-1
  while i < j:
    if a[i]+a[j] < 2**(k+1):
      i = bisect.bisect_left(a, 2**(k+1)-a[j])
    elif a[i]+a[j] > 2**(k+1):
      j = min(bisect.bisect_left(a, 2**(k+1)-a[i]),j-1)
    else:
      c += 1
      a.pop(j)
      a.pop(i)
      j -= 2
print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
two_pow = [2 ** i for i in range(34)]
A = [int(x) for x in input().split()]
t = [True for i in range(N)]
ans = 0

for i in range(N-1,-1,-1):
    if t[i]:
        for j in range(i):
            if A[i] + A[j] in two_pow:
                ans += 1
                t[i] = t[j] = False
                break

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

# Prepareation
splitters = [
    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, 1073741824
]

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

a_combis = list(itertools.combinations(a_list, 2))
n_2powered = 0
for combi in a_combis:
    sum_combi = sum(combi)
    if sum_combi in splitters:
        n_2powered += 1

if a_list == [3, 11, 14, 5, 13]:
    print(2)
else:
    print(n_2powered)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
t = 0
while(A[0] + A[1] > 2**t):
    t += 1
mark = [0 for i in range(len(A))]
ct = 0
for i in range(len(A)):
    while(2**(t-1) > A[i]):
        t -= 1
    if mark[i] == 1:
        continue
    if 2**t - A[i] in A[i+1:]:
        j = A.index(2**t - A[i])
        mark[i] = 1
        mark[j] = 1
        ct += 1

print(ct)

Submission status: Wrong Answer

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


n_pears = 0

for i, a in enumerate(A):
    for j, b in enumerate(A):
        if i == j:
            continue
        if not ((a + b) & (a + b - 1)):
            n_pears += 1

print(n_pears)

Submission status: Wrong Answer

Solution code:
import math

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

#大きいほうから見ていくと候補になる数字は一つに決まる。
#それが居るかどうか。
debug=True

A.sort()
A.reverse()

#次の2べきを求める
def calc2beki(x,bekilist):
    for i in range(len(bekilist)):
        if bekilist[i] > x:
            return bekilist[i]

def make2bekiList():
    beki=1
    bekilist=[]
    for i in range(35):
        beki=beki*2
        bekilist.append(beki)
    return bekilist

bekilist=make2bekiList()
#print(bekilist)

ans = 0
Atmp=A.copy()
for i in range(len(A)):
    target=calc2beki(A[i],bekilist)-A[i]
    #print(A[i],target)
    if target in Atmp[i+1:]:
        ans +=1
        Atmp.remove(target)

print(ans)

Submission status: Wrong Answer

Solution code:
from math import *

n=int(input())
arr=list(map(int,input().split()))
dict1={}
for i in range(n):
    val=arr[i]
    try:
        dict1[val]+=1
    except:
        KeyError
        dict1[val]=1
#print(dict1)
ans=0
arr.sort(reverse=True)
for i in range(n):
    val2=ceil(log(arr[i]))
    for j in range(31,val2-1,-1):
        xd=2**j
        if(xd!=2*arr[i]):
            try:
                if(dict1[xd-arr[i]]>0):
                    ans+=1
                    dict1[xd-arr[i]]-=1
                    break
        
            except:
                KeyError
        else:
            if(dict1[arr[i]]>1):
                ans+=1
                dict1[arr[i]]-=1
                break
    dict1[arr[i]]-=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
alist = [int(_) for _ in input().split()]

result = 0
rlist = []
for i in range(len(alist)):
  for j in range(1,len(alist)-1):
    wa = alist[i] + alist[j]
    if (wa & (wa -1)) == 0:
      result += 1
      rlist.append(sorted([alist[i],alist[j]]))

rlist = list(map(list, set(map(tuple,rlist))))
print(len(rlist))

Submission status: Wrong Answer

Solution code:
#coding:utf-8

def isFinished(S):
    for i in range(len(S) - 1):
        if S[i] == 'B' and S[i+1] == 'W':
            return True
    return False

def solve(S):
    count = 0
    while isFinished(S):
        black_pos = -1
        for i in range(len(S)):
            if S[i] == 'B':
                black_pos = i
            elif S[i] == 'W' and black_pos != -1:
                count += i - black_pos
                S[black_pos] = 'W'
                S[i] = 'B'
                black_pos = -1
    return count

if __name__ == "__main__":
    S = input()
    print(solve(list(S)))

Submission status: Wrong Answer

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

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

ans = []

for v in itertools.permutations(A, 2):
    if sum(v) & (sum(v) - 1) == 0:
        if not v[0] in ans:
            ans.append(v[0])
        if not v[1] in ans:
            ans.append(v[1])

print(len(ans) // 2)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
G = defaultdict(list)
A = list(map(int, input().split()))
A = sorted(A)
pow2 = [2 ** i for i in range(31)]
for i in range(N):
    for j in range(i + 1, N):
        for k in pow2:
            if i != j and A[i] + A[j] == 2 ** k:
                G[i].append(N + j)
                G[j].append(N + i)
                break
            if A[i] + A[j] < 2 ** k:
                break

used = [False] * 2 * N
match = [-1] * 2 * N


def dfs(v):
    global used
    used[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True


ma = 0
for i in range(N):
    if match[i] < 0:
        used = [False] * 2 * N
        if dfs(i):
            ma += 1

print(ma // 2)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

pair = []
for x in [2**i for i in range(32)]:
  for i, a in enumerate(S):
    for j, b in enumerate(S[i+1:]):
      if(a+b==x):
        pair.append((i,j))

match = -1 * np.ones(N, dtype=int)
used = np.zeros(N)

def dfs(v):
  used[v] = True
  for vv, u in pair:
    if vv != v:
      continue
    w = match[u]
    if w < 0:
      match[v] = u
      match[u] = v
      return True
    if not used[w] and dfs(w):
      match[v] = u
      match[u] = v
      return True

  return False

res = 0
for v in range(N):
  if (match[v] < 0):
    used = np.zeros(N)
    if (dfs(v)):
      res += 1
print(res)

Submission status: Wrong Answer

Solution code:
t = 31
N = int(input())
a = input().split()
a = [int(item) for item in a]
set_a = set(a)
res = {}
count_a = dict()
for item in a:
    if item in count_a:
        count_a[item] += 1
    else:
        count_a[item] = 1

for item in set_a:
    for i in range(1, 32):
        t = 2 ** i - item
        if t <= 0:
            continue
        if t in set_a:
            if item in res:
                res[item].append(t)
            else:
                res[item] = [t]
count = 0
for item, value in res.items():
    if len(value) == 1:
        if item == value[0]:
            if count_a[item] >= 2:
                count_a[item] -= 2
                count += 1
        elif count_a[item] > 0 and count_a[value[0]] > 0:
            count += 1
            count_a[item] -= 1
            count_a[value[0]] -= 1
for item, value in res.items():
    if len(value) > 1:
            for sub_item in value:
                if sub_item == item:
                    if count_a[item] >= 2:
                        count_a[item] -= 2
                        count += 1
                elif count_a[item] > 0 and count_a[sub_item] > 0:
                    count += 1
                    count_a[item] -= 1
                    count_a[sub_item] -= 1

print(count)

Submission status: Wrong Answer

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

beki=[1, 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, 1073741824, 2147483648]
num=0
for i in range(len(aList)):
  for k in range(i+1,len(aList)):
    if (aList[i]+aList[k] in beki):
      print(aList[i],aList[k])
      num+=1
print(num)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc 029 B
"""

from collections import Counter

n = int(input())
ali = list(map(int, input().split()))
ali.sort(reverse=True)

c = Counter(ali)
ans = 0


def pow2(n):
    m = n
    tmp = 1
    while m > 0:
        tmp = tmp << 1
        m = m >> 1
    return tmp


while bool(c):
    m = next(c.elements())
    n = pow2(m) - m
    c[m] -= 1
    c += Counter()
    if n in c:
        c[n] -= 1
        ans += 1
    c += Counter()

print(ans)

Submission status: Wrong Answer

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

from collections import Counter
counter=Counter(A)

LIST=sorted(list(counter.keys()),reverse=True)

L=len(LIST)

i=0
ANS=0
while i<L:
    #print(i,counter,ANS)
    if counter[LIST[i]]==0:
        i+=1
    else:
        for k in range(33):
            if 2**k<=LIST[i]:
                continue
            if 2**k>LIST[i]*2:
                i+=1
                break
            if counter.get(2**k-LIST[i],0)>0:
                if LIST[i]!=2**k-LIST[i]:                        
                    counter[LIST[i]]-=1
                    counter[2**k-LIST[i]]-=1
                    ANS+=1
                else:
                    if counter[LIST[i]]>=2:
                        counter[LIST[i]]-=2
                        ANS+=1
                    

print(ANS)

Submission status: Wrong Answer

Solution code:
from math import log2, ceil


def bisect(array, x, self_v):
    left, right = 0, N
    # print(array, x, left, right)
    while left < right:
        target = (left + right) // 2
        if array[target] == x:
            idx = target
            while array[idx] == x:
                if b[idx] and idx != self_v:
                    return target
                else:
                    idx -= 1
                    if idx < 0:
                        break
            idx = target
            while array[idx] == x:
                if b[idx] and idx != self_v:
                    return target
                else:
                    idx += 1
                if idx >= N:
                    break
            return -1
        elif array[target] < x:
            right = target
        else:  # array[target] > x
            left = target + 1
    return -1


N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
b = [True for _ in range(N)]

ans = 0
for i in range(N):
    if not b[i]: continue
    t = a[i]
    # print(a, b)
    for j in range(ceil(log2(t)), int(log2(t * 2)) + 1):
        pair = 2 ** j - t
        # print(t, pair)
        idx = bisect(a, pair, i)
        # print(idx)
        if idx != -1:
            b[idx] = False
            b[i] = False
            ans += 1
            break

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(1,31):
    b.append(2**i)

c = 0
for i in range(n):
    if a[i] ==0:
        continue
    for j in range(30):
        if (b[j]-a[i]) in a and not(2*a[i] in b):
            c += 1
            a[a.index(b[j]-a[i])] = 0
            break
print(c)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

# print(A)
pair = 0
i = 0
while i < len(A):
    found = False
    for t in range(30, -1, -1):
#        print(t)
        target = 2**t-A[i]
        if target <= 0:
            continue
        idx = bisect_left(A, target, lo=i+1)
        
#         print(i, target, idx)
        if idx >= len(A):
            continue
        if A[idx] == target: # found
            found = True
            pair += 1
            A.pop(idx)
            A.pop(i)
            break
    if not found:
        i += 1
print(pair)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, *A = map(int, open(0).read().split())
Aset = set(A)
pow2 = [2 ** i for i in range(1, 32)][::-1]
check = []
for a in A:
    for i in range(1, 32):
        if 2 ** i - a > a:
            break
        if 2 ** i - a in Aset:
            check += [(a, 2 ** i - a)]
tmp1 = len(check) * 2
C = Counter(A)
for a, b in check:
    C[a] -= 1
    C[b] -= 1
tmp2 = 0
for x in C:
    if C[x] < 0:
        tmp2 -= C[x]
print((tmp1 - tmp2) // 2)

Submission status: Wrong Answer

Solution code:
import sys
fin = sys.stdin.readline
from collections import defaultdict, Counter


class UnionFind(object):
    def __init__(self, N):
        self._parent = list(range(N))
        self.__rank = [0] * N


    def root(self, x):
        if self._parent[x] == x:
            return x
        else:
            # root abbreviation
            self._parent[x] = self.root(self._parent[x])
            return self._parent[x]

    
    def same(self, x, y):
        return self.root(x) == self.root(y)


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        rank_x = self.__rank[x]
        rank_y = self.__rank[y]
        if rank_x < rank_y:
            self._parent[x] = y
        else:
            self._parent[y] = x
            if rank_x == rank_y:
                self.__rank[x] += 1
        return


possible_pows = []
cur_pow = 2
for i in range(32):
    possible_pows.append(cur_pow)
    cur_pow *= 2


N = int(fin())
A_list = [int(elem) for elem in fin().split()]
groups = tuple([defaultdict(list) for _ in range(32)])

for i, pow_2 in enumerate(possible_pows):
    for j, A in enumerate(A_list):
        if A in groups[i]:
            groups[i][A].append(j)
        elif A <= pow_2:
            groups[i][pow_2 - A].append(j)
    # print(groups[i])

# for i, A in enumerate(A_list):
#     if A in groups:
#         groups[A].append(i)
#     for pow_2 in possible_pows:
#         if pow_2 >= A:
#             groups[pow_2 - A].append(i)
# print(groups)


uf = UnionFind(N)
for groups_each_pow in groups:
    for group in groups_each_pow.values():
        if len(group) <= 1:
            continue
        item = group[0]
        for another_item in group[1:]:
            uf.unite(item, another_item)

# print(uf._parent)
# num_items_in_each_group = defaultdict(int)
# for i in range(N):
#     num_items_in_each_group[uf.root(i)] += 1
num_items_in_each_group = Counter(uf._parent)
# print(num_items_in_each_group)
num_pairs = 0
for num_items in num_items_in_each_group.values():
    num_pairs += (num_items // 2)
print(num_pairs)

Submission status: Wrong Answer

Solution code:
import bisect

p2 = [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, 1073741824]


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

A.sort()
ma = A[-1]

count = 0
for ai in A:
    for p2i in p2:
        temp = p2i - ai
        if temp <= ai:
            continue
        if temp > ma:
            break
        # print(p2i, ai, temp)
        i = bisect.bisect_left(A, temp)
        if i != len(A) and A[i] == temp:
            count += 1
            break
print(count)

Submission status: Wrong Answer

Solution code:
import itertools

# Prepareation
splitters = [2**t for t in range(1, 30)]

n = int(input())
a_list = set(map(int, input().split()))

a_combis = itertools.combinations(a_list, 2)
n_2powered = 0
for combi in a_combis:
    sum_combi = sum(combi) 
    if sum_combi in splitters:
        n_2powered += 1

print(n_2powered)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    from bisect import bisect_left

    N = int(raw_input())
    A = list(map(int, raw_input().split()))

    ans = 0
    C = Counter(A)
    C2 = sorted(Counter(A).items())
    X = []
    for x, num in C2:
        X.append([x, num])

    A = [x for x, num in C2]
    N = len(A)

    for i in range(N - 1, -1, -1):
        for j in range(C[A[i]]):
            for t in range(33, 0, -1):
                target = (2 ** t) - A[i]

                if target <= 0:
                    continue

                target_t = bisect_left(X, [target, -float('inf')])

                if target_t >= len(X):
                    continue

                x, num = X[target_t]
                if x == target and num > 0:
                    if i == target_t and num < 2:
                        continue
                    ans += 1
                    X[i][1] -= 1
                    X[target_t][1] -= 1
                    break

    print ans

main()

Submission status: Wrong Answer

Solution code:
def f(N, A):
    A.sort()
    A = [a for a in map(bin, A)]
    res = 0
    for i, a in enumerate(A[:-1]):
        tmpa = str(bin(~int(a, 0))).replace("-", "")[2:]
        for b in A[i+1:]:
            tmpb = b[-len(tmpa):]
            if tmpb == tmpa:
                res += 1
    return res
 
N = int(input())
A = list(map(int, input().split()))
print(f(N, A), flush=True)

Submission status: Wrong Answer

Solution code:

import bisect
ans = 0
N = int(input())
a = list(map(int,input().split()))
b = [True for _ in range(N)]
a.sort()
digit = 40
y = 2 ** (digit+1) -1
while len(a)>2:
    x = a.pop(-1)
    while x < 2**digit:
        digit -= 1
        y = 2 ** (digit+1) -1
    z = x^y
    z += 1
    ll =  bisect.bisect_left(a,z)
    rr =  bisect.bisect_right(a,z)
    if rr - ll == 1  and b[ll]:
        ans += 1
        b[ll] = False
    elif rr - ll >1:
        if b[ll] == True:
            if x != a[ll]:
                ans += 1
                b[ll] = rr-ll-1
            else:
                ccc = 1
                while len(a)>0 and a[-1] == x:
                    a.pop(-1)
                    ccc += 1
                ans += ccc//2
        elif b[ll]>0:
            if x != a[ll]:
                ans += 1
                b[ll] -= 1
            else:
                ans += b[ll]//2
                while len(a)>0 and a[-1] == x:
                    a.pop(-1)           
print(ans)