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 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],2)))
    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
                    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:
# -*- coding: utf-8 -*-
from collections import defaultdict, deque
N = int(input())
tmp = list(map(int, input().split()))
An = deque()
for a in tmp:
    An.append(a)

maxA = max(tmp)

t2 = [2**i for i in range(32) if 2**i <= maxA]
t2.reverse()

ans = 0
for t in t2:
    tmp_dict = defaultdict(list)
    for A in An:
        tmp_dict[A%t].append(A)

    tmp = 0
    for k,v in list(tmp_dict.items()):
        m = min([len(v), len(tmp_dict[t-k])])
        if m > 0:
            tmp += m
            for l in v + tmp_dict[t-k]:
                try:
                    An.remove(l)
                except Exception:
                    pass
    ans += tmp//2

print(ans)

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],2)))
    print(val2)
    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
                    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:

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

count = 0
for i in range(len(x)):
    for j in range(1, len(x)):
        if i+j > len(x)-1:
            break
        search = x[i] + x[i+j]

        while True:
            div = search / 2
            search = div

            keisan = div * 10
            keisan = str(int(keisan))
            if keisan[-1] != '0':
                break

            if div == 1.0:
                count += 1
                break

print(count)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from math import log2
n = int(input())
a = [int(i) for i in input().split()]
a,x,ans = sorted(a),[1]*n,0
for i in range(n-1,-1,-1):
	if x[i]:
		m = 2**(int(log2(a[i]))+1)
		b = bisect_left(a,m-a[i])
		if a[b]==m-a[i] and i!=b: x[b],ans = 0,ans+1
print(ans)

Submission status: Wrong Answer

Solution code:
def search(_a, tmp):
    while _a >= 2 ** tmp:
        tmp += 1
    return tmp


n = int(input())
a = [int(i) for i in input().split()]
# a[i] + a[j] = 2^tとなる組の最大数
a.sort()
# print(a)
# diff = [search(a[i]) - a[i] for i in range(len(a))]
diff = [[0, i] for i in range(len(a))]
tmp = 0
for i in range(len(diff)):
    tmp = search(a[i], tmp)
    diff[i][0] = 2 ** tmp - a[i]
# print("   a:{}".format(a))
# print("diff:{}".format(diff))
diff.sort()
# print("diff:{}".format(diff))

i = 0
j = 0
count = 0
while i < len(a) and j < len(diff):
    # print("i:{} j:{} count:{}".format(i, j, count))
    while j < len(diff) and diff[j][0] < a[i]:
        j += 1
    if j < len(a) and a[i] == diff[j][0]:
        if i != diff[j][1]:
            count += 1
            i += 1
            if i > 0 and a[i - 1] == a[i] and i == diff[j][1]:
                i += 1
            j += 1
        else:
            j += 1
    else:
        i += 1
print(count)

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)>1:
    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)

Submission status: Wrong Answer

