Problem:


Score : 600 points

Problem Statement

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

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

Constraints

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

1 \leq A_i \leq 10^9

A_i is an integer.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

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

Sample Input 1

3
1 2 3

Sample Output 1

1

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

Sample Input 2

5
3 11 14 5 13

Sample Output 2

2



Sample input:
3
1 2 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
from 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):
    if not count:
        return 0
    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: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
#A = [2,6,14,26]

def check(a,b):
	i = 2
	while(True):
		n = (a+b) >> i
		if n == 0:
			return False
		if (n << i) == (a+b):
			return True
		i+=1


def ans2(A):
	n = len(A)
	cnd = set()
	for i in range(n):
		for j in range(i+1,n):
			if check(A[i],A[j]):
				cnd.add(i)
				cnd.add(j)
	return(len(cnd)//2)

def ans1(A,n):
	if len(A) <= 1:
		return n
	a = A[0]
	bs = A[1:]
	m = []
	flag = False
	for p,b in enumerate(bs):
		if check(a,b):
			flag = True
			m.append(ans(bs[:p]+bs[p+1:],n+1))
	if not flag:
		return ans(A[1:],n)
	return max(m)


print(ans2(A))

Submission status: Wrong Answer

Solution code:
aaa = [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, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888]

a = int(input())

b = list(map(int,input().split()))
ma = 0
ppp = 0
lllll = 0
su = 0
k = [[] for i in range(a)]
kk =[0 for i in range(a)]
for i in range(a-1 - lllll):
	for j in range(1,a-i - lllll):
		for l in range(39):
			if b[i] + b[i+j] == aaa[l]:
				if ma <= b[i] +b[i+j]:
					ma = b[i] +b[i+j]
					ppp = i+j
	if ppp != 0:
		su += 1
		b.pop(ppp)
		lllll += 1
		ppp = 0
	ma = 0

print(su)

Submission status: Wrong Answer

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
            dellist = []
        else:
            dellist = idx_dict[k] + idx_dict[t-k]
            if len(v) < len(tmp_dict[t-k]):
                m = len(v)
            else:
                m = len(tmp_dict[t-k])

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import socket
from collections import Counter

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


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


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


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


def read_str():
    return input()


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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[]
a=input().split(" ")
x=0
y=0
for a in range(0,N): 
    if a%2==0:
        x=x+1
    if a%2==1:
        y=y+1
z=(y//2)+(x//2)
print(z)

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=True
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
        elif j is False:
            ans+=1
    else:
        ans+=1
ans=(n-ans)//2
print(ans)

Submission status: Wrong Answer

Solution code:
import math

num = int(input())
balls = set(map(int, input().rstrip().split(" ")))
count = 0

while balls:
  a = balls.pop()
  for b in balls:
    if math.sqrt(a + b) % 1 == 0.0:
      count += 1
      balls.remove(b)
      break
      

print(count)

Submission status: Wrong Answer

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

A.sort(reverse=True)
B = [2**math.ceil(math.log(i, 2)) - i for i in A]

c = 0
for i in B:
    if i in A:
        c += 1
        A.pop(A.index(i))
print(c)

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
a.sort()
a.reverse()
def beki(s):
  k = math.log2(s)
  k = int(k) + 1
  return 2**k - s
def nib(x,s):
  a = i+1
  b = len(x)-1
  while a <= b:
    c = int((a+b)/2)
    y = x[c]
    if y == s:
      return c
    if y > s:
      a = c+1
    else:
      b = c-1
  return None  
i = 0
c = 0
r = len(a)
while i < r:
  nb = nib(a,beki(a[i]))
  if nb is not None:
    a = a[0:i+nb+1]+a[i+nb+2:r]
    c += 1
    r -= 1
  i += 1
    
print(c)

Submission status: Wrong Answer

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

N = int(input())
org = list(map(int, input().split()))
A=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=org      
B.sort(reverse=True)
      
print(pairCounter)
"""

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[]
a=input().split(" ")
x=0
y=0
for a in range(0,N): #リストaの成分のうち偶奇の個数を数える
    if a%2==0:
        x=x+1
    else:
        y=y+1
z=(y//2)+(x//2)
print(z)

Submission status: Wrong Answer

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

A.sort(reverse=True)
B = [2**math.ceil(math.log(i, 2)) - i for i in A]
print(B)
c = 0
for i in B:
    if i in A:
        c += 1
        A.pop(A.index(i))
print(c)

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=True
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
    else:
        ans+=1
ans=(n-ans)//2
print(ans)

Submission status: Wrong Answer

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

li = []

for i in range(n):
    for t in range(1, 31):
        try:
            tmp = a[(i+1):n].index(2**t - a[i])
            li.append([a[i], a[tmp+i+1]])
        except:
            pass

from itertools import combinations

MAX = len(li)

flag=0
for j in range(MAX, 0, -1):
    for c in combinations(li, j):
        # print(c)

        cntSet = set()
        for _ in range(2):
            for i in range(len(c)):
                # print(c, c[i])
                if c[i][_] in cntSet:
                    flag = 1
                    break
                else:
                    cntSet.add(c[i][_])
        
        if flag==0:
            break

    if flag==0:
        break
print(len(cntSet))

Submission status: Wrong Answer

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

if M>=3*(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: 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=True
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
        elif j:
            ans+=1
    else:
        ans+=1
ans=(n-ans)//2
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
a.sort()
amax = a[-1]
c = collections.Counter(a)

beki2 = [2**i for i in range(1,31)]

cnt = 0
ans = []
for i in a:
    for j in beki2:
        if j-i > amax:
            break
        if j-i in c:
            if j-i == i and c[j-i] == 1:
                continue
            #print(i,j-i)
            ans.append(j-i)
            ans.append(i)
ansset = set(ans)
for i in ansset:
    cnt += c[i]

print(cnt//2)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ct=0
 
M=max(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: 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:
        value_flag[i] = False
        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)

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

print(bm.solve() // 2)

Submission status: Wrong Answer

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

if M>=10**7:
  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: Wrong Answer

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

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
            A[i]=10^9-1
            A[i+j]=10^9-1
            break
        

print(counter)

Submission status: Wrong Answer

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


def func(n, a):
    # a[i] + a[j] = 2^tとなる組の最大数
    a.sort()
    available = [True for _ in range(len(a))]
    # print(a)
    # diff = [search(a[i]) - a[i] for i in range(len(a))]
    diff = [[0, len(a) - i - 1] for i in range(len(a))]
    tmp = 0
    for i in range(len(diff)):
        tmp = search(a[i], tmp)
        diff[i][0] = 2 ** tmp - a[i]
    diff.sort()
    a.reverse()
    diff.reverse()
    # print("   a:{}".format(a))
    # print("diff:{}".format(diff))
    i = 0
    j = 0
    count = 0
    while i < len(a) and j < len(diff):
        while j < len(diff) and (diff[j][0] > a[i] or not available[diff[j][1]]):
            j += 1
        while i < len(a) and not available[i]:
            i += 1
        # print("i:{} j:{} count:{} avail:{}".format(i, j, count, available))
        if i < len(a) and j < len(a) and a[i] == diff[j][0]:
            if i != diff[j][1]:
                count += 1
                available[i] = False
                available[diff[j][1]] = False
                i += 1
                # if i > 0 and a[i - 1] == a[i] and i == diff[j][1]:
                # i += 1
                j += 1
            else:
                j += 1
        else:
            i += 1
    return count


n = int(input())
a = [int(i) for i in input().split()]
print("{}".format(func(n, a)))
# print("{}".format(func(3, [1, 2, 3])))
# print("{}".format(func(5, [3, 11, 14, 5, 13])))
# print("{}".format(func(3, [1, 3, 29, 35])))
# print("{}".format(func(5, [1, 2, 2, 2, 2])))
# print("{}".format(func(6, [1, 2, 2, 2, 2, 1])))

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
        elif j:
            ans+=1
    else:
        ans+=1
ans=(n-ans)//2
print(ans)

Submission status: Wrong Answer

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

t=1
twice=[]
while t < 2*max(x):
    twice.append(t)
    t*=2
l=[[] for _ in range(len(x))]
for t in twice:
    for i in range(len(x)):
        for j, xx in enumerate(x):
            if xx == t-x[i]:
                l[i].append(j)

for i in range(len(l)):
    if i in l[i]:
        l[i].remove(i)

check=[]
def length(i,count):
    #print(count,check)
    if i not in check:
        count+=1
        check.append(i)
        for i in l[i]:
            count =max(count, length(i,count))
    return count
ans=0
for i in range(len(x)):
    ans+=length(i,0)//2
print(ans)

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

print(y)
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:
            ans+=1
    else:
        ans+=1
ans=(n-ans)//2
print(ans)

Submission status: Wrong Answer

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

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
            A[i]=10^9-1
            A[i+j]=10^9-1
        break
        

print(counter)

Submission status: Wrong Answer

Solution code:
import numpy as np

M = int(input())
X = np.sort(list(map(int, input().split())))
S = []
C = {}
b = -1
c = -1
O = {}
for i, x in enumerate(X):
  if x != b:
    S.append(x)
    C[x] = 0
    O[x] = i
  elif x == b and x != c:
    S.append(x)
    c = x
  b = x
  C[x] += 1
  
N = len(S)

pair = {}
for x in [2**i for i in range(32)][1:]:
  for i in range(N):
    a = S[i]
    if a >= x:
      break
    m = np.searchsorted(S, x)
    for jj in range(m):
      j = m-jj-1
      if i == j:
        break
      b = S[j]
      if a+b < x:
        break
      if(a+b==x):
        for p in range(C[a]):
          if O[a]+p not in pair:
            pair[O[a]+p] = []
          for q in range(C[b]):
            if (O[a]+p < O[b]+q):
              pair[O[a]+p].append(O[b]+q)

match = -1 * np.ones(M, dtype=int)
used = np.zeros(M)

def dfs(v):
  used[v] = True
  if v in pair:
    for u in pair[v]:
      w = match[u]
      if w < 0:
        match[v] = u
        match[u] = v
        return True
      if used[w] == 0 and dfs(w):
        match[v] = u
        match[u] = v
        return True

  return False

res = 0
for v in range(M):
  if (match[v] < 0):
    used = np.zeros(M)
    if (dfs(v)):
      res += 1
print(res)

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
import sys

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

def search_l(tar, left, right):
    # print("##", tar, left, right)
    m = (left + right) // 2
    if right - left <= 2:
        for ret in range(left, right):
            if A[ret] == tar: return ret
            else: continue
        else: return -1
    elif A[m] == tar: return search_l(tar, left, m + 1)
    elif A[m] > tar: return search_l(tar, left, m)
    else: return search_l(tar, m + 1, right)

# for i, Ai in enumerate(A):
#     print("#", search_l(Ai, 0, len(A)))
# sys.exit()

maxA = A[-1]
for i_max in range(33):
    if 2 ** i_max > maxA: break

ans = 0
used = [0] * N
# print("#", A)
for i_q in list(range(N))[::-1]:
    if i_q == 0: break
    q = A[i_q]
    # print("##", i_q, q)
    # update i_max
    for i_tmp in range(33):
        if 2 ** i_max <= q: i_max -= 1
        else: break
    # search counterpart (minimum index)
    tar = (2 ** i_max) - A[i_q]
    i_p_min = search_l(tar, 0, i_q)
    # print("###", "search_l", tar, i_p_min)
    if i_p_min < 0: continue # not found
    # pick unused one
    i_p = i_p_min
    for i_tmp in range(N):
        # print("####", i_p, A[i_p])
        if A[i_p] > tar: break
        elif used[i_p] > 0: i_p += 1
        else: break
    if A[i_p] > tar: continue # sold out
    # accepted
    ans += 1
    used[i_p] = 1
    used[i_q] = 1
    # print("##", (i_p, i_q), A[i_p] + q)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
AN = input().split(" ")

C = 0
count = 0

for i in range(N):

    if i == len(AN) - 1:
        break

    A = int(AN[i])
    flag = False
    for j in range(i+1, len(AN)):

        B = int(AN[j])

        C = A + B
        
        while True:
            if C == 2:
                count += 1
                i = 0
                flag = True
                break

            mod = C % 2

            if mod == 0:
                C = C // 2
            else:
                break

        if flag == True:
            break

print(count)

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):
    ans+=1
ans=(n-ans)//2
print(ans)

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
            A[i]=0
            A[i+j]=0
        break
        

print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
count = 0
for j in range(n):
  if a[j] > 0:
    p = sum([2**(k+1) for k in range(17) if 2**k <= a[j] < 2**(k+1)])
    for i in range(n-j):
      if a[j]+a[n-1-i] > p:
        break
      if (a[j]+a[n-1-i]) % p == 0:
        count += 1
        a[n-1-i] = -p
        break
print(count)

Submission status: Wrong Answer

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