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)
rd = {a: i for i, a in enumerate(count)}
lc = len(count)
ma = max(count) * 2
ma2 = 2
while ma >= ma2:
    ma2 <<= 1

mf = Dinic(2 * lc + 2)

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

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

Submission status: Wrong Answer

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

ExTwo = [2**i for i in range(1, 31)]
Used = [False for i in range(N)]
Count = 0
for i in range(N):
    if not Used[i]:
        for j in reversed(range(30)):
            if ExTwo[j] <= A[i]: break
            else:
                Pair = ExTwo[j] - A[i]
                if Pair in A:
                    if not Used[A.index(Pair)] and i != A.index(Pair):
                        Used[A.index(Pair)] = True
                        Used[i] = True
                        Count += 1
                        break
print(Count)

Submission status: Wrong Answer

Solution code:
from itertools import combinations 
def main():
    ansers = set() 
    for i in range(32):
        ansers.add(2 ** i)
    print(ansers) 
    n = int(input())
    all_a = list(map(lambda x: int(x), input().split(' ')))
    all_a = sorted(all_a)
    count = 0
    while True:
        if len(all_a) == 0:
            break
        target = all_a.pop()
        for i in reversed(all_a):
            if target + i in ansers:
                count += 1
                all_a.remove(i)
                break

    print(count)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def int_reverse(num):
    num_len = len(bin(num))-2
    f = 2**num_len-1
    return num ^ f

from collections import Counter

n = ni()
a = list(li())

one_pos = [Counter() for _ in range(32)]

ans = 0

for ai in a:
    one = bin(ai)[::-1].index('1')
    ai = ai>>(one+1)
    one_pos[one] += Counter([ai])

for cnt in one_pos:

    for key in sorted(cnt.keys(),reverse=True):
        val = cnt[key]
        vlr = cnt[int_reverse(key)]
        if val and vlr:
            plus = min(val,vlr)
            ans += plus
            cnt[key] -= plus
            cnt[int_reverse(key)] -= plus


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N=int(input())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
for a in A:
    dd[a]+=1
#print(dd)
B=sorted(A,reverse=True)
ans=0
for x in B:
    #print(x)
    if dd.get(x)==0:
        continue
    s=len(bin(x))-3
    if x==1<<s:
        t=dd.get(x,-1)
        if t!=-1:
            ans+=t//2
            dd[x]-=(t//2)*2
            #print(ans)
            #print(dd)
    else:
        s+=1
        t=dd.get((1<<s)-x,-1)
        if t!=-1:
            ans+=t
            dd[(1<<s)-x]-=1
            #print(ans)
            #print(dd)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from itertools import combinations
N = int(input())
A = [int(i) for i in input().split(" ")]
beki = [math.pow(2, i) for i in range(10)]
combs = list(combinations(A, 2))
check = []
counts = []
for comb in combs:
  if sum(comb) in beki:
    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)):
    print(check[i], check[j])
    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 itertools

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

