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: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)

t.reverse()
a.sort(reverse=True)

sum = 0
i = 0

#print(t,a)

while True:
    
    for j in range(i+1,len(a)):
        if a[j] == t[i] :
            sum += 1
            a.pop(j)

    i = i + 1
    if i >= len(a)-1:
        break

print(sum)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)

t.reverse()
a.sort(reverse=True)

sum = 0
i = 0

#print(t,a)

while True:
    
    first = i+1
    last = len(a)-1
    found = False

    while first<=last and not found:
        midpoint = (first + last)//2
        if a[midpoint] == t[i] :
            found = True
            sum += 1
            a.pop(midpoint)
            #print(a)
        else:
            if t[i] > a[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
            
    i = i + 1
    if i >= len(a)-1:
        break

print(sum)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)

t.reverse()
a.sort(reverse=True)

sum = 0
i = 0

#print(t,a)

while True:
    
    first = i+1
    last = len(a)-1
    found = False

    while first<=last and not found:
        midpoint = (first + last)//2
        if a[midpoint] == t[i] :
            found = True
            sum += 1
            a = a[:midpoint]
            a.extend(a[midpoint:])
            #print(a)
        else:
            if t[i] > a[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
            
    i = i + 1
    if i >= len(a)-1:
        break

print(sum)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [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]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)

t.reverse()
a.sort(reverse=True)

sum = 0
i = 0

#print(t,a)