Solution code:
N = int(input())
two_pow = [2 ** i for i in range(1,34)]
A = [int(x) for x in input().split()]
t = [True for i in range(N)]
ans = 0
A.sort()
for i in range(N):
    if t[i]:
        for j in range(N-1,i,-1):
            if t[j] and A[i] + A[j] in two_pow:
                ans += 1
                t[i] = t[j] = False
                break

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 15 21:15:13 2018
AGC029B
@author: maezawa
"""
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:
    if c[i] == 0:
        continue
    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
            c[i] -= 1
            #print(i,j-i)

print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy

N = int(input())
A_list = list(map(int, input().split(" ")))

max_A = max(A_list)
max_shisuu = int(np.ceil(max_A)) + 1

two_powers = [2 ** shisuu for shisuu in range(max_shisuu+1)]
count_list = np.zeros((N,), dtype=int)

#pair_dict = {}
two_power_pairs = []

aite_dict = {}
for i in range(N):
    aite_dict[i] = []

for i in range(N):
    for j in range(i+1, N):
        pair_sum = A_list[i]+A_list[j]
        if pair_sum in two_powers:
            two_power_pairs.append((i, j))
            count_list[i] += 1
            aite_dict[i] += [j]
            aite_dict[j] += [i]
            

class OUT:
    def __init__(self, two_power_pairs, pair_list, count_list, aite_dict):
        self.two_power_pairs = copy.deepcopy(two_power_pairs)
        self.pair_list = copy.deepcopy(pair_list)
        self.count_list = copy.deepcopy(count_list)
        self.aite_dict = copy.deepcopy(aite_dict)


    def find_pair(self):
        two_power_pairs = self.two_power_pairs
        count_list = self.count_list
        aite_dict = self.aite_dict
        tmp_count_list = count_list[count_list >= 1]
        
        if len(tmp_count_list) == 0:
            return None

        min_count = min(tmp_count_list)

        min_indexs = np.where(count_list == min_count)[0]
        
        ## 1 pair
        jibun = min_indexs[0]
        aite = aite_dict[jibun][0]
        out_pairs = [(jibun, aite)] if jibun <= aite else [(aite, jibun)]
        
        return out_pairs
    
    def register(self, target_pair):
        self.two_power_pairs.remove(target_pair)
        self.pair_list.append(target_pair)
        jibun, aite = target_pair
        self.aite_dict[jibun].remove(aite)
        self.aite_dict[aite].remove(jibun)
        self.count_list[jibun] -= 1
        self.count_list[aite] -= 1



pair_list = []
out_obj = OUT(two_power_pairs, pair_list, count_list, aite_dict)
out_obj_list = [out_obj]
obj_i = 0
while obj_i < len(out_obj_list):
    out_obj = out_obj_list[obj_i]
    target_pairs = out_obj.find_pair()
    
    if target_pairs is None:
        obj_i += 1
        continue
    
    #if len(target_pairs) >= 1:
    #    tmp_out_obj_list = [copy.deepcopy(out_obj) for i in range(1, len(target_pairs))]
    
    target_pair = target_pairs[0]
    #print(target_pair, out_obj.two_power_pairs)
    out_obj.register(target_pair)

print(max([len(out_obj.pair_list) for out_obj in out_obj_list]))
#print([(out_obj.pair_list) for out_obj in out_obj_list])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
N = int(input())
An = list(map(int, input().split()))

maxA = max(An)

t2 = [2**i for i in range(32) if 2**i <= maxA]
t2.reverse()

ans = 0
for t in t2:
    tmp_dict = defaultdict(list)
    for A in An:
        tmp_dict[A%t].append(A)

    tmp = 0
    for k,v in list(tmp_dict.items()):
        m = min([len(v), len(tmp_dict[t-k])])
        if m > 0:
            tmp += m
            for l in v + tmp_dict[t-k]:
                try:
                    An.remove(l)
                except Exception:
                    pass
    ans += tmp//2

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()
M=a[-1]*2

count=0
for i in range(n):
    powers=2
    while powers<M:
        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)
        powers*=2

print(count)

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
    if c[m] == 0:
        del c[m]
    if n in c:
        c[n] -= 1
        if c[n] == 0:
            del c[n]
        ans += 1
    c += Counter()

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 15 21:15:13 2018
AGC029B
@author: maezawa
"""
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:
    if c[i] == 0:
        continue
    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
            c[i] -= 1
            print(i,j-i)

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = {}
for i in range(len(a)):
    b[a[i]] = i
twins = []
now = 1
while now < a[-1]:
    now *= 2
    twins.append(now)
for i in range(len(a) - 1, 0, -1):
    tmpa = 0
    if a[i] not in b:
        continue
    for j in range(len(twins) - 1, 0, -1):
        if twins[j] < a[i]:
            break
        tmpa = twins[j] - a[i]
    if tmpa in b and b[tmpa] != i:
        del b[tmpa]
        del b[a[i]]

print((len(a) - len(b)) // 2)

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:
                    cnt_m = min(cnt, count[b])
                    mf.add_link(rd[a] + 1, lc + rd[b] + 1, cnt_m)
        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:
N = int(input())
A = list(map(int, input().split()))

dellist = lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]


def search(l, pair_num, level):

    none_flg = 1
    base = pair_num
    for i in range(1, len(l)):
        if ((l[0] + l[i]) & (l[0] + l[i] - 1)) == 0:
            next_l = dellist(l, [0, i])
            none_flg = 0
            pair_num = max(pair_num, search(next_l, base + 1, level=level+1))
    if none_flg:
        return pair_num

    return pair_num

print(search(l=A, pair_num=0, level=0))

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(29):
    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:
                a += 1
                if a >= n or not A[a] == A[j]:
                    continue
            used.add(a)
            used.add(j)
            ans += 1
    m //= 2

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()
M=a[-1]*2

powers=2
count=0
for i in range(n):
    while powers<M:
        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)
        powers*=2

print(count)

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])

even = sorted(even)
odd = sorted(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)):
            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)):
            ans += 1
            del odd2[j]
            break

print(ans)

Submission status: Wrong Answer