n = int(input())
a_list = set(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

print(n_2powered)

Submission status: Wrong Answer

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

ans_set = set()
for i in range(n-1):
    for j in range(i+1,n):
        if not ((a[i] + a[j]) & (a[i] + a[j]-1)):
            ans_set.add(a[i])
            ans_set.add(a[j])          

ans = int(len(ans_set)/2)
print(int(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
B = [2**k for k in range(1,31)]

ans = 0
for k in range(N-1):
    for l in range(k+1,N):
        if A[k]+A[l] in B:
            ans += 1
            break

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
'''
N = 5
A = [3,11,14,5,13]
'''

def check(a,b):
	i = 2
	while(True):
		n = 2**i
		if a+b < n:
			return False
		if a+b == n:
			return True
		i+=1


def ans(A,n):
	if len(A) <= 1:
		return n
	a = A[0]
	bs = A[1:]
	m = []
	flag = False
	for p,b in enumerate(bs):
		if check(a,b):
			flag = True
			n+=1
			m.append(ans(bs[:p]+bs[p+1:],n))
	if not flag:
		return ans(A[1:],n)
	return max(m)


print(ans(A,0))

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]):
        for b in A[i+1:]:
            tmpb = b[-len(a)+2:]
            tmpa = str(bin(~int(a, 0)))[3:]
            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:
N=int(input())
A=list(map(int, input().split()))
odd=[]
even=[]
for i in A:
    if i%2:
        odd.append(i)
    else:
        even.append(i)
odd.sort()
even.sort()
ls=[]
for i in range(30):
    ls.append(2<<i)

ans=0
if len(odd)>=2:
    for i in range(len(odd)):
        ct=0
        for j in range(len(ls)):
            if ct>=2:
                break
            if j>i:
                for k in range(len(odd)):
                    if odd[k]<j-i:
                        break
                    if odd[k]==j-i:
                        ct+=1
                        tmpi=i
                        tmpk=k
        if ct==1:
            odd.pop(tmpi)
            odd.pop(tmpk)
            ans+=1
if len(even)>=2:
    for i in range(len(even)):
        ct=0
        for j in range(len(ls)):
            if ct>=2:
                break
            if j>i:
                for k in range(len(even)):
                    if even[k]<j-i:
                        break
                    if even[k]==j-i:
                        ct+=1
                        tmpi=i
                        tmpk=k
        if ct==1:
            even.pop(tmpi)
            even.pop(tmpk)
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def int_reverse(num):
    num_len = len(bin(num))-2
    f = 2**num_len-1
    return num ^ f

from collections import Counter

n = ni()
a = list(li())
a.sort(reverse=True)

one_pos = [Counter() for _ in range(32)]

ans = 0

for ai in a:
    one = bin(ai)[::-1].index('1')
    ai = ai>>(one+1)
    one_pos[one] += Counter([ai])

for cnt in one_pos:

    for key in cnt.keys():
        val = cnt[key]
        vlr = cnt[int_reverse(key)]
        if val and vlr:
            plus = min(val,vlr)
            ans += plus
            cnt[key] -= plus
            cnt[int_reverse(key)] -= plus


print(ans)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
a.sort()
a.reverse()
def beki(s):
  k = math.log2(s)
  k = int(k) + 1
  return 2**k - s
i = 0
c = 0
while i < len(a):
  p = beki(a[i]) 
  print(p)
  if p in a[i+1:]:
    a.reverse()
    a.remove(p)
    a.reverse()
    c += 1
    i += 1
  else:
    i += 1
    
print(c)

Submission status: Wrong Answer

Solution code:
import collections
def hoge(n):
    k = 1    
    while k<=n:
        k*=2
    return k-n
ans = 0
input()
a = [int(x) for x in input().split()]
c = collections.Counter(a)
sa = list(set(a))
sa.sort()
for i in range(len(sa)-1,-1,-1):
    x = sa[i]
    if c[x]<= 0:
        continue    
    y = hoge(x)
    if x==y:
        ans += c[x]//2
    else:
        ans += min(c[x],c[y])
        c[y] -=c[x]
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
def hoge(n):
    k = 1    
    while k<=n:
        k*=2
    return k-n
ans = 0
input()
a = [int(x) for x in input().split()]
c = collections.Counter(a)
sa = list(set(a))
sa.sort()
for i in range(len(sa)-1,-1,-1):
    print(i)    
    x = sa[i]
    if c[x]<= 0:
        continue    
    y = hoge(x)
    if x==y:
        ans += c[x]//2
    else:
        ans += min(c[x],c[y])
        c[y] -=c[x]
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]
m = 0
while True:
    if 2**m > 2*max_a:
        break
    m += 1
used = [False] * n


def bisect(val, start, end):
    if start >= end:
        return None
    elif start + 1 == end:
        if a[start] == val:
            if used[start]:
                return None
            used[start] = True
            return start
        else:
            return None
    mid = (start + end) // 2
    if a[mid] == val:
        if used[mid]:
            res = bisect(val, mid+1, end)
            if res is not None:
                return res
            res = bisect(val, start, mid)
            return res
        else:
            used[mid] = True
            return mid
    elif a[mid] > val:
        return bisect(val, start, mid)
    else:
        return bisect(val, mid, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i]  == val):
    #         used[i] = True
    #         return i
    return None


