Problem:


Score : 600 points

Problem Statement

Takahashi has N balls with positive integers written on them. The integer written on the i-th ball is A_i.
He would like to form some number of pairs such that the sum of the integers written on each pair of balls is a power of 2.
Note that a ball cannot belong to multiple pairs.
Find the maximum possible number of pairs that can be formed.

Here, a positive integer is said to be a power of 2 when it can be written as 2^t using some non-negative integer t.

Constraints

1 \leq N \leq 2\times 10^5

1 \leq A_i \leq 10^9

A_i is an integer.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible number of pairs such that the sum of the integers written on each pair of balls is a power of 2.

Sample Input 1

3
1 2 3

Sample Output 1

1

We can form one pair whose sum of the written numbers is 4 by pairing the first and third balls.
Note that we cannot pair the second ball with itself.

Sample Input 2

5
3 11 14 5 13

Sample Output 2

2



Sample input:
3
1 2 3


Sample output:
1

Submission status: Wrong Answer

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

n_pears = 0

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

div, mod = divmod(n_pears * 2 - N, 2)
if mod == 1:
    div += 1
print(n_pears - div)

Submission status: Wrong Answer

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
maxa=max(a)
m=len(bin(maxa))-2
x=[[] for _ in range(m)]
for i in range(n):
    x[len(bin(a[i]))-3].append(a[i])
y=[]
for i in range(m):
    ti=m-1-i
    for j in range(len(x[ti])):
        tj=len(x[ti])-1-j
        
        tx=2**(len(bin(x[ti][tj]))-2)-x[ti][tj]
        tk=len(bin(tx))-3
        if x[ti][tj]==tx:
            y.append(tx)
            continue
        
        tz=bisect.bisect_left(x[tk],tx)
        if tz<len(x[tk]) and tx==x[tk][tz]:
            del x[tk][tz]
        else:
            y.append(x[ti][tj])
y.sort()
z=[2**i for i in range(30)]
y.append(0)

j=False
ans=0

for i in range(len(y)-1):
    if y[i] in z:
        if y[i]==y[i+1]:
            if j:
                j=False
            else:
                j=True
    else:
        ans+=1
ans=-(ans-n)//2
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0
pair_dict = {}
for i, a in enumerate(A):
    if a == -1:
        continue
    try:
        A[pair_dict.pop(a)] = -1
        a = -1
        ans += 1
    except:
        pair_dict[2**(int(math.log2(a))+1)-a] = i

print(ans)

Submission status: Wrong Answer

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

b = []

i = 1
max = 10**9
while True:
    t = 2**i
    if t < max:
        b.append(t)
    else:
        break
    i = i+1

e = []
o = []
for s in a:
    if s % 2 == 0:
        e.append(s)
    else:
        o.append(s)

#print(e)
#print(o)

sum = 0

i = 0
j = 0
for i in range(len(e) - 1):
    for j in range(i+1,len(e)):
        if b.count(e[i] + e[j]) > 0 :
            t = e[j]
            e[j] = e[i+1]
            e[i+1] = t
            i += 1
            sum += 1
            break            

i = 0
j = 0
for i in range(len(o) - 1):
    for j in range(i+1,len(o)):
        if b.count(o[i] + o[j]) > 0 :
            t = o[j]
            o[j] = o[i+1]
            o[i+1] = t
            sum += 1
            i += 1
            break

print(sum)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import math