Solution code:
# http://www.geocities.jp/m_hiroi/light/pyalgo61.html
class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a


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]

uf = UnionFind(N)

for i, ai in enumerate(A):
    for p2i in p2:
        temp = p2i - ai
        if temp <= ai:
            continue
        if temp > ma:
            break
        j = bisect.bisect_left(A, temp)
        if j != N and A[j] == temp:
            uf.union(i, j)

count = 0
for t in uf.subsetall():
    l, r = t
    count += r // 2
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = (int(i) for i in input().split())

B = []
for i in A:
    B.append(i)

num = 0
for i in B:
    num = num + B.count(2**(len(bin(i)) - 1) - i)
print(num)

Submission status: Wrong Answer

Solution code:
import copy

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


x = 1
beki = []
while x <= 2*10**9:
    x *= 2
    beki.append(x)

useA = copy.deepcopy(A)

pairs = 0
for i in range(len(beki)):
    full = beki[len(beki)-i-1]
    for j in range(N):
        firsthalf = A[j]
        otherhalf = full - firsthalf
        if otherhalf > 0:
            if firsthalf in useA and otherhalf in useA:
                pairs += 1
                useA.remove(firsthalf)
                
                try:
                    useA.remove(otherhalf)
                except:
                    useA.append(firsthalf)
                pairs -= 1

print(pairs)

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)
    idx = []
    for j in range(ceil(log2(t)), int(log2(t * 2)) + 1):
        pair = 2 ** j - t
        # print(t, pair)
        idx.append(bisect(a, pair, i))

    idx = [(x, a.count(a[x])) for x in idx if x != -1]

    if len(idx) == 0: continue

    # print(idx)
    to_use_idx = -1
    to_use_num = -1
    if len(idx) > 1:
        for i, c in idx:
            if to_use_num < c:
                to_use_idx = i
                to_use_num = c
            elif to_use_num == c:
                if to_use_idx < i:
                    to_use_idx = i
                    to_use_num = c
    elif len(idx) == 1:
        to_use_idx = idx[0][0]
    b[to_use_idx] = False
    b[i] = False
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from collections import defaultdict as dd

beki2 = [2**i for i in range(31)]
SOURCE = 0
SINK = 10**9+1

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

ct = Counter(A)
edge = dd(lambda: dd(int))
for i in sorted(ct.keys()):
  numi = ct[i]
  edge[SOURCE][-i] = numi
  edge[i][SINK] = numi
  for j in beki2:
    k = j - i
    if k < i:
      continue
    if i == k:
      #edge[-i][i] += numi // 2
      pass
    else:
      if k in ct:
        numk = ct[k]
        edge[-i][k] += numi if numi < numk else numk

# max-flow
# Ford-Fulkerson (impl: DFS)
visited = set()
def find_route(start, goal, bottleneck):
  global visited
  visited.add(start)
  if start == goal:
    return bottleneck
  for to in edge[start]:
    if to in visited or edge[start][to] <= 0:
      continue
    flow = find_route(
      to,
      goal,
      bottleneck if bottleneck <= edge[start][to] else edge[start][to]
    )
    if flow > 0:
      edge[start][to] -= flow
      edge[to][start] += flow
      return flow
  return 0

ans = 0
while True:
  visited = set()
  flow = find_route(SOURCE, SINK, float("inf"))
  if flow == 0:
    break
  ans += flow

# あまりで、同じ数を2つでペア作れるものを作る
for k, v in edge[0].items():
  if -k in beki2:
    ans += v // 2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
B = defaultdict(lambda: defaultdict(int))
cnt = 0
for a in A:
  idx = a
  lb = 0
  bits = ''
  rev = ''
  buf = ''
  rbuf = ''
  while idx:
    if idx % 2:
      idx //= 2
      break
    else:
      lb += 1
      idx //= 2
  if idx == 0:
    bits = '0'
    rev = '1'
  else:
    while idx:
      buf += str(idx % 2)
      rbuf += str(1 - idx % 2)
      if idx % 2 == 0:
        bits += buf
        buf = ''
        rev += rbuf
        rbuf = ''
      idx //= 2
    bits += '10' if buf == '1' else '1'
    rev += '0'
  if B[lb][bits] > 0:
    B[lb][bits] -= 1
    cnt += 1
  else:
    B[lb][rev] = 1
print(cnt)

Submission status: Wrong Answer

