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 bisect
ans = 0
N = int(input())
a = list(map(int,input().split()))
b = [True for _ in range(N)]
c = [True for _ in range(N)]
a.sort()
digit = 40
y = 2 ** (digit+1) -1
while len(a)>1:
    if b[-1]==False:
        a.pop(-1)
        b.pop(-1)
        continue
    x = a.pop(-1)
    b.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>0:
        rr -= 1
        if b[ll]==False:
            pass
        elif b[rr]==True:
            b[rr]=False
            ans += 1
        else:
            lll = ll
            rrr = rr
            while rrr-lll>1:
                if b[(rrr+lll)//2]:
                    lll = (rrr+lll)//2
                else:
                    rrr = (rrr+lll)//2
            b[lll] = False
            ans += 1           
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
T=[2**i for i in range(1,35)]
table=[True]*N
A.sort()
ans=0
for t in T[::-1]:
  l,r=0,N-1
  while l<r:
    if A[l]+A[r]>t:
      r-=1
    elif A[l]+A[r]==t:
      if table[l] and table[r]:
        ans+=1
        table[l],table[r]=False,False
      if not table[l]:
        l+=1
      if not table[r]:
        r-=1
    elif A[l]+A[r]<t:
      l+=1
print(ans)

Submission status: Accepted

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


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

    dic = {}
    for i in a:
        dic[i] = dic.get(i, 0) + 1

    a.sort(reverse=True)

    ans = 0
    for i in a:
        if i not in dic:
            continue
        dic[i] -= 1
        if not dic[i]:
            del dic[i]

        j, cnt = i, 1
        while j:
            j >>= 1
            cnt *= 2

        num = cnt - i
        if num in dic:
            dic[num] -= 1
            ans += 1
            if not dic[num]:
                del dic[num]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

"""
agc 029 B
"""

from collections import Counter

nn = 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


ii = 0
m = ali[ii]
while bool(c):
    while c[ali[ii]] == 0:
        ii += 1
    m = ali[ii]
    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

print(ans)

Submission status: Accepted

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):
  eraserlist=[]
  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*2
      else:
        dec=min(Acounter[number],Acounter[limit-number])
        Acounter[number]-=dec
        Acounter[limit-number]-=dec
        if Acounter[limit-number]==0:
          eraserlist.append(limit-number)
      if Acounter[number]==0:
        eraserlist.append(number)
      answer+=dec
    if number>=limit/2:
      eraserlist.append(number)
  for i in range(len(eraserlist)):
    if eraserlist[i] in Acounter.keys():
      Acounter.pop(eraserlist[i])
  limit=int(limit/2)
print(answer)
#print(Acounter)

Submission status: Accepted

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 > 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, 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):
    "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)):
    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:
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:
    if dp[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: Accepted

Solution code:
# from math import log2
from math import log
from bisect import bisect_left


def log2(x):
    return log(x, 2)


def getComp(n):
    return (1 << (1 + int(log2(n)))) - n


N = int(input())
A = [int(s) for s in input().split()]
A.sort()
B = []
C = []
i = 0
while i < len(A):
    j = i
    count = 1
    while i+1 < len(A) and A[j] == A[i+1]:
        count += 1
        i += 1
    B.append(A[j])
    C.append(count)
    i += 1

count = 0
i = len(B) - 1
while i >= 0:
    comp = getComp(B[i])
    j = bisect_left(B, comp)
    if i == j and C[i] < 2:
        i -= 1
        continue
    if B[j] != comp:
        i -= 1
        continue
    if not C[i] or not C[j]:
        i -= 1
        continue
    C[i] -= 1
    C[j] -= 1
    count += 1

print(count)

Submission status: Accepted

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

from collections import Counter
counter=Counter(A)

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

L=len(LIST)

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

print(ANS)

Submission status: Accepted

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

import bisect
import collections

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

checked=collections.Counter(a)

ans=0

while(a):
    c=a.pop()
    if checked[c]==0:
        continue
    checked[c]-=1
    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[x]>0:
        ans += 1
        checked[x]-=1
        
#    print(checked)
#        print(checked)
#        print(a[i],c,"xxx")




print(ans)

Submission status: Accepted

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,-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:
import math
import collections
n=int(input())
a=sorted(map(int,input().split()))[::-1]
s=collections.Counter(a)
r=0
flag=False
for i in range(n):
    #print(i,a[i])
    if flag:
        flag=False
        continue
    if s[a[i]]==0: continue
    pair = 2**math.ceil(math.log2(a[i]))-a[i]
    #print("pair",pair)
    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: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse = True)