def main():
	input()
	N = list(map(int,input().split()))
	se = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296]
	re = list(permutations(N, 2))
	
	re2 = []
	for i in re:
		if sum(i) in se:
			for j in i:
				re2.append(j)
	print( len(set(re2))//2 )



main()

Submission status: Wrong Answer

Solution code:
n=int(input())
d={}
v=0
*l,=map(int,input().split())
m=0

for i in l:
  d[i]=True
  m=max(m,i)

f=lambda x,y:2**(len(bin(x))+y-1)-x

for x in sorted(l)[::-1]:
  if not d[x]:continue
  for y in range(30):
    buf=f(x,y)
    if buf>10**9 or buf>m:break
    if buf in d and d[buf]:
      d[x],d[buf]=False,False
      v+=1
      break

print(v)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = sorted(A, reverse=True)
A = B
counter=0


for i in range(N):
    for j in range(1,N-i):
        temp=(int(bin(A[i]+A[i+j]).strip("0b")))
        if(temp&(temp-1)) ==0:
            counter +=1
        break
        

print(counter)

Submission status: Wrong Answer

Solution code:
import bisect

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

P2=[]
for i in range(1,32):
  P2.append(2**i)
  
def solve():
  a=A.pop()
  l=len(A)
  x=bisect.bisect_left(P2,a)
  for i in range(x,31):
    if a > P2[i]:
      return False
    else:
      cnt=P2[i]-a
      b=bisect.bisect_left(A,cnt)
      if b != l and A[b]== cnt:
        A.pop(b)
        return True

ans=0
for i in range(N):
  if len(A) < i:
    break
  else:
    if solve():
      ans+=1
print(ans)

Submission status: Wrong Answer

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


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


N = int(fin())
A_list = [int(elem) for elem in fin().split()]
# groups = tuple([defaultdict(list) for _ in range(32)])
groups = tuple([dict() for _ in range(32)])

adj = [[] for _ in range(N)]
for i, pow_2 in enumerate(possible_pows):
    for j, A in enumerate(A_list):
        if A in groups[i]:
            neighbor = groups[i][A]
            adj[j].append(neighbor)
            adj[neighbor].append(j)
        elif A <= pow_2:
            groups[i][pow_2 - A] = j
    # print(groups[i])

# print(adj)

used = [False] * N
match = [False] * N
def dfs(v):
    used[v] = True
    for nei in adj[v]:
        w = match[nei]
        if w == False or (not used[w] and dfs(w)):
            match[v] = nei
            match[nei] = v
            return True
    else:
        return False

res = 0
for v in range(N):
    if not match[v]:
        used = [False] * N
        if dfs(v):
            res += 1
print(res)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
#print (N,A)
i = 0
cnt = 0
while (i < len(A)-1):
    length = len(A)
    for j in range(length-1-i):
        temp = len(A)-1-j
        s = A[i]+A[temp]
        if ( 0 == s&(s-1)):
            A.pop(temp)
            cnt += 1
            break
        #print (A)
    i+=1
print (cnt)

Submission status: Wrong Answer

Solution code:
la=[262144,131072,65536,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2]
n=int(input())
l=list(map(int,input().split()))
l.sort()
l.reverse()
llen=len(l)
i=0
c=0
while True:
  if i>=llen:
    break
  a=l[i]
  for j in la:
    if j<=a:
      continue
    else:
      x=j-a
      if l.count(x)==1:
        if x==a:
          continue
        else:
          l.remove(x)
          c+=1
          i+=1
          llen-=1
      elif l.count(x):
        l.remove(x)
        c+=1
        i+=1
        llen-=1
  i+=1
print(c)

Submission status: Wrong Answer

Solution code:
import bisect

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

t_max=A[-1]+A[-2]

B=[]	#Beki

t=1
while t < t_max:
	t*=2
	if t<=t_max:
		B.append(t)

FLAG=[ 0 for i in range(N) ]

ans=0


for i in range(N-1,0,-1):

	x=A[i]
	bi=bisect.bisect_left(B,x)
	b=B[bi]
	ti=bisect.bisect_left(A, b-x)

	if A[ti]==b-x and FLAG[i]==0 and FLAG[ti]==0:
		ans+=1
		FLAG[i]=1
		FLAG[ti]=1

print ans

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(1, 32):
    base = 2**i
    pair_dict = {}
    for i, a in enumerate(A):
        if a == -1:
            continue
        try:
            A[pair_dict.pop(a)] = -1
            a = -1
            ans += 1
        except:
            pair_dict[base-a] = i

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


class MaxFlow:
    class Edge:
        def __init__(self, to, cap, rev):
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, node_size, inf):
        self._node = node_size
        self._inf = inf
        self._level = [-1]*self._node
        self._iter = [0]*self._node
        self._graph = [[] for _ in range(self._node)]

    def add_edge(self, from_, to, cap):
        self._graph[from_].append(self.Edge(to, cap, len(self._graph[to])))
        self._graph[to].append(self.Edge(from_, 0, len(self._graph[from_])-1))

    def bfs(self, start):
        self._level = [-1]*self._node
        que = deque()
        self._level[start] = 0
        que.append(start)
        while que:
            cur_vertex = que.popleft()
            for e in self._graph[cur_vertex]:
                if self._level[e.to] < 0 < e.cap:
                    self._level[e.to] = self._level[cur_vertex] + 1
                    que.append(e.to)

    def dfs(self, cur_vertex, end_vertex, flow):
        if cur_vertex == end_vertex:
            return flow
        while self._iter[cur_vertex] < len(self._graph[cur_vertex]):
            e = self._graph[cur_vertex][self._iter[cur_vertex]]
            if e.cap > 0 and self._level[cur_vertex] < self._level[e.to]:
                flowed = self.dfs(e.to, end_vertex, min(flow, e.cap))
                if flowed > 0:
                    e.cap -= flowed
                    self._graph[e.to][e.rev].cap += flowed
                    return flowed
            self._iter[cur_vertex] += 1
        return 0

    def solve(self, source, sink):
        flow = 0
        while True:
            self.bfs(source)
            if self._level[sink] < 0:
                return flow
            self._iter = [0]*self._node
            while True:
                f = self.dfs(source, sink, self._inf)
                if f == 0:
                    break
                flow += f


