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: Time Limit Exceeded

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

n_pears = 0
used_ball = [False] * N

for i in reversed(range(0, len(A))):
    if used_ball[i]:
        continue
    for j in reversed(range(0, i)):
        if used_ball[j]:
            continue
        if not ((A[i] + A[j]) & (A[i] + A[j] - 1)):
            n_pears += 1
            used_ball[j] = True
            break

print(n_pears)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, os
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr) if os.environ.get("USER")=="shun" else None
def exit(): sys.exit(0)


n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]
m = 0
while True:
    if 2**m > max_a:
        break
    m += 1
used = [False] * n


def bisect(val, start, end):
    debug(used)
    if start >= end:
        return None
    elif start + 1 == end:
        if a[start] == val:
            if used[start]:
                return None
            used[start] = True
            return start
        else:
            return None
    mid = (start + end) // 2
    if a[mid] == val:
        if used[mid]:
            res = bisect(val, start, mid)
            return res
        else:
            res = bisect(val, mid+1, end)
            if res is not None:
                return res
            used[mid] = True
            return mid
        # if used[mid]:
        #     res = bisect(val, mid+1, end)
        #     if res is not None:
        #         return res
        #     res = bisect(val, start, mid)
        #     return res
        # else:
        #     used[mid] = True
        #     debug("fuga", used)
        #     return mid
    elif a[mid] > val:
        return bisect(val, start, mid)
    else:
        return bisect(val, mid, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i]  == val):
    #         used[i] = True
    #         return i
    return None


def _find(b, end, e):
    # debug(b, end, e)
    val = 2**e - b
    if val <= 0:
        return None
    return bisect(val, 0, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i] + b == 2**e):
    #         used[i] = True
    #         return i
    # return None


def find(b, end):
    for e in reversed(range(m+1)):
        res = _find(b, end, e)
        if res is not None:
            return True
    return False


ans = 0
for j in reversed(range(n)):
    if used[j]:
        continue
    b = a[j]
    used[j] = True
    res = find(b, j)
    if res:
        ans += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, os
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr) # if os.environ.get("USER")=="shun" else None
def exit(): sys.exit(0)


n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]
m = 0
while True:
    if 2**m > max_a:
        break
    m += 1
used = [False] * n


def bisect(val, start, end):
    debug(used)
    if start >= end:
        return None
    elif start + 1 == end:
        if a[start] == val:
            if used[start]:
                return None
            used[start] = True
            return start
        else:
            return None
    mid = (start + end) // 2
    if a[mid] == val:
        if used[mid]:
            res = bisect(val, start, mid)
            return res
        else:
            res = bisect(val, mid+1, end)
            if res is not None:
                return res
            used[mid] = True
            return mid
        # if used[mid]:
        #     res = bisect(val, mid+1, end)
        #     if res is not None:
        #         return res
        #     res = bisect(val, start, mid)
        #     return res
        # else:
        #     used[mid] = True
        #     debug("fuga", used)
        #     return mid
    elif a[mid] > val:
        return bisect(val, start, mid)
    else:
        return bisect(val, mid, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i]  == val):
    #         used[i] = True
    #         return i
    return None


def _find(b, end, e):
    # debug(b, end, e)
    val = 2**e - b
    if val <= 0:
        return None
    return bisect(val, 0, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i] + b == 2**e):
    #         used[i] = True
    #         return i
    # return None


def find(b, end):
    for e in reversed(range(m+1)):
        res = _find(b, end, e)
        if res is not None:
            return True
    return False


ans = 0
for j in reversed(range(n)):
    if used[j]:
        continue
    b = a[j]
    used[j] = True
    res = find(b, j)
    if res:
        ans += 1


print(ans)

Submission status: Time Limit Exceeded

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

n_pears = 0
used_balls = []