while True:
    
    first = i+1
    last = len(a)-1
    found = False

    while first<=last and not found:
        midpoint = (first + last)//2
        if a[midpoint] == t[i] :
            found = True
            sum += 1
            a = a[:midpoint]
            a.extend(a[midpoint:])
            print(a)
        else:
            if t[i] > a[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
            
    i = i + 1
    if i >= len(a)-1:
        break

print(sum)

Submission status: Runtime Error

Solution code:
# coding:utf-8

import bisect

INF = float('inf')
MOD = 10 ** 9 + 7


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


def solve(num_cnt: list) -> int:
    num_cnt.sort()
    t = 2 ** (len(bin(num_cnt[-1])) - 2)
    used = [False] * len(num_cnt)
    cnt = 0
    for i in range(len(num_cnt))[::-1]:
        if used[i]:
            continue
        n = num_cnt[i]
        used[i] = True
        while 2 * n < t:
            t //= 2
        j = bisect.bisect_left(num_cnt, t - n)
        # print(n, t, j)
        if t - n == num_cnt[j] and n != t - n:
            cnt += 1
            used[j] = True

    return cnt


N = int(input())
A = inpl()

cnt_e, cnt_o = [], []
for a in A:
    if a % 2:
        cnt_o.append(a)
    else:
        cnt_e.append(a)

print(solve(cnt_e) + solve(cnt_o))

Submission status: Runtime Error

Solution code:
import math

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

count = 0



while(a!=[]):
    temp = a[-1]
    a.pop(-1)
    b=2**math.floor(math.log2(temp))
    if a ==[]:
        break
    if 2*b-temp > 0:
        count += 1
        a.pop(a.index(2*b-temp))
    
print(count)

Submission status: Runtime Error

Solution code:
def ans_solve(N, As):
    C = Counter(As)
    ans = 0
    for d in 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: Runtime Error

Solution code:
N = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 0
for i in range(30,-1,-1):
  c = []
  b = 2**i
  y = a.count(b)
  ans += (y//2)
  for j in range(len(a)):
    if a[j]>b:
      if a[j]-b in a:
        ans += 1
        c.append(j)
        c.append(a.index(a[j]-b))
  c.sort()
  d = reversed(c)
  for k in d:
    a.pop(k)
  for l in range(y):
    a.remove(b)
print(ans)

Submission status: Runtime Error

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:
    debug(*args)
    #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: Runtime Error

Solution code:
from collections import defaultdict
import os
def debug(*args): print(*args, file=sys.stderr)# os.environ.get("USER")
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: Runtime Error

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

b = [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]

sum = 0
i = 0
while True:

    t = 0
    for bb in b :
        if bb > a[i]:
            t = bb - a[i]
            break
    #print(t)
    
    for j in range(i,len(a)):
        if a[j] == t:
            sum += 1
            a = a[:j]
            a.extend(a[j+1:])
            #print(a)

    i = i + 1
    if i >= len(a)-1:
        break

print(sum)

Submission status: Runtime Error

Solution code:
import numpy as np


N=int(input())
A = list(map(int,input().split()))
 
A.sort()
 
A=A[::-1]

d = {A[0]:1}
prev=A[0]
for i in range(N):
    if A[i]!=prev:
        d[A[i]]==1
    else:
        d[A[i]]+=1
    prev = A[i]

count=0

for i in range(N):
    d[A[i]]-=1
    want=2**(int(np.log2(A[i]))+1) - A[i]
    if want in d.keys():
        if d[want]>=0:
            d[want]-=1
            count+=1
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
A = list(map(int,input().split()))
 
A.sort()
 
A=A[::-1]

d = {A[0]:1}
prev=A[0]
for i in range(N):
    if A[i]!=prev:
        d[A[i]]==1
    else:
        d[A[i]]+=1

count=0

for i in range(N):
    d[A[i]]-=1
    want=2**(int(np.log2(A[i]))+1) - A[i]
    if want in d.keys():
        if d[want]>=0:
            d[want]-=1
            count+=1
print(count)

Submission status: Runtime Error

Solution code:

N=int(input())
A = list(map(int,input().split()))
 
A.sort()
 
A=A[::-1]

d = {A[0]:1}
prev=A[0]
for i in range(N):
    if A[i]!=prev:
        d[A[i]]==1
    else:
        d[A[i]]+=1

count=0

for i in range(N):
    d[A[i]]-=1
    want=2**(int(np.log2(A[i]))+1) - A[i]
    if want in d.keys():
        if d[want]>=0:
            d[want]-=1
            count+=1
print(count)

Submission status: Runtime Error

Solution code:

N=int(input())
A = list(map(int,input().split()))
 
A.sort()
 
A=A[::-1]

d = {A[0]:1}
prev=A[0]
for i in range(N):
    if A[i]!=prev:
        d[A[i]]==1
    else:
        d[A[i]]+=1

count=0

for i in range(N):
    d[A[i]]-=1
    want=2**(int(np.log2(A[i]))+1) - A[i]
    if d[want]>0:
        d[want]-=1
        count+=1
print(count)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        if "1" not in bin(t)[3:]:
            ans+=1
print(len(ans))

Submission status: Runtime Error

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
Ae=[]
Ao=[]
for i in range(N):
    if A[i]%2==0:
        Ae.append(A[i])
    else:
        Ao.append(A[i])
if Ao!=[]:
    s=0
    Ao.sort()
    i=1
    while i<=len(Ao):
        a=int(math.log2(Ao[-i]))
        if 2**(a+1)-Ao[-i] in Ao[:-i]:
            s+=1
            Ao.remove(2**(a+1)-Ao[-i])
            i+=1
        else:
            i+=1
else:
    s=0
if Ae!=[]:
    t=0
    j=1
    Ae.sort()
    while j<=len(Ae):
        b=int(math.log2(Ae[-j]))
        if 2**(a+1)-Ae[-j] in Ae[:-j]:
            s+=1
            Ae.remove(2**(a+1)-Ae[-j])
            j+=1
        else:
            j+=1
else:
    t=0
print(s+t)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
for i in range(n-1):
    for j in range(i+1,n):
        if "1" not in bin(t)[3:]:
            ans+=1
print(len(ans))

Submission status: Runtime Error

Solution code:
_ = input()
s = input()
data = list(map(int, s.split()))

even = []
odd = []
for it in data:
    if it%2 == 0:
        even.append(it)
    else:
        odd.append(it)

# src is sorted
def get_pair(src, target):
    pair = []
    pair_id = []
    for i, first in enumerate(src):
        if first > target:
            break
        for j, second in enumerate(src[i+1:]):
            if first + second == target:
                pair.append([first, second])
                pair_id.append([i,j+i+1])
            elif first + second > target:
                break

#     print('pair,',pair)
#     print('pair_id',pair_id)
    return pair, pair_id

two = []
tmp = 1
while True:
    tmp *= 2
    if tmp > max_num:
        break
    two.append(tmp)

# for odd
all_pair =[]
all_pair_id = []
if len(odd) > 1:
    for target in two:
        pair, pair_id = get_pair(odd, target)
        all_pair += pair
        all_pair_id += pair_id
        
# make list
p_list = [[] for it in range(len(odd))]
for it in all_pair_id:
    p_list[it[0]].append(it[1])
    p_list[it[1]].append(it[0])

cnt = 0
while(True):
    END = True
    for i, it in enumerate(p_list):
        if len(it) == 1:
            p_list[it[0]] = []
            p_list[i] = []
            END = False
            cnt += 1
            break
    if END:
        break

# for even
all_pair =[]
all_pair_id = []
if len(even) > 1:
    for target in two:
        pair, pair_id = get_pair(even, target)
        all_pair += pair
        all_pair_id += pair_id
        
# make list
p_list = [[] for it in range(len(even))]
for it in all_pair_id:
    p_list[it[0]].append(it[1])
    p_list[it[1]].append(it[0])

while(True):
    END = True
    for i, it in enumerate(p_list):
        if len(it) == 1:
            p_list[it[0]] = []
            p_list[i] = []
            END = False
            cnt += 1
            break
    if END:
        break
print(cnt)

Submission status: Runtime Error

Solution code:

import math

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

l1 = [i for i in A if i%2==0]
l2 = [i for i in A if i%2!=0]

def is_this_ok(n):
    i = 2
    while 2**i <= n:
        if 2**i == n:
            return True
        i+=1
    return False


def f(l):
    memo = [True]*len(l)
    c = 0
    r = []
    for i in range(len(l)-1):
        if memo[i]:
            for j in range(i+1, len(l)):
                if memo[j]:
                    if is_this_ok(l[i]+l[j]):
                        #memo[i] = False
                        #memo[j] = False
                        c += 1
                        r.append((l[i],l[j]))
    return r


def dp(tpl, memo):
    if len(tpl) == 0:
        return 0
    r1 = dp(tpl[1:], memo)
    if (tpl[0][0] not in memo) and (tpl[0][1] not in memo):
        r2 = dp(tpl[1:], memo+tpl[0]) + 1
    else:
        r2 = 0

    return max(r1, r2)


r1 = dp(f(l1), (0,0))
r2 = dp(f(l2), (0,0))

print(r1 + r2)

Submission status: Runtime Error

Solution code:
N=int(input())
p=[]
list=[[]for i in range(N-1)]
for i in range(N-1):
    p=input().split()
    for char in p:
        list[i].append(int(char))
graph=[[] for i in range(N+1)]
for l in list:
    graph[l[0]].append(l[1])
    graph[l[1]].append(l[0])
count=[]
graph_c=[0 for i in range(0,N+4)]
for p in range(2,N+1):
    if graph_c[p]==0:
        c=1
        buf=[[],[]]
        done_point=[]
        done_list=[]
        done_point.append(p)
        done_list+=graph[p]
        m=min(graph[p])
        while m != 1 and graph_c[m]==0:
            if len(graph[m])>=3:
                buf[0].append(m)
                buf[1].append(c)
            c=c+1
            done_point.append(m)
            done_list+=graph[m]
            for a in done_point:
                if a in done_list:
                    done_list.remove(a)
            m=min(done_list)
        if not buf:
            b=buf[0][0]
            if graph_c[b]==0:
                count.append(graph_c[b])
        if m==1:
            if not buf:
                graph_c[b]=c-buf[1][0]+1
            count.append(c)
    else:
        count.append(graph_c[p])
for x in count:
    print(x, end=" ")
print("")

Submission status: Runtime Error

Solution code:
import bisect

N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
L=0
t=31
while(t>0):
    if len(A) == 0:
        break
    if A[-1]<(1<<(t-1)) or (1<<t) <= A[-1]:
        t -= 1
        L = 0
        continue

    large = A.pop(-1)
    small = (1<<t)-large
    if small < A[0] or A[-1]< small:
        t -= 1
        L = 0
        continue
    tmp = bisect.bisect_left(A,(1<<t)-large,lo=L,hi=len(A))
    if tmp == len(A):
        t -= 1
        L = 0
        continue
    if A[tmp] == (1<<t)-large:
        del A[tmp]
        ans += 1
        L = max(0,tmp-1)

print(ans)

Submission status: Runtime Error

Solution code:
n = input()
a = list(map(int, input().split()))
a.sort(reverse=True)
count = 0
for k, i in enumerate(a):
  pair = 2**(len(format(i,'b')))-i
  if pair == i and a.count(i)>1:
    count += 1
    a.index(k)
    a.index(k)
    a.insert(0,200001)
  elif pair == i and a.count(i)<=1:
    pass
  elif pair in a:
    count += 1
    a.remove(pair)
print(count)

Submission status: Runtime Error

Solution code:
def bins(a, x):
    left = 0
    right = len(a) - 1
    res = -1e10
    while left <= right:
        mid = (left + right) // 2
        if a[mid] == x:
            res = mid
            break
        elif a[mid] > x:
            right = mid - 1
        else:
            left = mid + 1
    return res

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

pow2s = [2 ** i for i in range(30)]
A.sort()
cand = [[0]*30 for _ in range(int(2e5) + 1)]
for i, a in enumerate(A):
    j = 0
    tmp = [pow2 - a for pow2 in pow2s]
    for t in tmp:
        index = bins(A[i:], t) + i
        if index > 0:
            cand[a][j] = t
            j += 1

suA = {i: 0 for i in A}
for i in A:
    suA[i] += 1
res = 0
for x in cand:
    for y in x:
        if y == 0:
            break
        if cand[y][0] == 0:
            res += 1
            break
        elif suA[i] >= 2:
            res += 1
            suA[i] -= 1
            break
print(res)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import copy

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

pairCounter=0
for i in range(N):
  if A[i] < 0:
    continue
  for b in range(9):
    pair=2**b - A[i]
    if pair < 1:
      continue
    if A.count(pair) >0:
      A[i] = -1
      A[A.index(pair)] = -1
      pairCounter+=1
      break

B=copy.copy(org)      
B.sort(reverse=True)
print(B)

pairCounterB=0
for i in range(N):
  if B[i] < 0:
    continue
  for b in range(9):
    pair=2**b - B[i]
    if pair < 1:
      continue
    if B.count(pair) >0:
      B[i] = -1
      B[B.index(pair)] = -1
      pairCounterB+=1
      break
      
if pairCounterB < pairCounter:
  print(pairCounter)
else:
  print(pairCounterB)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int, input().split()))
