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: Accepted

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

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

from collections import Counter

acnt = Counter(a)

ans = 0
temp = 0
for ai in sorted(a,reverse=True):
    pair = (1<<(ai.bit_length())) - ai
    
    if acnt[ai] > 0 and acnt[pair] > 0:
        if ai == pair:
            temp = (acnt[ai] // 2)
            ans += temp
            acnt[ai] -= (2*temp)
            
        elif ai > pair:
            temp = min(acnt[ai], acnt[pair])
            ans += temp
            acnt[ai] -= temp
            acnt[pair] -= temp
            
print(ans)

Submission status: Accepted

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

A.sort(reverse=True)
dic={}
for a in A:
    dic[a]=dic.get(a,0)+1

ans=0

for a in A:
    small=(1<<(len(format(a,"b")))) -a
    if small==a:
        if dic[a]>=2:
            dic[a]-=2
            ans+=1
        continue
    if dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a]-=1
        dic[small]-=1
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

b = {}
for c in a:
    try:
        b[c] += 1
    except:
        b[c] = 1


pow2 = 1
while pow2 <= a[0]:
    pow2 *= 2
# print(a, pow2)
cnt = 0
for aa in a:
    while  aa < (pow2//2):
        pow2 //= 2
    
    v = aa
    rem = pow2 - aa
    # print(aa, pow2, v, rem)
    if (not v in b) or (not rem in b):
        continue

    if rem != v and (b[v] > 0 and b[rem] > 0):
        hit = min(b[v], b[rem])
        cnt += hit
        b[v] -= hit
        b[rem] -= hit
    elif rem == v and b[v] > 1:
        cnt += b[v]//2
        b[v] = b[v]%2

print(cnt)



# b = {}
# c = {}
# # print(a)
# for e,i in enumerate(a):
#     b[i] = (e, [(x[0]+e+1, x[1]) for x in enumerate(a[e+1:])])

# # print(b)
# for be in b: # (3, (0, [(1,5),...]) in [3,5,..]
#     for j in b[be][1]:
#         try:
#             if (not (b[be][0], j[0]) in c[be+j[1]]):
#                 # c[be + j[1]].append(b[be][0])
#                 # c[be + j[1]].append(j[0])
#                 c[be+j[1]].append((b[be][0], j[0]))
#         except:
#             c[be + j[1]]  = [(b[be][0], j[0])]
#             # c[be + j[1]].append(b[be][0])
#             # c[be + j[1]].append(j[0])


# # print("c: ", c)
# d= []

# twopowerlist = [2**p for p in range(30)]
# for n in twopowerlist:
#     try:
#         # print(n, c[n])
#         # d[n] = len(c[n])//2
#         d.append(c[n])
#     except:
#         pass
# d.sort(key=lambda x:len(x))
# d.reverse()

# for p in [x for y in d[0] for x in y]:
#     # print("p:",  p)
#     for e,q in enumerate(d[1:]):
#         for j in q:
#             if p in j:
#                 try:
#                     d.pop(e+1)
#                 except:
#                     pass

# # print(d)
# print(len(d[0]))






###########################3



# b = {}
# c = {}
# for e,i in enumerate(a):
#     b[i] = [copy.deepcopy(a)[e+1:], 1]
#     c[i] = 1

# for be in b:
#     for j in b[be][0]:
#         try:
#             c[j+be] += 1
#         except:
#             c[j+be] = 1


# sum = 0
# for n in twopowerlist:
#     try:
#         sum += c[n]
#     except:
#         pass
# print("list: ", c)
# print(sum)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict

def main():
    n = int(input())
    nums = list(map(int, input().split()))
    nums.sort()

    nums_cnt = defaultdict(int)
    for num in nums:
        nums_cnt[num] += 1

    cnt = 0
    for num in reversed(nums):
        if nums_cnt[num] <= 0:
            continue

        power_of_2 = 1 << math.ceil(math.log2(num))
        pair = power_of_2 - num

        if pair != 0 and nums_cnt[pair] > 0:
            nums_cnt[pair] -= 1
            nums_cnt[num] -= 1
            cnt += 1
        elif pair == 0 and nums_cnt[num] >= 2:
            nums_cnt[num] -= 2
            cnt += 1

    print(cnt)
    return

main()

Submission status: Accepted

Solution code:
import math
from collections import defaultdict

def main():
    _ = int(input())
    nums = list(map(int, input().split()))
    n = len(nums)
    nums.sort()

    nums_cnt = defaultdict(int)
    for num in nums:
        nums_cnt[num] += 1

    cnt = 0
    #print(num_bin_digits)

    for cur in reversed(range(n)):
        num = nums[cur]
        if nums_cnt[num] <= 0:
            continue

        power_of_2 = 1 << math.ceil(math.log2(num))

        pair = power_of_2 - num


        if pair != 0 and nums_cnt[pair] > 0:
            nums_cnt[pair] -= 1
            nums_cnt[num] -= 1
            cnt += 1
        elif pair == 0 and nums_cnt[num] >= 2:
            nums_cnt[num] -= 2
            cnt += 1


        '''
        idx = bisect.bisect_left(nums, pair)
        if idx >= cur or nums[idx] != pair:
            #print('continue',pair, idx)
            continue

        while used[idx]:
            idx += 1

        if nums[idx] == pair:
            used[idx] = True
            cnt += 1

        #print(idx, num, power_of_2, pair)
        #print(cnt, nums, used)
        '''

        #print(nums_cnt)

    print(cnt)

    return

main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
dic = {}
for a in A:
    dic[a] = dic.get(a,0)+1
ans = 0

for a in A:
    small = (1<<(len(format(a,"b")))) - a
    if small == a:
        if dic[a] >= 2:
            dic[a] -= 2
            ans += 1
        continue
    if dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a] -= 1
        dic[small] -= 1
        ans += 1