for i in reversed(range(0, len(A))):
    if i % 1000 == 0:
        used_balls.sort()
        for n in used_balls:
            if i <= n:
                del used_balls[n:]
            break
        if i == n:
            continue
    if i in used_balls:
        continue
    for j in reversed(range(0, i)):
        if j in used_balls:
            continue
        if not ((A[i] + A[j]) & (A[i] + A[j] - 1)):
            n_pears += 1
            used_balls.append(j)
            break

print(n_pears)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
aA = sorted([int(_) for _ in input().split()],reverse=True)
aA1 = [ _ for _ in aA if _ % 2 ]
aA0 = [ _ for _ in aA if _ % 2 == 0 ]


def searchPair(aD):
    iL = len(aD)
    dsT =set()
    iC = 0
    for i in range(iL):
        for j in range(i+1,iL):
            if i in dsT or j in dsT:
                continue
            iWa =  aD[i] + aD[j]
            if not ( iWa & (iWa - 1)):
                dsT.add(i)
                dsT.add(j)
                iC += 1
                break

    return iC
iC = 0
iC += searchPair(aA1)
iC += searchPair(aA0)
print(iC)

Submission status: Time Limit Exceeded

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

from collections import defaultdict

xs = sorted(A, reverse=True)

cs = defaultdict(int)

for x in xs:
    cs[x] += 1

result = 0

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

#print(cs)
print(result)

Submission status: Time Limit Exceeded

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
    
    if a[i+1:].count(t) > 0:
        sum += 1
        a.remove(t)

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

print(sum)

Submission status: Time Limit Exceeded

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

n_pears = 0
used_balls = []

for i in reversed(range(0, len(A))):
    if i in used_balls:
        continue
    for j in reversed(range(0, i)):
        if j in used_balls:
            continue
        if not ((A[i] + A[j]) & (A[i] + A[j] - 1)):
            n_pears += 1
            used_balls.append(j)
            break

print(n_pears)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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 pair in a[k+1:]:
    count += 1
    a.pop(k)
  elif pair == i:
    pass
  elif pair in a:
    count += 1
    a.remove(pair)
print(count)

Submission status: Time Limit Exceeded

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

a.sort(reverse=True)
#print(a)

sum = 0
i = 0
while True:

    t = 0
    for bb in b :
        if bb > a[i]:
            t = bb - a[i]
            break
    
    if a[i+1:].count(t) > 0:
        sum += 1
        a.remove(t)

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

print(sum)

Submission status: Time Limit Exceeded

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

n_pears = 0
used_balls = []

for i in reversed(range(0, len(A))):
    if i in used_balls:
        continue
    for j in reversed(range(0, i)):
        if j in used_balls:
            continue
        if not (A[i] + A[j]) & (A[i] + A[j] - 1):
            n_pears += 1
            used_balls.append(i)
            used_balls.append(j)
            break

print(n_pears)

Submission status: Time Limit Exceeded

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

A.sort()
m = 1 << 30
used = [False] * n
ans = 0

def search(ok, ng, n):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if A[mid] < n or (A[mid] == n and used[mid]):
        return search(mid, ng, n)
    else:
        return search(ok, mid, n)

for i in range(30):
    for j in range(n):
        if used[j] or A[j] >= m:
            continue
        a = search(-1, n, m - A[j]) + 1
        if a >= n:
            continue
        if A[a] == m - A[j]:
            if a == j:
                a += 1
                if a >= n or not A[a] == A[j]:
                    continue
            used[a] = True
            used[j] = True
            ans += 1
    m >>= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
aA = sorted([int(_) for _ in input().split()],reverse=True)
#aA1 = [ _ for _ in aA if _ % 2 ]
#aA0 = [ _ for _ in aA if _ % 2 == 0 ]


def searchPair(aD):
    iL = len(aD)
    dsT =set()
    iC = 0
    for i in range(iL):
        for j in range(i+1,iL):
            if i in dsT or j in dsT:
                continue
            iWa =  aD[i] + aD[j]
            if not ( iWa & (iWa - 1)):
                dsT.add(i)
                dsT.add(j)
                iC += 1

    return iC