b=[1]*a[0]
for i in range(n-1):
  if(a[i]<a[i+1]):
    b=b+[1]*(a[i+1]-a[i])
  elif(a[i]==a[i+1]):
    b=[b[0]+1]+[1]*(a[i+1]-1)
  else:
    b=b[0:a[i+1]]
    b[-1]=b[-1]+1
print(b[0])

Submission status: Runtime Error

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
Ae=[]
Ao=[]
for i in range(N):
    if A[i]%2==0:
        Ae.append(A[i])
    else:
        Ao.append(A[i])
if Ao!=[]:
    s=0
    Ao.sort()
    i=1
    while i<=len(Ao):
        a=int(math.log2(Ao[-i]))
        if 2**(a+1)-Ao[-i] in Ao[:-i]:
            s+=1
            Ao.remove(2**(a+1)-Ao[-i])
            i+=1
        else:
            i+=1
else:
    s=0
if Ae!=[]
    t=0
    j=1
    Ae.sort()
    while j<=len(Ae):
        b=int(math.log2(Ae[-j]))
        if 2**(a+1)-Ae[-j] in Ae[:-j]:
            s+=1
            Ae.remove(2**(a+1)-Ae[-j])
            j+=1
        else:
            j+=1
else:
    t=0
print(s+t)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
Ae=[]
Ao=[]
for i in range(N):
    if A[i]%2==0:
        Ae.append(A[i])
    else:
        Ao.append(A[i])