def _find(b, end, e):
    "slow!!!!"
    # debug(b, end, e)
    val = 2**e - b
    if val <= 0:
        return None
    return bisect(val, 0, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i] + b == 2**e):
    #         used[i] = True
    #         return i
    # return None


def find(b, end):
    for e in reversed(range(m+1)):
        res = _find(b, end, e)
        if res is not None:
            return True
    return False


ans = 0
for j in reversed(range(n)):
    b = a[j]
    used[j] = True
    res = find(b, j)
    if res:
        debug(b, j)
        ans += 1


print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

A.sort()
A.reverse()

Ma = A[0]+A[1]
now = 1
count = -1

tmp = []

while now <= Ma:
    now = now*2
    count = count+1
    tmp.append(now)
    
ans = 0
now = 0
K = len(tmp)-1

while now<len(A)-1:
    c = A[now]
    if c<tmp[K-1] and len(tmp)>1:
        del tmp[K]
        K = K-1
    for i in range(now+1, len(A)):
        if A[i]+c == tmp[K]:
            del A[i]
            ans = ans+1
            break
    now = now+1
        
print(ans)

Submission status: Wrong Answer

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

ans1, ans2 = 0,0

maxA = max(A)
B = [1]
t = 1
while t < maxA:
    t *= 2
    B.append(t)

d = dict()
for i in range(N):
    if A[i] in d:
        d[A[i]] += 1
    else:
         d[A[i]] = 1

for i in range(N):
    t = 2**len(bin(A[i])[2::]) - A[i]
    if t in d:
        if d[t] > 0:
            ans2 += 1
            d[t] -= 1
            d[A[i]] -= 1

print(ans1+ans2)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
two_list = [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]

count = 0
items = {}
for a in A_list:
    if a in items:
        items[a] += 1

    else:
        items[a] = 1
A_list.sort(reverse=True)

for a in A_list:
    if items[a] >= 1:

        for t in two_list:
            m = t -a
            if m in items:
                if m == a and items[a] >= 2:
                    count += 1
                    items[a] -= 1
                    items[m] -= 1
                    break

                elif m != a and items[m] >= 1 and items[a] >=1:
                    count += 1
                    items[a] -= 1
                    items[m] -= 1
                    break
print(count)

Submission status: Wrong Answer

Solution code:
import math
import collections
n=int(input())
a=sorted(map(int,input().split()))[::-1]
s=dict(collections.Counter(a))
r=0
flag=False
for i in range(n):
    if flag:
        flag=False
        continue
    if s[a[i]]==0: break
    pair = 2**math.ceil(math.log2(a[i]))-a[i]
    if pair in s.keys() and s[pair]>0:
        s[a[i]]-=1
        s[pair]-=1
        r+=1
        continue
    if i<n-1 and pair==0 and a[i+1]==a[i] and s[a[i]]>=2:
        s[a[i]]-=2
        r+=1
        flag=True
print(r)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
a.sort()
amax = a[-1]
c = collections.Counter(a)

beki2 = [2**i for i in range(1,31)]

cnt = 0

for i in a:
    for j in beki2:
        if j-i > amax:
            break
        if j-i in c:
            if j-i == i and c[j-i] == 1:
                continue
            if c[j-i] == 0:
                continue
            cnt += 1
            c[j-i] -= 1