iC = 0
#iC += searchPair(aA1)
#iC += searchPair(aA0)
iC += searchPair(aA)
print(iC)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
aA = sorted([int(_) for _ in input().split()],reverse=True)
aA1 = [ _ for _ in aA if _ % 2 ]
aA0 = [ _ for _ in aA if _ % 2 == 0 ]


def searchPair(aD):
    iL = len(aD)
    dsT =set()
    iC = 0
    for i in range(iL):
        for j in range(i+1,iL):
            if i in dsT or j in dsT:
                continue
            iWa =  aD[i] + aD[j]
            if not ( iWa & (iWa - 1)):
                dsT.add(i)
                dsT.add(j)
                iC += 1

    return iC
iC = 0
iC += searchPair(aA1)
iC += searchPair(aA0)
print(iC)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
a = sorted(a,reverse = True)
def beki(s):
  k = math.log2(s)
  k = int(k) + 1
  return 2**k - s
def nib(x,s,i):
  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]),i)
  if nb is not None:
    del a[nb]
    c += 1
    r -= 1
  i += 1
    
print(c)

Submission status: Time Limit Exceeded

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 pair in a[k+1:]:
    count += 1
    a.pop(k)
  elif pair == i:
    pass
  elif pair in a:
    count += 1
    a.remove(pair)
print(count)

Submission status: Time Limit Exceeded

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,i):
  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]),i)
  if nb is not None:
    del a[nb]
    c += 1
    r -= 1
  i += 1
    
print(c)

Submission status: Time Limit Exceeded

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,i):
  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]),i)
  if nb is not None:
    a = a[0:nb] + a[nb+1:r]
    c += 1
    r -= 1
  i += 1
    
print(c)

Submission status: Time Limit Exceeded

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 = []
num= 0
if a_odds!=[] and a_even!=[]:
    num = max(a_odds[0],a_even[0])
elif a_odds ==[]:
    num= a_even[0]
elif a_even == []:
    num = a_odds[0]
    
for i in range(round(math.log2(num))+1,0,-1):
    alist.append(2**i)


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: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import combinations

def solve(N, As):
    data = {}
    for i, a in enumerate(As):
        data.setdefault(a, []).append(i)
    d_pairs = []
    counters = Counter()
    keys = list(sorted(data.keys()))
    for v in combinations(keys, 2):
        if bin(v[0] + v[1]).count("1") == 1:
            d_pairs.append((v[0], v[1]))
            counters.update([v[0]] * len(data[v[0]]))
            counters.update([v[1]] * len(data[v[1]]))
    for v in keys:
        if bin(v * 2).count("1") == 1:
            d_pairs.append((v, v))
            counters.update([v] * len(data[v]))
    cost = []
    for p in d_pairs:
        if p[0] != p[1]:
            c1 = counters[p[0]] if bin(p[0]).count("1") != 1 else 10 ** 10
            c2 = counters[p[1]] if bin(p[1]).count("1") != 1 else 10 ** 10
            cost.append((c1 + c2, p[0], p[1]))
        else:
            cost.append((10 ** 10 * 2 + 1, p[0], p[1]))
    ans = 0
    cost.sort()
    for cost_pair in sorted(cost):
        if cost_pair[1] != cost_pair[2]:
            while len(data[cost_pair[1]]) > 0 and len(data[cost_pair[2]]) > 0:
                ans += 1
                data[cost_pair[1]].pop()
                data[cost_pair[2]].pop()
        else:
            while len(data[cost_pair[1]]) > 1:
                ans += 1
                data[cost_pair[1]].pop()
                data[cost_pair[2]].pop()
    return ans

if __name__ == "__main__":
    N = input()
    As = [int(c) for c in input().split()]
    print(solve(N, As))

Submission status: Time Limit Exceeded