if Ao!=[]:
    s=0
    Ao.sort()
    i=1
    while i<=len(Ao):
         a=int(math.log2(Ao[-i]))
        if 2**(a+1)-Ao[-i] in Ao[:-i]:
            s+=1
            Ao.remove(2**(a+1)-Ao[-i])
            i+=1
        else:
            i+=1
else:
    s=0
if Ae!=[]
    t=0
    j=1
    Ae.sort()
    while j<=len(Ae):
        b=int(math.log2(Ae[-j]))
        if 2**(a+1)-Ae[-j] in Ae[:-j]:
            s+=1
            Ae.remove(2**(a+1)-Ae[-j])
            j+=1
        else:
            j+=1
else:
    t=0
print(s+t)

Submission status: Runtime Error

Solution code:
from collections import deque, Counter, defaultdict


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


def solve(count):
    sk = sorted(count.keys())
    rd = {a: i for i, a in enumerate(sk)}
    lc = len(count)
    ma = max(count)

    mf = Dinic(2 * lc + 2)
    s, g = 0, 2 * lc + 1

    for i, a in enumerate(sk):
        cnt = count[a]
        li = i + 1
        k = 2
        b = k - a
        flag = False
        while b <= ma:
            if b > 0 and b in count:
                if a != b or cnt > 1:
                    mf.add_link(li, lc + rd[b] + 1, cnt)
                    flag = True
            k <<= 1
            b = k - a
        if flag:
            mf.add_link(s, li, cnt)
            mf.add_link(lc + li, g, cnt)

    # print(*mf.links, sep='\n')
    return mf.max_flow(s, g) // 2


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: Runtime Error