d = {} # d[i] = number of i
ans = 0
for i in A:
	for j in range(31, 0, -1):
		x = 2 ** j - i
		if x in d and d[x] > 0:
			ans = ans + 1
			d[x] -= 1
			break
	else:
		d[i] = d.get(i, 0) + 1
print(ans)

Submission status: Accepted

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 t != A[i]:
            if d[t]>0 and d[A[i]]>0:
                ans2 += 1
                d[t] -= 1
                d[A[i]] -= 1
        else:
            if d[t] > 1:
                ans2 += 1
                d[t] -= 2


print(ans1+ans2)

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
from collections import Counter
n = int(input())
cnt = Counter(list(map(int, input().split())))
keys = sorted(cnt.keys(), reverse=True)
bs = [2 ** i for i in range(32)]
ans = 0
for k in keys:
  if k in bs:
    while cnt[k] >= 2:
      cnt[k] -= 2
      ans += 1
    continue
  to = bs[br(bs, k)] - k
  while cnt[k] > 0:
    if to in cnt and cnt[to]:
      ans += 1
      cnt[to] -= 1
      cnt[k] -= 1
    else:
      break
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    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: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
a.sort(key=lambda x:-x)
d = defaultdict(int)
for i in a:
    d[i] += 1
beki = [2**i for i in range(32,0,-1)]
ans = 0
for i in a:
    if d[i] == 0:
        continue
    for j in beki:
        if j <= i:
            break
        ni = j - i
        if ni == i:
            if d[i] >= 2:
                ans +=1
                d[i]-=2
                break
        elif d[ni] > 0:
            ans += 1
            d[ni]-=1
            d[i]-=1
            break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N, = map(int, raw_input().split())
A = map(int, raw_input().split())
c = Counter(A)
ks = c.keys()
ks.sort()
r = 0
for i in ks[::-1]:
  for j in xrange(60):
    p = 1<<j
    if i<=p:
      break
  if p==i:
    r += c[i]//2
  else:
    q = p-i
    x = min(c[i], c[q])
    r += x
    c[i] -= x
    c[q] -= x
print r

Submission status: Accepted

Solution code:
import bisect

import collections


n = int(input())
a = list(map(int, input().split()))
a_counter = collections.Counter(a)
a_keys = sorted(a_counter.keys(), reverse=True)

targets = []

t = 0
vt = 1
for v in a:
    while v >= vt:
        t += 1
        vt *= 2
        targets.append(vt)
targets.reverse()


cnt = 0
for key in a_keys:
    if a_counter[key] <= 0:
        continue
    for t in targets:
        if key >= t:
            break
        if key == t-key:
            p = max(0, min(a_counter[key], a_counter[t-key])) // 2
        else:
            p = max(0, min(a_counter[key], a_counter[t-key]))
        a_counter[key] -= p
        a_counter[t-key] -= p
        cnt += p
print(cnt)

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:
# B
import math

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

A_dict = dict()
for a in A_list:
    if a in A_dict.keys():
        A_dict[a] += 1
    else:
        A_dict[a] = 1

res = 0
A_list_ = list(reversed(sorted(A_list)))
for a in A_list_:
    # partner
    r = 2**math.ceil(math.log2(a))
    if a == r:
        res += A_dict[a] // 2
        A_dict[a] = 0
    else:
        b = r - a
        if A_dict[a] > 0 and A_dict.get(b, 0) > 0:
            A_dict[a] -= 1
            A_dict[b] -= 1
            res += 1
print(res)

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:
            ans += D[i]//2
            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:
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)

#print(larger_nibeki(n))
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 collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
zp = []
for i in range(1, 31):
    zp.append(2**i)

dprint(zp)
    
N, = getIntList()
#print(N)

za = getIntList()