Solution code:
temp_len = int(input())
input_nums = [int(i) for i in input().split(" ")]
powers = [2**i for i in range(30)]
def powercount(nums):
    if (nums is None) or len(nums) < 2:
        return 0
    single = nums[0]
    others = nums[1:]
    toBePairs = [(i - single) for i in powers if (i - single) > 0]
    pairables = []
    for i in toBePairs:
        if i in others:
            tmp = others[:]
            tmp.remove(i)
            pairables.append(int(powercount(tmp) + 1))
    pairables.append(powercount(others))
    return max(pairables)
print(powercount(input_nums))

Submission status: Time Limit Exceeded

Solution code:
from math import log2, ceil
from bisect import bisect_right

N = int(input())
a = list(map(int, input().split()))
a = sorted(a)
b = [True for _ in range(N)]

ans = 0
for i in list(range(N))[::-1]:
    if not b[i]: continue
    t = a[i]
    flg = False
    left = log2(t)
    for j in list(range(ceil(left), int(1.414 + left) + 1))[::-1]:
        pair = 2 ** j - t
        right = bisect_right(a, pair)
        k = min(right, i - 1)
        while k >= 0:
            if a[k] < pair: break
            if a[k] == pair:
                if b[k]:
                    if k != i:
                        b[k] = False
                        b[i] = False
                        ans += 1
                        flg = True
                        break
            k -= 1
        if flg:
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
l=[]

i=0
maxt = 2 * 10**9
while 1:
    t = 2**i
    if t > maxt:
        break
    l.append(t)
    i += 1

#print(l)

def mymatch(n, aList):
    for i in range(0, len(aList)):
        if n == aList[i]:
            return True

    

num_of_list = input()
a_list = list(map(int,input().split()))
a_list.sort(reverse=True)
#print( a_list )
i = 0 
count = 0 

while len(a_list):
    #print( a_list )
    a = a_list.pop(0)
    #print("a: %d" % (a))
    for n in range(0, len(a_list)):
        #print( a_list[n] )
        if mymatch( a+a_list[n], l ):
            #print( "match!!!: %d" % (a_list[n]) )
            a_list.remove(a_list[n])
            count += 1
            break

print( count )

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect


def is_exist_b(search_list, target):
    low = 0
    high = len(search_list)
    if high == 0:
        return False
    index = (low + high) // 2
    while low <= high:
        if target == search_list[index]:
            break
        elif i > search_list[index]:
            low = index + 1
        elif i < search_list[index]:
            high = index - 1
        index = (low + high) // 2
    if target == search_list[index]:
        return True
    else:
        return False


def make_list(base, ceil):
    limit = ceil + base
    max_t = int(math.log2(limit))
    result = []
    for t in range(1, max_t + 2):
        can = 2**t - base
        if 0 < can <= ceil:
            result.append(can)
    return result


n = int(input())

nums = list(map(int, input().split()))
nums = sorted(nums)

combs = []
for i in range(n):
    for num in make_list(nums[i], nums[n - 1]):
        if is_exist_b(nums[i + 1:], num):
            combs.append((nums[i], num))

answer = 0
for i in range(len(combs)):
    existence = []
    for a, b in combs[i:]:
        if not (is_exist_b(existence, a) or is_exist_b(existence, b)):
            bisect.insort_left(existence, a)
            bisect.insort_left(existence, b)
    size = len(existence) // 2
    if size == n // 2:
        answer = size
        break
    if size > answer:
        answer = size

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import Counter


random_case =0
if not random_case:
    N = int(input())
    A = list(map(int , input().split()))
# A.sort()
else:
    import random
    A = [random.randint(1,10) for _ in range(7)]
    print(A)

beki = {2**i for i in range(32)}
beki_rlist = (([2**i for i in range(32)]))