class BipartiteMatching:
    def __init__(self, size1, size2):
        self._u_size, self. _v_size = size1, size2
        self.mf = MaxFlow(self._u_size+self. _v_size+2,
                          min(self._u_size, self._v_size))
        for i in range(self._u_size):
            self.mf.add_edge(0, i+1, 1)
        for i in range(self._v_size):
            self.mf.add_edge(self._u_size+i+1, self._u_size+self._v_size+1, 1)

    def add_edge(self, from_, to):
        self.mf.add_edge(from_+1, to+self._u_size+1, 1)

    def solve(self):
        return self.mf.solve(0, self._u_size+self._v_size+1)


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

pow_set = {2 ** p for p in range(1, 32)}

bm = BipartiteMatching(n, n)

value_dic = {}
value_flag = [True for i in range(n)]
for i, a, in enumerate(A):
    if a in value_dic:
        bm.add_edge(i, i)
        for v in value_dic[a]:
            bm.add_edge(v, i)
            if value_flag[v] is True:
                value_flag[v] = False
                bm.add_edge(v, v)
            if value_flag[i] is True:
                value_flag[i] = False
                bm.add_edge(i, i)

    for k in pow_set:
        if k - a < 1:
            continue
        if k - a not in value_dic:
            value_dic[k - a] = set()
        value_dic[k - a].add(i)