Solution code:
def f(N, A):
    A.sort()
    #A = [a for a in map(bin, A)]
    used = [False] * N
    res = 0
    for i, a in enumerate(A[:-1]):
        if used[i]: continue
        for j, b in list(enumerate(A[i+1:]))[::-1]:
            if used[i+j+1]: continue
            #print(i, a, ":", i+j+1, b)
            if  all([x == "0" for x in bin(a+b)[3:]]):
                #print("↑↑↑")
                res += 1
                used[i] = True
                used[i+j+1] = True
                break
    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 = map(int, input().split())


def is2t(val):
    mod = 0
    while mod == 0:
        val, mod = divmod(val, 2)
    return val == 0


n_pears = 0

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

print(n_pears)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
maxa=max(a)
m=len(bin(maxa))-2
x=[[] for _ in range(m)]
for i in range(n):
    x[len(bin(a[i]))-3].append(a[i])
#print(x)
y=[]
for i in range(m):
    ti=m-1-i
    tx=[]
    for j in range(len(x[ti])):
        tj=len(x[ti])-1-j
        tx=2**(len(bin(x[ti][tj]))-2)-x[ti][tj]
        tk=len(bin(tx))-3
        judge=True
        #print(tx,x[ti][tj])
        if x[ti][tj]==tx:
            y.append(tx)
            continue
        for k in range(len(x[tk])):
            if x[tk][k]==tx:
                judge=False
                del x[tk][k]
                break
        if judge:
            y.append(x[ti][tj])
y.sort()
ans=0
z=[2**i for i in range(32)]
y.append(0)
#print(y)
j=False
for i in range(len(y)-1):
    if y[i] in z:
        if y[i]==y[i+1]:
            if j:
                j=False
            else:
                j=True
        elif j is False:
            ans+=1
    else:
        ans+=1
ans=(n-ans)//2
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = sorted([int(_) for _ in input().split()], reverse=True)
dp = {}
for a in A:
    dp[a] = dp.get(a, 0) + 1
ans = 0
for a in A:
    dp[a] -= 1
    if dp.get(2**int(math.log2(a) + 1) - a, 0) > 0:
        dp[2**int(math.log2(a) + 1) - a] -= 1
        ans += 1
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(b[j]-a[i] == a[i]):
            c += 1
            a[a.index(b[j]-a[i])] = 0
            break
print(c)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math

N=int(input())

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

answer=0
A.sort(reverse=True)

Amax=A[0]
limit=1
while(True):
  if limit>Amax:
    break;
  limit*=2

Acounter=Counter(A)
print(Acounter)

while(limit!=1):
  for number,count in Acounter.items():
    if limit-number in Acounter.keys():
      if number==limit-number:
        dec=math.floor(Acounter[number]/2)
        Acounter[number]-=dec
      else:
        dec=min(Acounter[number],Acounter[limit-number])
        Acounter[number]-=dec
        Acounter[limit-number]-=dec
      answer+=dec
  limit=int(limit/2)
print(answer)

Submission status: Wrong Answer

Solution code:
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
already = set()

def is_in(t, n):
    i = bisect.bisect_left(A[:n + 1], t)
    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            return i
        i += 1

    return -1

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    already.add(n)
    a = A[n]
    t = 2 ** (math.log2(a) + 1)
    while t > a:
        i = is_in(t, n)
        if i != -1:
            res += 1
            break
        t //= 2

print(res)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict
n = int(input())
#evens, odds = {}, {}
evens, odds = defaultdict(int), defaultdict(int)
for x in input().split():
    x = int(x)
    if x % 2 == 0:
        #evens.append(x)
        evens[x] = 1
    else:
        odds[x] = 1
        #odds.append(x)

# 存在:1 ない:0 使用:2

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

def search(ls, even_used, odds_used):
    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

even_max = max(evens.values())
count = 0
odds_used = [0 for _ in range(len(odds))]
even_used = [0 for _ in range(len(evens))]
odds_v = list(odds.keys())
evens_v = list(evens.keys())

for i, x in enumerate(odds_v):
    if odds[x] == 1:
        for j, y in enumerate(odds_v[i+1:]):
            if odds[y] == 1 and ok(x, y):
                count += 1
                odds[x] = odds[y] = 2
                for k in range(1, even_max):
                    a = x * (2 ** k)
                    b = y * (2 ** k)
                    if max(a, b) > even_max:
                        break
                    if evens[a] == evens[b] == 1:
                        evens[a] = evens[b] = 2
                        count += 1

for i, x in enumerate(evens_v):
    if evens[x] == 1:
        for j, y in enumerate(evens_v[i+1:]):
            if evens[y] == 1 and ok(x, y):
                count += 1
                evens[x] = evens[y] = 2

print(count)