tc = collections.Counter(za)
za.sort(reverse = True)

r = 0
for x in za:
    if tc[x]==0: continue
    tc[x] -= 1
    for y in zp:
        if y<= x: continue
        g = y - x
        if g> x:
            break
        if tc[g] >0:
            r +=1
            tc[g] -=1
print(r)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
A.sort()
d = defaultdict(int)
for a in A:
    d[a] += 1
ans = 0

for i in range(N-1, -1, -1):
    a = A[i]
    if d[a] == 0:
        continue
    s = 2**(len(bin(a))-2)
    p = s-a
    if (d[p] > 0 and p!=a) or d[p]>1:
        ans += 1
        d[p] -= 1
        d[a] -= 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def adj(v):
    t = 1
    while t <= 2*10**9:
        if t > v:
            yield t-v
        t *= 2

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

cnt = defaultdict(int)
for a in A:
    cnt[a] += 1

degree = defaultdict(int)
for v in cnt.keys():
    for u in adj(v):
        if u == v:
            degree[v] += int(cnt.get(u,0) >= 2)
        else:
            degree[v] += int(cnt.get(u,0) >= 1)

stack = [v for v,c in degree.items() if c == 1]
res = 0
while stack:
    v = stack.pop()
    c = cnt.get(v,0)
    if c == 0:
        continue
    for u in adj(v):
        if u == v and cnt.get(u,0) >= 2:
            break
        elif cnt.get(u,0) >= 1:
            break
    res += 1
    del cnt[u]
    degree[u] -= 1
    if degree[u] == 1:
        stack.append(u)

print(res)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
from collections import Counter as co
D=co(A)

cnt=0
for i in range(N):
  if D[A[-1-i]]>0:
    D[A[-1-i]]-=1
    for j in range(1,16):
      d=2**j
      if A[-1-i]<d:
        e=d-A[-1-i]
        break
    if e in D:
      if D[e]>0:
        cnt+=1
        D[e]-=1
print(cnt)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
from collections import Counter as co
D=co(A)

cnt=0
for i in range(N):
  if D[A[-1-i]]>0:
    D[A[-1-i]]-=1
    for j in range(1,16):
      d=2**j
      if A[-1-i]<d:
        e=d-A[-1-i]
        break
    if e in D:
      cnt+=1
      D[e]-=1
print(cnt)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
from collections import Counter as co
D=co(A)

cnt=0
for i in range(N):
  if D[A[-1-i]]>0:
    D[A[-1-i]]-=1
    for j in range(1,16):
      d=2**j
      if A[-1-i]<d:
        e=d-A[-1-i]
        break
    if D[e]>0:
      cnt+=1
      D[e]-=1
print(cnt)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
from collections import Counter as co
D=co(A)

cnt=0
for i in range(N):
  if D[A[-1-i]]>0:
    for j in range(1,16):
      d=2**j
      if A[-1-i]<d:
        e=d-A[-1-i]
        break
    if D[e]>0:
      cnt+=1
      D[A[-1-i]]-=1
      D[e]-=1
print(cnt)

Submission status: Runtime Error

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
class UnionFind(): #集合の取り扱い、辺に重み、階層を意識するときは使えない
    def __init__(self,n):
        self.n=n
        self.par = [-1]*n
    def find(self,x):
        if self.par[x] <0: #負なら親、要素数
            return x
        else: #正なら親の番号
            self.par[x]=self.find(self.par[x]) #一回調べたら根を繋ぎ変える、経路圧縮
            return self.par[x]
    def union(self,x,y):
        x=self.find(x) #x,yの親
        y=self.find(y)

        if x==y: #親が同じなら何もしない
            return 
        if self.par[x]>self.par[y]: #要素数が大きい方をxにする
            x,y=y,x
        self.par[x]+=self.par[y] #xがある集合にyが入った集合をくっつける
        self.par[y]=x

    def size(self,x):
        return -self.par[self.find(x)] #親のサイズ
    
    def same(self,x,y): #親が同じ、すなわち同じ集合か
        return self.find(x)==self.find(y)

    def member(self,x): #同じ木（集合）にある要素全部リストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root ]
    
    def roots(self): #集合の根になってる要素をリストで返す
        return [i for i , x in enumerate(self.par) if x<0]
    
    def group_count(self): #集合の数、木の数
        return len(self.roots())

    def all_member(self): #辞書型で返す
        return {r: self.member(r) for r in self.roots()}
    def __str__(self):
        return "\n".join('{}:{}'.format(r,self.member(r)) for r in self.roots)