def guchoku():
    max_ans = 0
    for tmp_a in itertools.permutations(A):
        tmp_ans = 0
        for i in range(len(A)//2):
            if tmp_a[2*i]+tmp_a[2*i+1] in beki:
                tmp_ans+=1
        max_ans = max(tmp_ans,max_ans)
    return max_ans


# print(guchoku())
# print("---")
ans = 0
c = Counter(A)
for i in reversed(sorted(c.keys())):
    for tmp in beki_rlist:
        if c[i]==0:
            break
        elif tmp == i*2:
            ans += c[i]//2
            c[i]-= c[i]//2 *2
        elif c[tmp-i]:
            val = min(c[i],c[tmp-i])
            c[i] -=val
            c[tmp-i]-=val
            ans +=val
print(ans)
# print(guchoku())
# print(c)
# print(ans==guchoku())

# print(c)

Submission status: Time Limit Exceeded

Solution code:
from math import log2, ceil
from bisect import bisect_right

N = int(input())
a = list(map(int, input().split()))
a = sorted(a)
b = [True for _ in range(N)]

ans = 0
for i in list(range(N))[::-1]:
    if not b[i]: continue
    t = a[i]
    flg = False
    left = log2(t)
    for j in list(range(ceil(left), int(1.414 + left) + 1))[::-1]:
        pair = 2 ** j - t
        right = bisect_right(a, pair)
        k = min(right, N - 1)
        while k >= 0:
            if a[k] < pair: break
            if a[k] == pair:
                if b[k]:
                    if k != i:
                        b[k] = False
                        b[i] = False
                        ans += 1
                        flg = True
                        break
            k -= 1
        if flg:
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = input()
a = list(map(int, input().split()))
a.sort(reverse=True)
count = 0
for i in a:
  pair = 2**(len(format(i,'b')))-i
  if pair == i and a.count(i)>1:
    count += 1
    a.remove(pair)
    a.remove(pair)
    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: Time Limit Exceeded

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
A.sort()
s=0
i=1
while i<=len(A)-1:
    a=int(math.log2(A[-i]))
    if 2**(a+1)-A[-i] in A[:-i]:
        s+=1
        A.remove(2**(a+1)-A[-i])
        i+=1
    else:
        i+=1
print(s)

Submission status: Time Limit Exceeded

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):
        t -= 1
        L = 0
        continue
    if A[-1] < (1 << (t-1)):
        t -= 1
        L = 0
        continue

    large = A.pop(-1)
    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: Time Limit Exceeded

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 = []
num= 0
if a_odds!=[] and a_even!=[]:
    num = max(a_odds[0],a_even[0])
elif a_odds ==[]:
    num= a_even[0]
elif a_even == []:
    num = a_odds[0]
    