print(ans)

Submission status: Accepted

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):
    if(dict1[arr[i]]>0):
        xd=2**(len(bin(arr[i]))-2)
        if(xd-arr[i]!=arr[i]):
            try:
                if(dict1[xd-arr[i]]>0):
                    ans+=1
                    dict1[xd-arr[i]]-=1
                    dict1[arr[i]]-=1
            except:
                KeyError
        else:
            if(dict1[arr[i]]>1):
                ans+=1
                dict1[arr[i]]-=2
print(ans)

Submission status: Accepted

Solution code:
def b_powers_of_two(N, A):
    # 参考: https://beta.atcoder.jp/contests/agc029/submissions/3804857
    from bisect import bisect_left
    a = sorted(A)
    ans = 0
    for j in range(N - 1, -1, -1):
        # b > a[j]となるような最小のb(これは2の冪乗である)を探す
        b = 1
        while b <= a[j]:
            b <<= 1

        k = bisect_left(a, b - a[j])
        if k < j and (b - a[j] == a[k]):
            # a[k] <= a[j] であり、かつ、a[j] + a[k] = b(2の冪乗)
            # となるペア(j, k)が見つかれば、貪欲にペアにしてよい。
            # (a[j] を放置すると、ペアにできる可能性がある整数が少なくなり、得にならない)
            ans += 1
            # 整数でなくしておいて、ペアに使えないようにする。
            # ペアのうち、要素番号が大きい方は足し、小さい方は引いておくと、
            # 同じ値が複数あったときも二部探索で以前にペアにした整数を
            # ピックアップすることがなくなる。
            a[j] += 0.1
            a[k] -= 0.1

    return ans

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

Submission status: Accepted

Solution code:
from collections import Counter

def larger_nibeki(i):
	return 2 ** len(format(i, "b"))

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = 0
c = Counter(a)

for i in range(n):
	if c[a[i]] == 0:
		continue
	else:
		c[a[i]] -= 1
		if c[larger_nibeki(a[i]) - a[i]] > 0:
			ans += 1
			c[larger_nibeki(a[i]) - a[i]] -= 1

print(ans)

Submission status: Accepted

Solution code:
import math

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

count = 0

b = {}
for i in range(len(a)):
    if a[i] in b:
        b[a[i]] += 1
    else:
        b[a[i]] = 1