n,m=map(int,input().split())
p=list(map(int,input().split()))
tree=UnionFind(n)
for i in range(m):
  x,y=map(int,input().split())
  tree.union(x-1,y-1)
ans=0
for i in range(n):
  if tree.same(p[i]-1,i):
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
cnt=0
maxa=max(a)
while 2**cnt<2*maxa:
    cnt+=1
    # print(2**cnt)

lsta=[0]*n
for i in range(1,cnt+1)[::-1]:
    dic=defaultdict(list)
    for j in range(n):
        if 2**i>a[j] and lsta[j]==0:
            if dic[a[j]]!=[]:
                lsta[j]=-1
                lsta[dic[a[j]].pop()]=-1
            else:
                dic[2**i-a[j]].append(j)
    # print(dic)
# print(lsta)
ans=-sum(lsta)//2
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def twosum(n):
  now = 1
  while n >= now:
    now *= 2
  return now - n
n=int(input())
a=sorted(list(map(int,input().split())))
d = defaultdict(int)
for i in a:
    d[i] += 1
ans = 0
for i in a[::-1]:
    d[i] -= 1:
    find = twosum(i)
    if d[find] > 0 and d[i] >= 0:
        ans += 1
        d[find] -= 1
    else:
        d[i] += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import heapq
import bisect

n = ni()
a = na()
ls = []
nibeki = [2**i for i in range(1,31)]

for i in a:
    heapq.heappush(ls,-i)

s = {}
ans = 0

for _ in range(n):
    m = -heapq.heappop(ls)
    if m in s and s[m] > 0:
        s[m] -= 1
        ans += 1
        continue
    b = bisect.bisect_right(nibeki,m)
    dif = 0 if b > 0 and nibeki[b-1] == m else nibeki[b]-m
    if m in s:
        s[dif] += 1
    else:
        s[dif] = 1

print(ans)

Submission status: Runtime Error

Solution code:
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

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

    ans = 0
    c = Counter(A)
    B = sorted(c.keys(), reverse=True)

    for b in B:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            if a in C:
                cur = min(c[a], c[b])
            else:
                cur = 0
        ans += cur
        # c[b] -= cur
        c[a] -= cur

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from collections import Counter
    from bisect import bisect
    import sys
    input = sys.stdin.buffer.readline

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

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)
    bi = [2**i for i in range(1, 15)]

    for b in A:
        a = (bi[bisect(bi, b)]) - b
        if a == b:
            ans += c[b]//2
            c[b] %= 2
        else:
            if a in c.keys():
                cur = min(c[a], c[b])
                ans += cur
                c[b] -= cur
                c[a] -= cur
        # print(a, b, c, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, *A = map(int, open('0').read().split())
ans = 0
A.sort()
dic = defaultdict(list)
for i, a in enumerate(A):
  dic[a] += [i]
for i in range(N-1,-1,-1):
  a = A[i]
  if dic[a]==[]:
    continue
  dic[a].pop()
  k = 1
  while k<=a:
    k *= 2
  n = k-a
  if dic[n]!=[]:
    dic[n].pop()
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
N, *A = map(int, open(0).read().split())
ans = 0
A.sort()
used = [False]*N
for i in range(N-1,-1,-1):
  if used[i]:
    continue
  a = A[i]
  k = 1
  while k<=a:
    k *= 2
  n = k-a
  ind  = bisect_left(A,n)
  while A[ind]==n:
    if not used[ind] and ind!=i:
      break
    ind += 1
  else:
    continue
  ans += 1
  used[ind] = True
  used[i] = True
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import *
import copy
from collections import *


N=int(input())
A=list(map(int,input().split()))
idle_max=10**9
peki2=[]
for i in range(1,100):
    a=2**i
    if a<=2*idle_max:
        peki2.append(a)