print(cnt//2)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())
A = list(map(int, input().strip().split()))
remain_a = [0 for _ in range(max(A) + 1)]
for a in A:
  remain_a[a] += 1
pair_d = {}
for i in range(len(A)):
  for j in range(i+1, len(A)):
    a = A[i] + A[j]
    if a & 1<<(len(bin(a))-3) == a:
      if A[i] not in pair_d:
        pair_d[A[i]] = [A[j]]
      else:
        pair_d[A[i]].append(A[j])

twop = 0
for i, jlist in sorted(pair_d.items(), key=lambda x: len(x[1])):
  for j in sorted(jlist, key=lambda x: remain_a[x]):
    if remain_a[i] > 0 and remain_a[j] > 0:
      twop += 1
      remain_a[i] -= 1
      remain_a[j] -= 1

print(twop)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
ma = sum(sorted(a)[-2:])
t = int(math.log2(ma))
al = []
for i in range(1, t+1):
  ti = 2**i
  for j in a:
    if ti-j in a:
      if not (j == ti-j and a.count(j) == 1):
        if not j in al and not ti-j in al:
          al.append(j)
print(len(al))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
nibeki = [int(2**i) for i in range(1, 30)]
count = 0
alredy = []

for i in range(N):
  alredy.append(i)
  for j in range(N):
    if j not in alredy:
      if A[i] + A[j] in nibeki:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import Counter


random_case =0
if not random_case:
    N = int(input())
    A = list(map(int , input().split()))
# A.sort()
else:
    import random
    A = [random.randint(1,10) for _ in range(7)]
    print(A)

beki = {2**i for i in range(32)}
beki_rlist = (([2**i for i in range(32)]))


def guchoku():
    max_ans = 0
    for tmp_a in itertools.permutations(A):
        tmp_ans = 0
        for i in range(len(A)//2):
            if tmp_a[2*i]+tmp_a[2*i+1] in beki:
                tmp_ans+=1
        max_ans = max(tmp_ans,max_ans)
    return max_ans


# print(guchoku())
# print("---")
ans = 0
c = Counter(A)
for i in sorted(c.keys()):
    for tmp in beki_rlist:
        if c[i]==0:
            break
        elif tmp == i*2:
            ans += c[i]//2
            c[i]-= c[i]//2 *2
        elif c[tmp-i]:
            val = min(c[i],c[tmp-i])
            c[i] -=val
            c[tmp-i]-=val
            ans +=val
print(ans)
# print(guchoku())
# print(c)
# print(ans==guchoku())

# print(c)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def int_reverse(num):
    num_len = len(bin(num))-2
    f = 2**num_len-1
    return num ^ f

from collections import Counter

n = ni()
a = list(li())

one_pos = [Counter() for _ in range(32)]

ans = 0

for ai in a:
    one = bin(ai)[::-1].index('1')
    ai = ai>>(one+1)
    one_pos[one] += Counter([ai])

for cnt in one_pos:

    for key in sorted(cnt.keys(),reverse=True):
        if cnt[key] and cnt[int_reverse(key)]:
            ans += 1
            cnt[key] -= 1
            cnt[int_reverse(key)] -= 1


print(ans)

Submission status: Wrong Answer

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

ans1, ans2 = 0,0

maxA = max(A)
B = [1]
t = 1
while t < maxA:
    t *= 2
    B.append(t)

d = dict()
for i in range(N):
    if A[i] in d:
        d[A[i]] += 1
    else:
         d[A[i]] = 1

for i in range(N):
    if A[i] not in B:
        t = 2**len(bin(A[i])[2::]) - A[i]
        if t in d:
            if d[t] > 0:
                ans2 += 1
                d[t] -= 1
                d[A[i]] -= 1

print(ans1+ans2)

Submission status: Wrong Answer

Solution code:
import collections
def hoge(n):
    k = 1    
    while k<=n:
        k*=2
    return k-n
ans = 0
input()
a = [int(x) for x in input().split()]
c = collections.Counter(a)
sa = list(set(a))
sa.sort()
for i in range(len(sa)-1,0,-1):
    x = sa[i]
    if c[x]<= 0:
        continue    
    y = hoge(x)
    if x==y:
        ans += c[x]//2
    else:
        ans += min(c[x],c[y])
        c[y] -=c[x]
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    retval = 0
    memo = {}
    for a in A:
        pair_created = False
        for i in range(30, 0, -1):
            s = pow(2, i)
            if a < s and (s-a) in memo and memo[s-a]:
                memo[s-a] -= 1
                pair_created = True
                break
        if pair_created:
            retval += 1
            continue
        if a not in memo:
            memo[a] = 0
        memo[a] += 1
    print(retval)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

if __name__ == '__main__':
    n = int(input())
    d = dict(Counter(int(s) for s in input().split()))
    ans = 0
    for x in (1 << i for i in range(29, 0, -1)):
        d2 = {}
        for v, c in d.items():
            cmpl = x - v
            if cmpl < 0:
                d2[v] = c
                continue
            if cmpl in d2:
                c2 = d2[cmpl]
                if c < c2:
                    d2[cmpl] -= c
                    ans += c
                else:
                    del d2[cmpl]
                    ans += c2
                    if c > c2:
                        d2[v] = c - c2
            else:
                d2[v] = c
        d = {}
        for v, c in d2.items():
            d[v] = c
    print(ans)

Submission status: Wrong Answer

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

import bisect

n=int(input())
a = [int(i) for i in input().split()]
a.sort()
#print(a)
checked=[0]*n

ans=0

while(a):
    if checked[len(a)-1]==1:
        c=a.pop()
        continue
    c=a.pop()
    d=c
    keta=0
    while(d!=0):
        d=d//2
        keta +=1
    x = 2**keta - c
#    print(c,x)
    i = bisect.bisect_right(a, x)
    if i and a[i-1] == x and checked[i-1]==0:
        ans += 1
        checked[i-1]=1
#        print(checked)
#        print(a[i],c,"xxx")




print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(i) for i in input().split()]

A.sort()
m = 2 ** 30
used = set()
ans = 0

def search(ok, ng, n):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if A[mid] < n or (A[mid] == n and mid in used):
        return search(mid, ng, n)
    else:
        return search(ok, mid, n)

for i in range(30):
    m //= 2
    for j in range(n):
        if j in used or A[j] >= m:
            continue
        a = search(-1, n, m - A[j]) + 1
        if a >= n:
            continue
        if A[a] == m - A[j]:
            if a == j:
                if not A[a+1] == A[j]:
                    continue
                a += 1
            used.add(a)
            used.add(j)
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
evens, odds = [], []
for x in input().split():
    x = int(x)
    if x % 2 == 0:
        evens.append(x)
    else:
        odds.append(x)

def ok(x, y):
    if math.log(x+y, 2).is_integer():
        return True
    return False

def search(ls):
    count = 0
    used = [0 for _ in range(len(ls))]
    for i, x in enumerate(ls):
        if used[i] != 1:
            for j, y in enumerate(ls[i+1:]):
                if used[i+j+1] != 1 and ok(x, y):
                    count += 1
                    used[i] = used[i+j+1] = 1
    return count


print(search(evens) + search(odds))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int( input())
A = list( map( int, input().split()))
V = [0]*N
ans = 0
for i in range(30,0,-1):
    D = defaultdict( lambda:[])
    T = 2**i
    for j in range(N):
        if V[j] == 1:
            continue
        if A[j] < T:
            if D[T - A[j]]:
                ans += 1
                V[D[T-A[j]].pop()]=1
                V[i] = 1
            else:
                D[A[j]].append(j)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

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

ans = 0
even = []
odd = []

for i in range(N):
    if A[i] % 2 == 0:
        even.append(A[i])
    else:
        odd.append(A[i])

#print(even)
#print(odd)

even2 = copy.deepcopy(even)
odd2 = copy.deepcopy(odd)

for i in range(len(even)):
    for j in reversed(range((len(even2)))):
        if i >= j:
            break
        num = even[i] + even2[j]
        if not (num & (num - 1)):
            #print(i,j)
            ans += 1
            del even2[j]
            break


for i in range(len(odd)):
    for j in reversed(range((len(odd2)))):
        if i >= j:
            break
        num = odd[i] + odd2[j]
        if not (num & (num - 1)):
            #print(i,j)
            ans += 1
            del odd2[j]
            break

print(ans)

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)