for i in range(len(a) - 1, -1, -1):
    if  b[a[i]] == 0:
        continue
    temp = a[i]
    b[a[i]] -= 1
    s=2**math.floor(math.log2(temp))
    st = 2*s - temp 
    if a ==[]:
        break
    if st in b and b[st] > 0:
        b[2*s-temp] -= 1
        count += 1
    
print(count)

Submission status: Accepted

Solution code:
def solve(C):
    ans = 0
    for a in sorted(C, reverse=True):
        if C[a] <= 0:
            continue
        ma = 1 << a.bit_length()
        b = ma - a
        if b in C and C[b] > 0:
            if a == b:
                pair = C[a] // 2
            else:
                pair = min(C[a], C[b])
                C[b] -= pair
            ans += pair
    return ans

from collections import defaultdict
N, *A = map(int, open(0).read().split())
C_e = defaultdict(int)
C_o = defaultdict(int)
for a in A:
    if a % 2 == 0:
        C_e[a] += 1
    else:
        C_o[a] += 1
print(solve(C_e) + solve(C_o))

Submission status: Accepted

Solution code:
from collections import Counter

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

def nibeki(x):
    cnt = 0
    while(x>1):
        x //=2
        cnt += 1
    return 2**(cnt+1)

cntSet = 0
c = Counter(a)
ks = list(c.keys())
ks.sort(reverse=True)

for k in ks:
    pair = nibeki(k)-k
    if k==pair:
        cntSet += c[k]//2

    elif c[k]>0 and c[pair]>0:
        COUNT = min(c[k], c[pair])
        c[k] -= COUNT
        c[pair] -= COUNT
        cntSet +=COUNT

print(cntSet)

Submission status: Accepted

Solution code:
from collections import Counter
N, *A = map(int, open(0).read().split())
A.sort(reverse=True)
C = Counter(A)
ans = 0
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = (2 ** (a.bit_length())) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N, *A = map(int, open(0).read().split())
A.sort(reverse=True)
C = Counter(A)
ans = 0
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = (1 << (a.bit_length())) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
def larger_nibeki(i):
    return 2 ** len(format(i, 'b'))
N = int(input())
A = sorted(map(int, input().split()), reverse=True)
C = defaultdict(int)
for a in A:
    C[a] += 1
ans = 0
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = larger_nibeki(a) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
def larger_nibeki(i):
    return 2 ** len(format(i, 'b'))
N, *A = map(int, open(0).read().split())
A.sort(reverse=True)
C = defaultdict(int)
for a in A:
    C[a] += 1
ans = 0
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = larger_nibeki(a) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import Counter
def larger_nibeki(i):
    return 2 ** int(math.log2(a) + 1)
N, *A = map(int, open(0).read().split())
A.sort(reverse=True)
ans = 0
C = Counter(A)
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = larger_nibeki(a) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)

Submission status: Accepted

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


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


N = int(fin())
A_list = [int(elem) for elem in fin().split()]
A_list.sort(reverse=True)
rest = Counter(A_list)
num_pairs = 0
for A in A_list:
    idx = bisect(possible_pows, A)
    complement = possible_pows[idx] - A
    if rest[complement] > 0:
        if complement == A and rest[A] >= 2:
            rest[complement] -= 1
            num_pairs += 1
        elif complement != A and rest[A] >= 1:
            rest[complement] -= 1
            num_pairs += 1
    rest[A] -= 1
print(num_pairs)

Submission status: Accepted

Solution code:
# https://beta.atcoder.jp/contests/agc029/submissions/3804087
from collections import Counter

N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
b = Counter(a)

ans = 0
for t in a:
    if b[t] == 0: continue
    s = (1 << t.bit_length()) - t
    if t == s:
        ans += b[t] // 2
        b[t] %= 2
    else:
        u = min(b[s], b[t])
        ans += u
        b[s] -= u
        b[t] -= u

print(ans)

Submission status: Accepted

Solution code:
# https://beta.atcoder.jp/contests/agc029/submissions/3804087
from collections import Counter

N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
b = Counter(a)

ans = 0
for t in a:
    s = (1 << t.bit_length()) - t
    if t == s:
        ans += b[t] // 2
        b[t] %= 2
    else:
        u = min(b[s], b[t])
        ans += u
        b[s] -= u
        b[t] -= u

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
pow2 = [2**i for i in range(1, 31)]
nums = []
counts = {}