peki2.sort(reverse=True)
lst=[[],[]]
for a in A:
    if a%2:
        lst[1].append(a)
    else:
        lst[0].append(a)

lst[0].sort(reverse=True)
lst[1].sort(reverse=True)
setlst=[set(lst[0]),set(lst[1])]
Counerlst=[Counter(lst[0]),Counter(lst[1])]

count=0
for l in range(2):
    for n in lst[l]:
        if n in setlst[l]:
            for p in peki2:
                a=p-n
                if a in setlst[l]:
                    count+=1
                    Counerlst[l][a]-=1
                    Counerlst[l][n]-=1
                    if Counerlst[l][a]==0:
                        setlst[l].remove(a)
                    if Counerlst[l][n]==0:
                        setlst[l].remove(n)
                    break
print(count)

Submission status: Runtime Error

Solution code:
    N=int(input())
    lis=list(map(int,input().split()))
    lis.sort()
    sum=0
    while(len(lis)>1):
        v=lis.pop()
        k=1
        while k<=v:
            k*=2
        m=k-v
        if m in lis:
            sum+=1
            lis.remove(m)

    print(sum)

Submission status: Runtime Error

Solution code:
N=int(input())
    lis=list(map(int,input().split()))
    lis.sort(reverse=True)
    dis={}
    for x in lis:
        if x in dis.keys():
            dis[x]=dis[x]+1
        else:
            dis[x]=1
    lis=[]
    sum=0
    for key,value in dis.items():
        if value<=0:
            continue
        else:
            x = 1
            while (x<=key):
                x*=2
            another = x-key
            if another in dis.keys() and dis[another]>0:
                if another==key:
                    sum+=value//2
                else:
                    m=min(dis[another],value)
                    dis[another]-=m
                    sum+=m
            dis[key]=0
    print(sum)

Submission status: Runtime Error

Solution code:


import  math
N=int(input())
lis=list(map(int,input().split()))
lis.sort(reverse=True)
dis={}
for x in lis:
    if x in dis.keys():
        dis[x]=dis[x]+1
    else:
        dis[x]=1
lis=[]
sum=0
for i in range(1,27):
    lis.append(pow(2,i))
for key,value in dis.items():
    dis[key]=0
    if value!=0:
       k = 0
       while (lis[k] <= key):
           k += 1
       another = lis[k] - key
       if another in dis.keys():
           if another==key:
               sum+=value//2
           else:
               m=min(dis[another],value)
               dis[another]-=m
               sum+=m
               dis[key]=0
print(sum)

Submission status: Runtime Error

Solution code:
import  math
N=int(input())
lis=list(map(int,input().split()))
lis.sort(reverse=True)
dis={}
for x in lis:
    if x in dis.keys():
        dis[x]=dis[x]+1
    else:
        dis[x]=1
lis=[]
sum=0
for i in range(1,27):
    lis.append(pow(2,i))
#print(dis)
for key,value in dis.items():
    dis[key]=0
    if value!=0:
#       print("first=",key,value)
        k = 0
        while (lis[k] <= key):
            k += 1
        another = lis[k] - key
#        print("second=",another,dis[another])
        if another in dis.keys():
            if another==key:
                sum+=value//2
            else:
                m=min(dis[another],value)
                dis[another]-=m
#                print("*",m)
                sum+=m
        dis[key]=0
#    print(dis)
print(sum)

Submission status: Runtime Error

Solution code:
import  math
N=int(input())
lis=list(map(int,input().split()))
lis.sort(reverse=True)
dis={}
for x in lis:
    if x in dis.keys():
        dis[x]=dis[x]+1
    else:
        dis[x]=1
lis=[]
sum=0
for i in range(1,27):
    lis.append(pow(2,i))
#print(dis)
for key,value in dis.items():
    dis[key]=0
    if value!=0:
#       print("first=",key,value)
        k = 0
        while (lis[k] <= key):
            k += 1
        another = lis[k] - key
#        print("second=",another,dis[another])
        if another in dis.keys():
            if another==key:
                sum+=value//2
            else:
                m=min(dis[another],value)
                dis[another]-=m
#                print("*",m)
                sum+=m
        #dis[key]=0
#    print(dis)
print(sum)