Solution code:
N=int(input())
A = list(map(int,input().split()))
count=0
skip=[]
for i in range(len(A)-1):
    if j in skip:
            continue
    for j in range(i+1,len(A)):
        if j in skip:
            continue
        else:
            
            A_num = A[i]+A[j]
            A_num = format(A_num, 'b')
            if sum(list(map(int,str(A_num)))) ==1:
                skip.append(int(i))
                skip.append(int(j))
                count+=1
                continue
print(count)

Submission status: Runtime Error

Solution code:
N=int(input())
A = list(map(int,input().split()))
A_list=[]
count=0
skip=[]
for i in range(len(A)-1):
    if j in skip:
            continue
    for j in range(i+1,len(A)):
        if j in skip:
            continue
        else:
            
            A_num = A[i]+A[j]
            A_num = format(A_num, 'b')
            if sum(list(map(int,str(A_num)))) ==1:
                skip.append(int(i))
                skip.append(int(j))
                count+=1
                continue

        
        

print(count)

Submission status: Runtime Error

Solution code:
N = input()
b= input().split(" ")

i = 0
gu_num =[]
ki_num = []
list_ni =[1, 2, 4, 8, 16, 32, 64, 128, 256, 512,
1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288,
1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912]
while i<=int(N)-1:
    if int(b[i])%2==0:
        gu_num.append(int(b[i]))
    else:
        ki_num.append(int(b[i]))
    i +=1