for a in A:
	if a not in counts:
		nums.append(a)
		counts[a] = 0
	counts[a] += 1
nums.reverse()
ans = 0
for n in nums:
	if n not in counts:
		continue
	for p in pow2:
		if p > n and (p-n) in counts:
			if n == p - n:
				if counts[p-n] >= 2:
					ans += counts[p-n] // 2
					counts[p-n] = counts[p-n] % 2
			else:
				cnt = min(counts[p-n], counts[n])
				ans += cnt
				counts[p-n] -= cnt
				counts[n] -= cnt
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def ans_solve(N, As):
    C = Counter(As)
    ans = 0
    for d in reversed(sorted(As)):
        n = (2 ** d.bit_length()) - d
        if d != n:
            if C[d] > 0 and C.get(n, 0) > 0:
                C[d] -= 1
                C[n] -= 1
                ans += 1
        else:
            ans += C[d]//2
            C[d] = 0
    return ans
 
 
if __name__ == "__main__":
    N = input()
    As = [int(c) for c in input().split()]
    print(ans_solve(N, As))

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
ctr = Counter(A)
lctr = sorted(list(ctr.items()),reverse=True)

ans = 0
for k,_ in lctr:
    beki = 2**(len(bin(k))-2)
    a = beki-k
    if a == k:
        ans += ctr[k]//2
    else:
        tmp = min(ctr[k], ctr[a])
        ans += tmp
        ctr[a] -= tmp
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
D = {}
for i in A :
    if i in D :
        D[i] += 1
    else :
        D[i] = 1

ans = 0
A = sorted(A,reverse=True)
for i in A :
    r = 2**math.ceil(math.log2(i))
    if i == r :
        ans += (D[i] // 2)
        D[i] = 0
    else :
        b = r-i
        if D[i] > 0 and D.get(b,0) > 0 :
            D[i] -= 1
            D[b] -= 1
            ans += 1
print(ans)

Submission status: Accepted

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

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


def solve(count):
    ret = 0
    for a in sorted(count, reverse=True):
        cnt = count[a]
        if cnt <= 0:
            continue
        maxn = 1 << a.bit_length()
        b = maxn - a
        if b in count and count[b] > 0:
            if a == b:
                c = cnt // 2
            else:
                c = min(cnt, count[b])
                count[b] -= c
            ret += c
    return ret


count_even = collections.defaultdict(lambda: 0)
count_odd = collections.defaultdict(lambda: 0)

for a in A:
    if a % 2 == 0:
        count_even[a] += 1
    else:
        count_odd[a] += 1

print(solve(count_even) + solve(count_odd))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
 
N = int(input())
A = [int(a) for a in input().split()]
A = sorted(A)
 
c = 0
for i in range(N - 1 , -1, -1):
    if A[i] == int(A[i]):
        b = 1
        while b <= A[i]:
            b <<= 1
 
        j = bisect.bisect_left(A, b - A[i])
        if i > j:
            if b - A[i] == A[j]:
                c += 1
                A[j] = A[j] - 0.5
                A[i] = A[i] + 0.5
print(c)

Submission status: Accepted

Solution code:
from collections import defaultdict
import os, sys
if os.environ.get("USER") == "hoge":
    def debug(*args): print(*args, file=sys.stderr)
else:
    def debug(*args): pass
def debug(*args): pass
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:
    debug(A)
    #print(x)
    if dd.get(x,-1)==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
        #print((1<<s)-x)
        t=dd.get((1<<s)-x,-1)
        if t>=1:
            ans+=1
            dd[x]-=1
            dd[(1<<s)-x]-=1
            #print(ans)
            #print(dd)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import os, sys
# def debug(*args): print(*args, file=sys.stderr)# os.environ.get("USER")
# def debug(*args): os.environ.get("USER")
def debug(*args): pass
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:
    debug(A)
    #print(x)
    if dd.get(x,-1)==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
        #print((1<<s)-x)
        t=dd.get((1<<s)-x,-1)
        if t>=1:
            ans+=1
            dd[x]-=1
            dd[(1<<s)-x]-=1
            #print(ans)
            #print(dd)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def larger_nibeki(i):
    return 2 ** len(format(i, 'b'))
N, *A = map(int, open(0).read().split())
A.sort(reverse=True)
ans = 0
C = Counter(A)
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = larger_nibeki(a) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def debug(*args): print(*args, file=sys.stderr)
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,-1)==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
        #print((1<<s)-x)
        t=dd.get((1<<s)-x,-1)
        if t>=1:
            ans+=1
            dd[x]-=1
            dd[(1<<s)-x]-=1
            #print(ans)
            #print(dd)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def larger_nibeki(i):
    return 2 ** len(format(i, 'b'))