rec = defaultdict(int)
for i in range(N):
    rec[A[i]] = i + 1

for i in range(1, N + 1):
    for k in range(31):
        j = rec[2 ** k - A[i - 1]]
        if i - 1 != j and j != 0:
            j = rec[2 ** k - A[i - 1]]
            G[i - 1].append(N + j - 1)
            G[j - 1].append(N + i - 1)


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:
from collections import Counter
from bisect import bisect_left

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

ans = 0
C = []
for x, num in dict(Counter(A)).items():
    C.append([x, num])
C.sort()

A = []
for x, num in C:
    A.append(x)

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

        if target <= 0:
            continue

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

        if target_t >= len(C):
            continue

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

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque
N=int(input())

E=deque()
O=deque()

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

for i in range(len(a)):
    if a[i]%2==0:
        E.append(a[i])
    else:
        O.append(a[i])
        
E=list(E)
O=list(O)
E.sort()
O.sort()

ans=0
for e in range(len(E)):
    t=0
    while E[len(E)-1-e]>2**t:
       t=t+1
       #print(t)
    if E[bisect.bisect_left(E,2**t-E[len(E)-1-e])]+E[len(E)-1-e]==2**t:
        ans+=1
        E[bisect.bisect_left(E,2**t-E[len(E)-1-e])]-=0.5
        