ki_kaisu =0
i=0
while i < len(ki_num):
    k=i+1
    while  k<len(ki_num):
        goukei = ki_num[i]+ki_num[k]
        judge= goukei in list_ni
        if judge==True:
            ki_kaisu += 1
        k +=1
    i += 1


gu_kaisu =0
i=0
while i < len(gu_num):
    k=i+1
    while  k<len(gu_num):
        goukei = ki_num[i]+gu_num[k]
        judge= goukei in list_ni
        if judge==True:
            gu_kaisu += 1
        k +=1
    i += 1



print(ki_kaisu+gu_kaisu)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
ct=0
 
M=max(a)
min=min(a)

if m>=10**8:
  print(0)
else:
  for i in range(100):
    if 2**i>M:
      x=i
      break
  L=[]
  for j in range(2**x-1):
    L.append(0)
  
  for j2 in range(n):
    L[a[j2]-1]+=1
  
  for k in range(x,1,-1):
    l1=L[0:2**(k-1)-1]
    l2=L[2**(k-1):2**k]
    l2.reverse()
    ct+=int(L[2**(k-1)-1]/2)
    for m in range(len(l1)):
      if l1[m]>=1 and l2[m]>=1:
        ct+=min(l1[m],l2[m])
        l1[m]-=min(l1[m],l2[m])
        l2[m]-=min(l1[m],l2[m])
    L=l1
  ct+=int(L[0]/2)
  print(ct)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

pairCounter=0
for i in range(N):
  if A[i] < 0:
    continue
  for b in range(9):
    pair=2**b - A[i]
    if pair < 1:
      continue
    #print(pair)
    if A.count(pair) >0:
      A[i] = -1
      A[A.index(pair)] = -1
      pairCounter+=1
      break

print(pairCounter)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict, deque
# import random
N = int(input())
tmp = list(map(int, input().split()))
# tmp = [random.randint(1,10**9) for _ in range(10**5)]
# print("run")

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:
    # print(f"t={t}")

    tmp_dict = defaultdict(list)
    idx_dict = defaultdict(list)
    for i,A in enumerate(An):
        if A > 0:
            tmp_dict[A % t].append(A)
            idx_dict[A % t].append(i)
    # print("An")
    # print(f"tmp_dict len = {len(tmp_dict)}")

    tmp = 0
    for k,v in list(tmp_dict.items()):
        if k == 0 or k == t:
            m = len(v) // 2
        else:
            if len(v) < len(tmp_dict[t-k]):
                m = len(v)
                dellist = idx_dict[k]
            else:
                m = len(tmp_dict[t-k])
                dellist = idx_dict[t-k]

        if m > 0:
            tmp += m
            for l in dellist:
                An[l] = 0
    ans += tmp//2

Submission status: Runtime Error

Solution code:
import numpy as np
import bisect

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

A = np.array(A)
AA = np.array(A)

beki = [2]
while beki[-1]*2 <= A[-1]+A[-2]:
    beki.append(beki[-1]*2)

beki = beki[::-1]
ans = 0
ind = 0
for b in beki:
    ind = 0
    for i in range(N-ans*2):
        tar = b - AA[ind]
        if tar < 0:
            break

        ind1 = bisect.bisect_left(AA,AA[ind],0,len(AA))
        ind2 = bisect.bisect_left(AA,tar,ind1,len(AA))

        if len(AA) > ind2 and AA[ind2] == tar:
            AA = np.delete(AA,ind1)
            AA = np.delete(AA,ind2-1)
            ans += 1

        else:
            ind += 1

        if len(AA) <= 1:
            break
    if len(AA) <= 1:
        break

print(ans)

Submission status: Runtime Error

Solution code:
import math

N = int(input())
a = list(map(int,input().split()))
a_odds = []
a_even = []

for i in range(N):
    if a[i]%2 != 0:
        a_odds.append(a[i])
    else:
        a_even.append(a[i])