N, *A = map(int, open(0).read().split())
A.sort(reverse=True)
ans = 0
C = Counter(A)
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    if C[larger_nibeki(a) - a] > 0:
        ans += 1
        C[larger_nibeki(a) - a] -= 1
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import Counter


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

n_pears = 0
counter = Counter(A)

for i in reversed(range(0, len(A))):
    if counter[A[i]] <= 0:
        continue
    counter[A[i]] -= 1
    Aj = 2 ** int(math.log2(A[i]) + 1) - A[i]
    if counter[Aj] > 0:
        n_pears += 1
        counter[Aj] -= 1

print(n_pears)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, os
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): pass # if os.environ.get("USER")=="shun" else None
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 > max_a:
        break
    m += 1
used = [False] * n


def bisect(val, start, end):
    debug(used)
    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, start, mid)
            return res
        else:
            res = bisect(val, mid+1, end)
            if res is not None:
                return res
            used[mid] = True
            return mid
        # 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
        #     debug("fuga", used)
        #     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):
    # 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)):
    if used[j]:
        continue
    b = a[j]
    used[j] = True
    res = find(b, j)
    if res:
        ans += 1


print(ans)

Submission status: Accepted

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

xs = sorted(A, reverse=True)

cs = {}

for x in xs:
    cs[x] = cs.get(x, 0) + 1

result = 0

for x in xs:
    if cs[x]:
        for i in range(31, 0, - 1):
            m = 2**i
            y = m - x
            if y > x or y < 1:
                continue
            if y in cs:
                if x == y:
                    if cs[y] >= 2:
                        cs[y] -= 2
                        result += 1
                        break
                else:
                    if cs[y] >= 1:
                        cs[x] -= 1
                        cs[y] -= 1
                        result += 1
                        break

#print(cs)
print(result)

Submission status: Accepted

Solution code:
from bisect import bisect
N = int(input())
*A, = map(int, input().split())
B = {}
for a in A:
    B[a] = B.get(a, 0) + 1
R = sorted(B.items())
C = []; D = []
for k, v in sorted(B.items()):
    C.append(k)
    D.append(v)
M = len(C)
j = 0
ans = 0
for i in range(M-1, -1, -1):
    if D[i] == 0:
        continue
    a = C[i]
    b = 2**a.bit_length()
    j = bisect(C, b-a-1)
    if j < M and C[j] == b-a:
        if i == j:
            c = D[i]//2
        else:
            c = min(D[i], D[j])
        ans += c
        D[i] -= c; D[j] -= c
print(ans)

Submission status: Accepted

Solution code:
input()
a=sorted(map(int,input().split()))[::-1]
s={}
l=[2**-~i for i in range(31)[::-1]]
r=0
for v in a:
	for j in l:
		p=j-v
		if p in s and s[p]>0:r+=1;s[p]-=1;break
	else:s[v]=s.get(v,0)+1
print(r)

Submission status: Accepted