print(bm.solve() // 2)

Submission status: Wrong Answer

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
maxa=max(a)
m=len(bin(maxa))-2
x=[[] for _ in range(m)]
for i in range(n):
    x[len(bin(a[i]))-3].append(a[i])
y=[]
for i in range(m):
    ti=m-1-i
    for j in range(len(x[ti])):
        tj=len(x[ti])-1-j
        
        tx=2**(len(bin(x[ti][tj]))-2)-x[ti][tj]
        tk=len(bin(tx))-3
        if x[ti][tj]==tx:
            y.append(tx)
            continue
        
        tz=bisect.bisect_left(x[tk],tx)
        if tz<len(x[tk]) and tx==x[tk][tz]:
            del x[tk][tz]
        else:
            y.append(x[ti][tj])
y.sort()
ans=0
z=[2**i for i in range(30)]
y.append(0)

j=False
for i in range(len(y)-1):
    if y[i] in z:
        if y[i]==y[i+1]:
            if j:
                j=False
            else:
                j=True
        elif j is False:
            ans+=0
    else:
        ans+=1
ans=(n-ans)//2
print(ans)

Submission status: Wrong Answer

Solution code:
def is_power2(num):
	return num != 0 and ((num & (num - 1)) == 0)


a = input()
b = input().split()
b = [int(i) for i in b]
dicter = dict()
counter = 0
i = 0
while i < len(b):
	temp = b[i]
	if temp not in dicter:
		dicter[temp] = 1
		i += 1
	else:
		dicter[temp] += 1
		i += 1
		if is_power2(temp) == True and dicter[temp] == 2:
			counter += 1
			dicter[temp] = 0
		
lister = [2**i for i in range(31)][::-1]
for i in b:
	if dicter[i] > 0:
		for j in lister:
			if j - i in dicter and dicter[j - i] >= 1 and not (i == j - i):
				dicter[j - i] -= 1
				dicter[i] -= 1
				counter += 1
				break
			 
	
print(counter)

Submission status: Wrong Answer

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

ans = 0
pwtwo = [2**i for i in range(1, 31)]
pn = [0 for _ in range(n)]
ok = []
for i in range(n):
    for j in range(i+1, n):
        if (a[i]+a[j]) in pwtwo:
            ok.append((i, j))
            pn[i] += 1
            pn[j] += 1

while sum(x >= 2 for x in pn):
    if 1 in pn:
        i = pn.index(1)
        for j in range(n):
            if i in ok[j]:
                p, q = ok[j]
                pn[p] = 0
                pn[q] = 0
                break
        ans += 1
    else:
        ans += sum(x >= 2 for x in pn) // 2
        break

ans += sum(x >= 1 for x in pn) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))


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

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

mf = Dinic(2 * lc + 2)

for i in range(lc):
    a = sk[i]
    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(0, li, cnt)
        mf.add_link(lc + li, 2 * lc + 1, cnt)

# print(*mf.links, sep='\n')

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

Submission status: Wrong Answer

Solution code:
from collections import Counter as C
n = int(input())
l = sorted(map(int, input().split()), reverse = True)
c = C(l)
res = 0
for e in l:
    for p in range(32, 0, -1):
        e_ = (1 << p) - e
        if c.get(e_, 0) > 0:
            # print(e, e_, c)
            c[e_] -= 1
            c[e] -= 1
            res += 1
            break
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
# A = [3, 11, 14, 5, 13]

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(1, 32):
    base = 2**i
    pair_dict = {}
    for i, a in enumerate(A):
        if a == -1:
            continue
        elif a in pair_dict:
            A[pair_dict.pop(a)] = -1
            a = -1
            ans += 1
            continue
        pair_dict[base-a] = i

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
d={}
v=0
*l,=map(int,input().split())
m=0

for i in l:
  d[i]=True
  m=max(m,i)

f=lambda x,y:2**(len(bin(x))+y-1)-x

for x in sorted(l)[::-1]:
  if not d[x]:continue
  for y in range(30):
    buf=f(x,y)
    if buf>10**9 or buf>m:continue
    if buf in d and d[buf]:
      d[x],d[buf]=False,False
      v+=1
      break

print(v)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
a = [int(i) for i in input().split()]

a.sort(reverse=True)

count = 0
for _ in range(N):
    for y in range(1, len(a)):
        if a[0] % 2 != a[y]:
            continue
        if math.log2(a[0]+a[y]) % 1 == 0:
            count += 1
            del a[y]
            break
    del a[0]
    if len(a) < 1:
        break

print(count)

Submission status: Wrong Answer

Solution code:
ball_num = int(input())
engraved_nums = [int(A) for A in input().split(" ")]

candidates = []
two_pow = 2

while(two_pow < 10**9):
  candidates.append(two_pow)
  two_pow *= 2
candidates.reverse()

odd_nums = []
even_nums = []

engraved_nums.sort()
engraved_nums.reverse()

for num in engraved_nums:
  if num % 2 == 0:
    even_nums.append(num)
  else:
    odd_nums.append(num)

pair_num = 0
for cand in candidates:
  for nums in (even_nums, odd_nums):
    num_len = len(nums)
    i = 0
    while i < num_len:
      if cand > nums[i]:
        j = i + 1
        while j < num_len:
          will_removed = nums[i]
          if cand == nums[i] + nums[j]:
            pair_num += 1
            nums.remove(nums[j])
            nums.remove(will_removed)
            num_len -= 2
            j -= 1
            i -= 1
          j += 1
      i += 1