for o in range(len(O)):
    t=0
    while O[len(O)-1-o]>2**t:
       t=t+1
       #print(t)
    if O[bisect.bisect_left(O,2**t-O[len(O)-1-o])]+O[len(O)-1-o]==2**t:
        ans+=1
        O[bisect.bisect_left(O,2**t-O[len(O)-1-o])]-=0.5
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a0=[]
a1=[]
for i in a:
    if i%2==0:
        a0.append(i)
    else:
        a1.append(i)
ans=0
if len(a0)>1:
    a0.sort()
    a0.reverse()
    for j in range(len(a0)-1):
        for k in range(j+1,len(a0)):
            if a0[k]!=-1:
                b=j+k
                while b%2==0:
                    b//=2
                if b==1:
                    ans+=1
                    a0[k]=-1
                    break
if len(a1)>1:
    a1.sort()
    a1.reverse()
    for j in range(len(a1)-1):
        for k in range(j+1,len(a1)):
            if a1[k]!=-1:
                b=j+k
                while b%2==0:
                    b//=2
                if b==1:
                    ans+=1
                    a1[k]=-1
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
a.sort()
amax = a[-1]
c = collections.Counter(a)

beki2 = [2**i for i in range(1,31)]

cnt = 0

for i in a:
    for j in beki2:
        if j-i > amax:
            break
        if j-i in c:
            if j-i == i or c[j-i] == 0:
                continue
            cnt += 1
            c[j-i] -= 1

print(cnt//2)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
H = defaultdict(lambda: [])
Ad = defaultdict(lambda: 0)
N = int(input())
A = inpl()
for i in A:
    Ad[i] += 1
ans = 0
for j in range(30,0,-1):
    k = 2**j
    t = []
    H = defaultdict(lambda: [])
    for i, j in Ad.copy().items():
        if k <= i:
            break
        if 2*i == k:
            m = Ad[i]//2
            Ad[i] -= m
            ans += m
        if H[k-i]:
            m = min(Ad[k-i], Ad[i])
            Ad[k-i] -= m
            Ad[i] -= m
            ans += m
        else:
            H[i] = j
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
p = 1
while 2**p <=a[0]:
    p += 1
ans = 0
m =len(a)
for i in range(p,0,-1):
    j=0
    while j < m:
        k = j+1
        if k == m:
            print(ans)
            exit()
        while a[j]+a[k]>=2**i:
            if a[j]+a[k]== 2**i:
                ans += 1
                a.remove(a[k])
                m -=1
                break
            else:
                k += 1
                if k ==m:
                    break
        j += 1