for i in range(round(math.log2(num))+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: Time Limit Exceeded

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

squared = [2]
tmp = 2
while tmp < 2 * 10**9:
    tmp *= 2
    squared.append(tmp)

pairs = []
for i in range(N):
    for j in range(i+1, N):
        if A[i] + A[j] in squared:
            pairs.append([A[i], A[j]])

adopt = [format(i, 'b').rjust(len(pairs), '0') for i in range(2**len(pairs))]
max_pair = 0

for i in range(len(adopt)):
    num = []
    for j in range(len(pairs)):
        if adopt[i][j] == '1':
            num.append(pairs[j][0])
            num.append(pairs[j][1])
    if len(num) == len(set(num)) and len(num) > max_pair:
        max_pair = len(num) // 2

print(max_pair)

Submission status: Time Limit Exceeded

Solution code:
import copy 
import itertools

N = int(input())
A = list(map(int, input().split()))
bs = [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, 1073741824, 214748364]
A_dict = {}

for a in A:
    if a not in A_dict:
        A_dict[a] = 1
    else:
        A_dict[a] += 1

A_ = []
A_dict_c = copy.deepcopy(A_dict)
for a in A:
    A_dict_c[a] -= 1
    ad_c = copy.deepcopy(A_dict_c)
    for b in bs:
        key = b - a
        if key in A_dict:
            if ad_c[key] > 0:
                A_.append((min(a, key), max(a, key)))
                ad_c[key] -= 1

SETS = []
for i in range(1 << len(A_)):
    output = []
    for j in range(len(A_)):
        if ((i >> j) & 1) == 1:
            output.append(A_[j])
    SETS.append(output)


count = 0
A_dict_c = copy.deepcopy(A_dict)
for sets in SETS:
    if not sets:
        continue
    else:
        A_dict_c = copy.deepcopy(A_dict)
        sub_count = 0
        for pair in sets:
            if A_dict_c[pair[0]] > 0 and A_dict_c[pair[1]] > 0:
                sub_count += 1
                A_dict_c[pair[0]] -= 1
                A_dict_c[pair[1]] -= 1
            else:
                break
        if count < sub_count:
            count = sub_count
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

def dfs(v,visited):
  for u in m2[v]:
    if u in visited:
      continue
    visited.add(u)
    if(n2[u]==-1 or dfs(n2[u],visited)):
      n2[u]=v
      return True
  return False

n=int(input())
a=list(map(int,input().split()))
a.sort()
b=[]
kari=[]
ma=[]
m2=[]
n2=[]
vt=[]
vp=[]
visited=[]
ans=0
for i in range(n):
  kari=[]
  for j in range(20):
    for k in range(bisect.bisect_left(a,2**j-a[i]),bisect.bisect_right(a,2**j-a[i])):
      if(k==i):
        continue
      kari.append(k)
  ma.append(kari)
for i in range(n):
  kari=[]
  for j in ma[i]:
    kari.append(j+n)
  m2.append(kari)
for i in range(2*n):
  n2.append(-1)
print(sum(dfs(s,set())for s in range(n))//2)

Submission status: Time Limit Exceeded

Solution code:
from math import log2, ceil
from bisect import bisect_left, bisect_right

N = int(input())
a = list(map(int, input().split()))
a = sorted(a)
b = [True for _ in range(N)]

ans = 0
for i in list(range(N))[::-1]:
    if not b[i]: continue
    t = a[i]
    flg = False
    for j in list(range(ceil(log2(t)), int(log2(t * 2)) + 1))[::-1]:
        pair = 2 ** j - t
        left = bisect_left(a, pair)
        right = bisect_right(a, pair)
        # print(t, pair, a, b, left, right)
        if left == right:
            if left < N and left != i:
                if a[left] == pair and b[left]:
                    b[left] = False
                    b[i] = False
                    ans += 1
                    flg = True
                    break
        else:
            k = min(right - 1, N - 1)
            while k >= max(0, left):
                if a[k] != pair: break
                if b[k]:
                    if k != i:
                        b[k] = False
                        b[i] = False
                        ans += 1
                        flg = True
                        break
                k -= 1
            if flg:
                break

print(ans)

Submission status: Time Limit Exceeded

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 = 0
  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:
  p = beki(a[i]) 
  nb = nib(a[i+1:r],p)
  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: Time Limit Exceeded

Solution code:
import math


def is_exist_b(search_list, target):
    low = 0
    high = len(search_list)
    if high == 0:
        return False
    index = (low + high) // 2
    while low <= high:
        if target == search_list[index]:
            break
        elif i > search_list[index]:
            low = index + 1
        elif i < search_list[index]:
            high = index - 1
        index = (low + high) // 2
    if target == search_list[index]:
        return True
    else:
        return False


def make_list(base, ceil):
    limit = ceil + base
    max_t = int(math.log2(limit))
    result = []
    for t in range(1, max_t + 1):
        can = 2**t - base
        if 0 < can <= ceil:
            result.append(can)
    return result


n = int(input())

nums = list(map(int, input().split()))
nums = sorted(nums)

combs = []
for i in range(n):
    for num in make_list(nums[i], nums[n - 1]):
        if is_exist_b(nums[i + 1:], num):
            combs.append((nums[i], num))

answer = 0
for i in range(len(combs)):
    existence = []
    for a, b in combs[i:]:
        if not (a in existence or b in existence):
            existence.append(a)
            existence.append(b)
    size = len(existence) // 2
    if size > answer:
        answer = size

print(answer)