print(pair_num)

Submission status: Wrong Answer

Solution code:
import numpy as np
# N = int(input())
# A = list(map(int, input().split()))
A = [3, 11, 14, 5, 13]

A = np.array(A)
ax, ay = np.meshgrid(A, A)
AA = ax + ay
triAA = np.triu(AA, k=1)
# print(triAA.dtype)
# triAA = triAA.ravel()
# print(triAA)
# np.where(triAA)
tmp_bool = np.array([False]*len(A))
# print(row_bool)
powers = [int(2**i) for i in range(1, 33)]
for p in powers:
    # print(p)
    col_bool = np.any(triAA == p, axis=1)
    triAA[0, col_bool] = 0
    tmp_bool = np.logical_or(tmp_bool, col_bool)
    # total += np.any(triAA == p, axis=0).sum()
print(tmp_bool.sum())
# print(triAA in (1, 2))

Submission status: Wrong Answer

Solution code:
n=int(input())
d={}
v=0
*l,=map(int,input().split())
for i in l:
  d[i]=True

f=lambda x,y:2**(len(bin(x))+y-1)-x

for x in sorted(l)[::-1]:
  if not d[x]:continue
  for y in range(30):
    buf=f(x,y)
    if buf in d and d[buf]:
      d[x],d[buf]=False,False
      v+=1
      break

print(v)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))


odd = [A[i] for i in range(N) if A[i]%2 != 0 ]
even = list(set(A)-set(odd))

odd.sort(reverse=True)
even.sort(reverse=True)

count = 0
for i in odd:
    try:
        odd.remove(2**(int(np.log2(i))+1)-i)
        count += 1
    except:
        continue

for i in even:
    try:
        even.remove(2**(int(np.log2(i))+1)-i)
        count += 1
    except:
        continue

print(count)

Submission status: Wrong Answer

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

c = []
for i in range(n):
    for j in range(len(b)):
        if -a[i]+b[j] > 0:
            if not (-a[i] + b[j]== a[i] and a[i] != a[i-1]):
                 c.append(-a[i]+b[j])

C = set(c)

d = C&A
print(len(d)//2)

Submission status: Wrong Answer

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
        l+=1
      r-=1
    elif A[l]+A[r]<t:
      l+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

def is_power2(num):
	return num != 0 and ((num & (num - 1)) == 0)


a = input()
b = input().split()
b = [int(i) for i in b]
b.sort()
dicter = dict()
counter = 0
i = 0
while i < len(b):
	temp = b[i]
	if temp not in dicter:
		dicter[temp] = 1
		i += 1
	else:
		dicter[temp] += 1
		i += 1
		if is_power2(temp) == True and dicter[temp] == 2:
			counter += 1
			dicter[temp] = 0
			
			del b[bisect.bisect_left(b, temp)]
			del b[bisect.bisect_left(b, temp)]
			i -= 2
		
lister = [2**i for i in range(31)][::-1]
for i in b:
	for j in lister:
		if j - i in dicter and dicter[j - i] >= 1 and not (i == j - i) :
			dicter[j - i] -= 1
			dicter[i] -= 1
			counter += 1
			break
			 
	
print(counter)

Submission status: Wrong Answer

Solution code:
la=[262144,131072,65536,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2]
n=int(input())
l=list(map(int,input().split()))
l.sort()
l.reverse()
llen=len(l)
i=0
c=0
while True:
  if i>=llen:
    break
  a=l[i]
  for j in la:
    if j<=a:
      continue
    else:
      x=j-a
      if l.count(x):
        l.remove(x)
        c+=1
        i+=1
        llen-=1
  i+=1
print(c)

Submission status: Wrong Answer

Solution code:

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

Submission status: Wrong Answer

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

def is_in(t, n):
    i = bisect.bisect_right(A, t) - 1
    if i > n or i < 0:
        return False

    while t == A[i]:
        if i not in already:
            already.add(i)
            return True

        i -= 1
        if i < 0:
            return False

    return False

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:
        if is_in(t - a, n):
            res += 1
            break
        t >>= 1
print("AAA")
print(res)

Submission status: Wrong Answer

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):
  for j in range(N -i -1):
    if A[j+i +1] < 1:
      continue
    if A[i] < 1:
      break
    wa = A[i] + A[j+i +1]
    for b in range(9):
      if 2**b & wa == wa:
        A[i]=-1
        A[j+i +1]=-1
        pairCounter+=1
        break