a_odds.sort()
a_odds.reverse()
a_even.sort()
a_even.reverse()

count = 0
alist = []
max= 0
if a_odds!=[] and a_even!=[]:
    max = max(a_odds[0],a_even[0])
elif a_odds ==[]:
    max= a_even[0]
elif a_even == []:
    max = a_odds[0]
    
for i in range(round(math.log2(max))+1,0,-1):
    alist.append(2**i)


def my_index(l,x,default=False):
    if x in l:
        return l.index(x)
    else:
        return default

def judge(a,b):
    n = a+b
    ans = -1
    while(n>0):
        if n==1:
            ans = 0
            break
        elif n%2 == 1:
            ans = 1
            break
        elif n%2 == 0:
            n = n/2
    return ans


'''while(a_odds!=[]):
    for i in range(len(a_odds)):
        if judge(a_odds[0],a_odds[i])==0 and i!=0:
            count += 1
            a_odds.pop(i)
            break
    a_odds.pop(0)'''

while(a_odds!=[]):
    temp = a_odds[0]
    a_odds.pop(0)
    if a_odds ==[]:
        break
    for i in alist:
        b = i-temp
        if (i-temp) in a_odds:
            count += 1
            a_odds.pop(a_odds.index(i-temp))
            break
    
    
while(a_even!=[]):
    temp = a_even[0]
    a_even.pop(0)
    if a_even==[]:
        break
    for i in alist:
        if (i-temp) in a_even:
            count += 1
            a_even.pop(a_even.index(i-temp))
            break
    

print(count)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
ct=0
list=[]

if n==1:print(0)
else:
  for g in range(50):
    list.append(2**g)
  
  M=max(a)
  
  if M>=10**7:
    while M>=10**7:
      for h in range(len(a)):
        if M<10**7:
          break
        elif M+a[h] in list:
          ct+=1
          a.remove(M)
          a.remove(a[h])
          break
        else:
          a.remove(M)
        M=max(a)
        
  
  
  
  for i in range(50):
    if 2**i>M:
      x=i
      break
  L=[]
  for j in range(2**x-1):
    L.append(0)
  
  for j2 in range(len(a)):
    L[a[j2]-1]+=1
  
  for k in range(x,1,-1):
    l1=L[0:2**(k-1)-1]
    l2=L[2**(k-1):2**k]
    l2.reverse()
    ct+=int(L[2**(k-1)-1]/2)
    for m in range(len(l1)):
      if l1[m]>=1 and l2[m]>=1:
        ct+=min(l1[m],l2[m])
        l1[m]-=min(l1[m],l2[m])
        l2[m]-=min(l1[m],l2[m])
    L=l1
  ct+=int(L[0]/2)
  print(ct)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
ct=0
list=[]

if n==1:print(0)
else:
  for g in range(50):
    list.append(2**g)
  
  M=max(a)
  
  if M>=10**6:
    while M>=10**6:
      for h in range(len(a)):
        if M<10**6:
          break
        elif M+a[h] in list:
          ct+=1
          a.remove(M)
          a.remove(a[h])
          break
        else:
          a.remove(M)
        M=max(a)
        
  
  
  
  for i in range(50):
    if 2**i>M:
      x=i
      break
  L=[]
  for j in range(2**x-1):
    L.append(0)
  
  for j2 in range(len(a)):
    L[a[j2]-1]+=1
  
  for k in range(x,1,-1):
    l1=L[0:2**(k-1)-1]
    l2=L[2**(k-1):2**k]
    l2.reverse()
    ct+=int(L[2**(k-1)-1]/2)
    for m in range(len(l1)):
      if l1[m]>=1 and l2[m]>=1:
        ct+=min(l1[m],l2[m])
        l1[m]-=min(l1[m],l2[m])
        l2[m]-=min(l1[m],l2[m])
    L=l1
  ct+=int(L[0]/2)
  print(ct)