Solution code:
import sys
import socket
from collections import Counter

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('b1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    res = 0
    n = read_int()
    a = read_int_list()
    a.sort()
    c = Counter(a)
    for i in range(n - 1, -1, -1):
        if c[a[i]] <= 0:
            continue
        c[a[i]] -= 1
        p = 1
        while not p <= a[i] < 2 * p:
            p *= 2
        comp = 2 * p - a[i]
        if c[comp] > 0:
            c[comp] -= 1
            res += 1
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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


def solve(count):
    ans = 0
    for a in sorted(count, reverse=True):
        cnt = count[a]
        if cnt <= 0:
            continue
        ma = 1 << (a.bit_length())
        b = ma - a
        if b in count and count[b] > 0:
            if a == b:
                pair = cnt // 2
            else:
                pair = min(cnt, count[b])
                count[b] -= pair
            ans += pair
    return ans


count_e = defaultdict(lambda: 0)
count_o = defaultdict(lambda: 0)
for a in aaa:
    if a % 2 == 0:
        count_e[a] += 1
    else:
        count_o[a] += 1

print(solve(count_e) + solve(count_o))

Submission status: Accepted

Solution code:
import math,collections
n=int(input())
a=sorted(map(int,input().split()))[::-1]
s=collections.Counter(a)
r=0
f=0
for i,v in enumerate(a):
	p=2**math.ceil(math.log2(v))-v
	if f:f=0
	elif s[v]==0:pass
	elif p in s.keys()and s[p]>0:s[v]-=1;s[p]-=1;r+=1
	elif i<n-1 and p==0 and v==a[i+1]and s[v]>1:s[v]-=2;r+=1;f=1
print(r)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect, bisect_left
from collections import defaultdict

def inpl(): return list(map(int, input().split()))
N = int(input())
A = sorted(inpl())
beki = [2**i for i in range(1, 31)]
D = defaultdict(list)


for i, a in enumerate(A):
    D[a].append(i)

answer = 0
matched = [0]*(N)

for t in range(31, 0, -1):
    S = 2 ** (t)
    R = bisect_left(A, S) - 1
    for i in range(R, 0, -1):
        if A[i] + A[i-1] < S:
            break
        if matched[i]:
            continue
        X = S - A[i]
        if len(D[X]) >= 1 + (X == A[i]):
            a = D[A[i]].pop()
            b = D[X].pop()
            assert a == i
            matched[a] = 1
            matched[b] = 1
            answer += 1
print(answer)

Submission status: Accepted

Solution code:
import math,collections
n=int(input())
a=sorted(map(int,input().split()))[::-1]
s=collections.Counter(a)
r=0
f=0
for i,v in enumerate(a):
	if f:f=0;continue
	if s[v]==0:continue
	p=2**math.ceil(math.log2(v))-v
	if p in s.keys() and s[p]>0:s[v]-=1;s[p]-=1;r+=1;continue
	if i<n-1 and p==0 and a[i+1]==v and s[v]>=2:s[v]-=2;r+=1;f=1
print(r)

Submission status: Accepted

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

def is_in(t, n):
    i = key.setdefault(t, bisect.bisect_left(A, t))
    if i >= n:
        return -1

    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            key[t] = i
            return i
        i += 1

    return -1

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

    a = A[n]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        i = is_in(t - a, n)
        if i != -1:
            res += 1
            break
        t >>= 1

print(res)
print("")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(31)]
A.sort()
already = set()


def to_dic(A):
    d = {}
    for a in A:
        d[a] = d.setdefault(a, 0) + 1

    return d

def is_in(t, num):
    i = D.setdefault(t, 0)
    if i == 0:
        return 0
    s = min(i, num)
    D[t] -= s
    return s


res = 0
D = to_dic(A)
A2 = list(D.keys())
A2.sort()

for n in range(len(A2) - 1, -1, -1):
    a = A2[n]

    if a in T:
        res += D[a] // 2
        D[a] = 0

        if D[a] % 2 == 0:
            continue

    num = D[a]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        s = is_in(t - a, num)
        res += s
        num -= s
        if num == 0:
            break

        t >>= 1

print(res)

Submission status: Accepted

Solution code:
N=int(input())
A=sorted([int(i) for i in input().split()],reverse=True)
B=[2**(len(bin(i))-2) for i in A]
D=dict()
for i in range(N):
    if not(A[i] in D):
        D[A[i]]=1
    else:
        D[A[i]]+=1
ans=0
for i in range(N):
    if D[A[i]]<=0:
        continue
    if B[i]==2*A[i]:
        if D[A[i]]>=2:
            D[A[i]]-=2
            ans+=1
    else:
        if (B[i]-A[i]) in D:
            if D[B[i]-A[i]]!=0:
                D[A[i]]-=1
                D[B[i]-A[i]]-=1
                ans+=1
print(ans)