print(pairCounter)

Submission status: Wrong Answer

Solution code:
n = input()
a = list(map(int, input().split()))
a.sort(reverse=True)
count = 0
ex_list = []
for i in a:
  ex_list.append(i)
  pair = 2**(len(format(i,'b')))-i
  if a.count(pair)-ex_list.count(pair)>0:
    count += 1
    ex_list.append(pair)
print(count)

Submission status: Wrong Answer

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

def is_in(t, n):
    i = bisect.bisect_right(A, t) - 1
    if i > n or i < 0:
        return False

    while t == A[i]:
        if i not in already:
            already.add(i)
            return True

        i -= 1
        if i < 0:
            return False

    return False

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:
        if is_in(t - a, n):
            res += 1
            break
        t >>= 1

print(res)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
list=[]
list = t.split()
print(list)
ans=0

def even(i,k):
  for j in range(k+1,len(list)):
    if(int(list[j])%2==0):
      s = i + int(list[j])
      if(power(s)):
        return 1
    else:
      continue
      
  return 0
  
def odd(i,k):
  for j in range(k+1,len(list)):
    if(int(list[j])%2==0):
      continue
    else:
      s = i + int(list[j])
      if(power(s)):
        return 1
      
  return 0
      

def power(s):
  while(True):
    s = int(s / 2)
    if(s==1):
       return 1

    if(s % 2 != 0):
      break      
      return 0

for i in range(len(list)-1):
  if(int(list[i]) % 2 == 0):
    if(even(int(list[i]),i)):
      ans = ans+1
  else:
    if(odd(int(list[i]),i)):
      ans = ans+1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter as C
n = int(input())
l = sorted(map(int, input().split()), reverse = True)
c = C(l)
res = 0
for e in l:
    e_ = (1 << (len(bin(e)) - 2)) - e
    # print(e, e_)
    if c.get(e_, 0) > 0:
        c[e_] -= 1
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
import bisect

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

P2=[]
for i in range(1,32):
  P2.append(2**(32-i))
  
def solve():
  a=A.pop(0)
  l=len(A)
  for i in range(31):
    if a > P2[i]:
      return False
    else:
      cnt=P2[i]-a
      b=bisect.bisect_left(A,cnt)
      if b != l and A[b]== cnt:
        A.pop(b)
        return True

ans=0
for i in range(N):
  if len(A) < i:
    break
  else:
    if solve():
      ans+=1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

    else:
        j -=1
        line[j-1].append(a[i])
for i in range(p):
    ans -= (mom[i]*(mom[i]+1))//2
#print(mom)
#print(p)
#print(line)
b=[]
for i in range(p-1,0,-1):
    for x in line[i]:
        j = 0
        while n-1-j>= 0:
            #print(a[n-1-j])
            if x + a[n-1-j] == 2**(i+1) and j not in b:
                ans += 1
                #print(x,a[n-1-j])
                b.append(j)
                break
            elif x + a[n-1-j] > 2**(i+1):
                break
            else:
                j += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from itertools import permutations

def main():
	input()
	bitlist = list(map(int,input().split()))
	re = list(permutations(bitlist, 2))

	re2 = []
	for i in re:
		if float.is_integer(math.log2(sum(i))):
			for j in i:
				re2.append(j)
	print( len(set(re2))//2 )


main()

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))


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

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

mf = Dinic(2 * lc + 2)

for i in range(lc):
    a = sk[i]
    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(0, li, cnt)
        mf.add_link(lc + li, 2 * lc + 1, cnt)

# print(*mf.links, sep='\n')

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

Submission status: Wrong Answer

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

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