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:
from collections import Counter
N = int(input())
*l, = map(int, input().split())
c = Counter(l)
ks = c.keys()
ans = 0

for i in sorted(ks):
    while c[i]:
        for j in range(32)[::-1]:
            v = (2**j)-i
            if v in ks:
                if v!=i or (v==i and c[v]>=2):
                    c[v] -= 1
                    c[i] -= 1
                    ans += 1
                    break
        else:
            break


print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    d = {}
    for i in A:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    r = 0
    for i in A:
        if d[i] == 0:
            continue
        for j in reversed(range(1,32)):
            t = pow(2, j) - i
            if t == i:
                if d[t] > 1:
                    d[t] -= 2
                    r += 1
            elif t in d and d[t] > 0:
                d[t] -= 1
                d[i] -= 1
                r += 1
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from bisect import bisect_right

n = int(input())
a = [int(x) for x in input().split()]
a = sorted(a)

ans = 0
visited = [False]*n

while a:
    s = a.pop()
    if visited.pop():
        continue
    m = 1
    while m <= s:
        m *= 2
    r = bisect_right(a, m-s)
    l = bisect_left(a, m-s)
    if r-l > 0:
        a.pop(r-1)
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from bisect import bisect_right

n = int(input())
a = [int(x) for x in input().split()]
a = sorted(a)

ans = 0

while a:
    s = a.pop()
    m = 1
    while m <= s:
        m *= 2
    ind = bisect_right(a, m-s)
    if ind == 0:
        continue
    if a[ind-1] == m-s:
        a.pop(ind-1)
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    ans = 0
    A.sort(reverse=True)
    c = dict(Counter(A))

    for b in A:
        if c[b] == 0:
            continue
        a = (1 << b.bit_length()) - b
        if a == b:
            ans += c[b]//2
            c[b] %= 2
        else:
            if a in c.keys() and c[a] > 0:
                cur = min(c[a], c[b])
                ans += cur
                c[b] -= cur
                c[a] -= cur
        # print(a, b, c, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)

    for b in A:
        if c[b] == 0:
            continue
        a = (1 << b.bit_length()) - b
        if a == b:
            ans += c[b]//2
            c[b] %= 2
        else:
            if a in c.keys() and c[a] > 0:
                cur = min(c[a], c[b])
                ans += cur
                c[b] -= cur
                c[a] -= cur
        # print(a, b, c, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
n= int(input())
lis= list(map(int,input().split()))
lis.sort(reverse=True)
ans=0
while lis:
  a =lis.pop(0)
  num = 2**math.ceil(math.log(a,2))-a
  if num==0:num=a
  if num in lis:
    lis.remove(num)
    ans +=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

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

"""

2べきになる条件は？
→片方が2の補数であること

Nが大きい→貪欲的に
最大の奴はそれより小さい奴としかペアを組めない
→大きい奴から貪欲にとっけいけばいける？

いけそうかなぁ
"""

A.sort()
An = []
for i in range(N):
    if i == 0 or An[-1][0] != A[i]:
        An.append([ A[i] , 1 ])
    else:
        An[-1][1] += 1

import bisect
ans = 0

#print (An)

for i in range(len(An)-1,-1,-1):

    for j in range(An[i][1]):

        An[i][1] -= 1

        for k in range(30,-1,-1):
            if 2**k <= An[i][0]:
                continue

            ind = bisect.bisect_left(An,[2**k - An[i][0],0])
            if ind < len(An) and An[ind][0] == 2**k - An[i][0] and An[ind][1] > 0:
                An[ind][1] -= 1
                ans += 1
                break

print (ans)

Submission status: Time Limit Exceeded

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

A.sort()
used = [0]*N

import bisect

ans = 0
for i in range(N-1, -1, -1):
    if used[i] == 1:
        continue
    num = pow(2, len(bin(A[i]))-2) - A[i]
    idx = bisect.bisect_left(A, num)
    while idx < i and used[idx] == 1:
        idx += 1
    if A[idx] == num and idx < i:
        ans += 1
        used[idx] = 1
        used[i] = 1

print(ans)

Submission status: Time Limit Exceeded

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

A.sort()
used = [0]*N

import bisect

ans = 0
for i in range(N-1, -1, -1):
    if used[i] == 1:
        continue
    for j in range(32):
        if A[i] < pow(2, j) <= 2*A[i]:
            num = pow(2, j) - A[i]
            break
    idx = bisect.bisect_left(A, num)
    while idx < i and used[idx] == 1:
        idx += 1
    if A[idx] == num and idx < i:
        ans += 1
        used[idx] = 1
        used[i] = 1

print(ans)

Submission status: Time Limit Exceeded

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

    print(sum)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists,reverse=True)
from collections import Counter
dic=dict(Counter(lists))

ans=0
howmuch=[[] for i in range(30)]
for num in lists:
    c=0
    while num%2==0:
        num=num//2
        c+=1
    howmuch[c].append(num)
for i in range(30):
    if len(howmuch[i])<=1:
        pass
    else:
        dic=dict(Counter(howmuch[i]))
        for some in howmuch[i]:
            for j in range(1,30):
                if 2**j-some in dic.keys() and dic[some]>0 and dic[2**j-some]>0:
                    if some!=2**(j-1):
                        m=min(dic[some],dic[2**j-some])
                        dic[some]-=m
                        dic[2**j-some]-=m
                        ans+=m
                    elif some==2**(j-1):
                        ans+=dic[some]//2
                        dic[some]=dic[some]%2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
lis=list(map(int,input().split()))
lis.sort(reverse=True)
dic={}
i=0
for x in lis:
    dic[i]=x
    i+=1

sum=0
i=0
while i<N:
    if dic[i]==0:
        i+=1
        continue
    else:
        first=dic.get(i)
        dic[i]=0
        i+=1
        k=1
        while(pow(2,k)<=first):
            k+=1
        second=pow(2,k)-first
        if second in dic.values():
            #print(first,"hhhh")
            for key,value in dic.items():
                if value==second:
            #        print("zhhhh")
                    dic[key]=0
                    sum+=1
                    break
        #print(dic)
print(sum)
#print(lis)

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
lis=list(map(int,input().split()))
lis.sort()
dic={}
i=1
for x in lis:
    dic[i]=x
    i+=1
sum=0
while N>0:
    if dic[N]==0:
        N-=1
        continue
    else:
        first=dic.get(N)
        #print("$",first)
        dic[N]=0
        #print(dic)
        N-=1
        k=2
        while(k<=first):
            k*=2
        second=k-first
        for key,value in dic.items():
         #   print(second)
            if value==second:
          #      print("wahhhhh")
                dic[key]=0
           #     print(dic)
                sum+=1
                break
print(sum)
#print(lis)

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
lis=list(map(int,input().split()))
lis.sort()
sum=0
while N>0:
    first=lis[N-1]
    k=2
    while(k<=first):
        k*=2
    del lis[N-1]
    N-=1
    second=k-first
    if lis.count(second)!=0:
        sum+=1
        N-=1
        del lis[lis.index(second)]
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
lis=list(map(int,input().split()))
lis.sort(reverse=True)
#print(lis)
sum=0
while N>0:
    first=lis[0]
    k=0
    while(pow(2,k)<=first):
        k+=1
 #       print("@",pow(2,k))
    del lis[0]
    second=pow(2,k)-first
 #   print(first,second)
    if lis.count(second)!=0:
        sum+=1
        N-=1
        del lis[lis.index(second)]
#    print(lis)
    N-=1
print(sum)
#print(lis)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
cnt = 0
l = []
flag = False
for i in range(N):
  #print("check:", A[i])
  for j in l:
    if not (A[i]+j) & (A[i]+j-1):
      #print(A[i], j)
      l.remove(j)
      cnt += 1
      flag = True
      break
  if flag == False:
    l.append(A[i])
  else:
    flag = False
 
print(cnt)
#print(l)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
cnt = 0
hist = [0 for _ in range(N)]
for i in range(N-1,0,-1):
    if hist[i]==0:
        a = A[i]
        k = 0
        while 2**k<=a:
            k += 1
        b = 2**k-a
        ind = bisect_left(A,b)
        if ind<i and A[ind]==b and hist[ind]==0:
            hist[i]=1
            hist[ind]=1
            cnt += 1
        elif ind<i and A[ind]==b and hist[ind]==1:
            ind += 1
            while A[ind]==b and ind<i:
                if hist[ind]==0:
                    hist[i]=1
                    hist[ind]=1
                    cnt += 1
                    break
                ind += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
cnt = 0
hist = [0 for _ in range(N)]
for i in range(N-1,0,-1):
    if hist[i]==0:
        a = A[i]
        k = 0
        while 2**k<=a:
            k += 1
        b = 2**k-a
        ind = bisect_left(A[:i],b)
        if ind<i and hist[ind]==0:
            hist[i]=1
            hist[ind]=1
            cnt += 1
        elif ind<i and hist[ind]==1:
            ind += 1
            while A[ind]==b and ind<i:
                if hist[ind]==0:
                    hist[i]=1
                    hist[ind]=1
                    cnt += 1
                    break
                ind += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
cnt = 0
hist = [0 for _ in range(N)]
for i in range(N-1,0,-1):
    if hist[i]==0:
        a = A[i]
        k = 0
        while 2**k<=a:
            k += 1
        b = 2**k-a
        ind = bisect_left(A[:i],b)
        if ind<i and hist[ind]==0:
            hist[i]=1
            hist[ind]=1
            cnt += 1
        elif ind<i and hist[ind]==1:
            ind += 1
            while A[ind]==b:
                if hist[ind]==0:
                    hist[i]=1
                    hist[ind]=1
                    cnt += 1
                    break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
input()
a = [int(x) for x in input().split()]
a.sort()
pair_cnt = 0
while len(a) >= 2:
    x = a.pop()
    if (2 ** x.bit_length() - x) in a:
        a.remove(2 ** x.bit_length() - x)
        pair_cnt += 1
print(pair_cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort(reverse = True)
    M = max(A)
    ex = [0 for _ in range(M+1)]
    for i in range(N):
        ex[A[i]] += 1
        
    
    def exp(x):
        l = len(str(bin(x))[2:])
        return 2**l

    ans = 0
    for i in range(N):
        use = A[i]
        if ex[use] == 0:
            continue
        ex[use] -= 1
        pare = exp(use)-use
        if ex[pare] != 0:
            ex[pare] -= 1
            ans += 1
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort(reverse = True)
    M = max(A)
    ex = [0 for _ in range(M+1)]
    for i in range(N):
        ex[A[i]] += 1
        
    
    def exp(x):
        ans = 1
        while x >= ans:
            ans *= 2
        return ans

    ans = 0
    for i in range(N):
        use = A[i]
        if ex[use] == 0:
            continue
        ex[use] -= 1
        pare = exp(use)-use
        if ex[pare] != 0:
            ex[pare] -= 1
            ans += 1
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ball = list(map(int, input().split()))
ball.sort(reverse = True)
dic = {}
for i in range(ball[0] + 1):
    dic[i] = 0
for x in ball:
    dic[x] += 1

ans = 0
for x in ball:
    if dic[x] != 0:
        y = 2**(x.bit_length()) - x
        if dic[y] != 0:
            if y == x and dic[y] == 1: 
                continue
            ans += 1
            dic[x] -= 1
            dic[y] -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input=sys.stdin.readline
k=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
i=0
n=k
while i<n:
    s=l[-1]
    b=1
    while b<=s:
        b*=2
    g=b-s
    p=bisect.bisect_left(l,g)
    if p==len(l)-1:
        l.pop(-1)
        i+=1
        continue
    else:
        if l[p]==g:
            l.pop(-1)
            l.pop(p)
            i+=2
            ans+=1
        else:
            l.pop(-1)
            i+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
i=0
while i<n:
    s=l[n-i-1]
    b=1
    while b<=s:
        b*=2
    g=b-s
    p=bisect.bisect_left(l[:n-i-1],g)
    if p==n-i-1:
        i+=1
        continue
    else:
        if l[p]==g:
            l.pop(n-i-1)
            l.pop(p)
            i+=2
            ans+=1
        else:
            i+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
i=0
while i<n:
    s=l[n-i-1]
    b=1
    while b<=s:
        b*=2
    g=b-s
    p=bisect.bisect_left(l[:n-i-1],g)
    if p==n-i-1:
        i+=1
        continue
    else:
        if l[p]==g:
            l.pop(n-i-1)
            l.pop(p)
            i+=2
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import itertools
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while True:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
while i>0:
    b=bisect_left(A,B[i])
    if A[b]==B[i] and b!=i:
        A.pop(b)
        B.pop(b)
        count+=1
        i-=2
    else:
        A=A[:i]
        B=B[:i]
        i-=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while True:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
while i>0:
    b=bisect_left(A,B[i])
    if A[b]==B[i] and b!=i:
        A=A[:b]+A[b+1:i]
        B=B[:b]+B[b+1:i]
        count+=1
        i-=2
    else:
        A=A[:i]
        B=B[:i]
        i-=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import itertools
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while True:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
while i>0:
    b=bisect_left(A,B[i])
    if A[b]==B[i] and b!=i:
        A=list(itertools.chain(A[:b],A[b+1:i]))
        B=list(itertools.chain(B[:b],B[b+1:i]))
        count+=1
        i-=2
    else:
        A=A[:i]
        B=B[:i]
        i-=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import math
  import bisect
  #import collections
  import sys
  input = sys.stdin.readline

  N = int(input())
  A = list(map(int,input().split()))
  #C = collections.Counter(A)
  C = {}
  for a in A:
    if a in C:
      C[a] += 1
    else:
      C[a] = 1
  A = sorted(list(C.keys()))
  #print(C)
  #print(A)

  ans = 0
  for i in range(len(A)-1,-1,-1):
    a = A[i]
    b = (1<<(int(math.log(a,2))+1))-a
    if a == b:
      ans += C[a]//2
      C[a] -= C[a]//2*2
    else:
      r = bisect.bisect_left(A[:i], b)
      if r < i and A[r] == b:
        mn = min(C[a],C[A[r]])
        ans += mn
        C[a] -=  mn
        C[A[r]] -= mn
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
#C = collections.Counter(A)
C = {}
for a in A:
  if a in C:
    C[a] += 1
  else:
    C[a] = 1
A = sorted(list(C.keys()))
#print(C)
#print(A)

ans = 0
for i in range(len(A)-1,-1,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  if a == b:
    ans += C[a]//2
    C[a] -= C[a]//2*2
  else:
    r = bisect.bisect_left(A[:i], b)
    if r < i and A[r] == b:
      mn = min(C[a],C[A[r]])
      ans += mn
      C[a] -=  mn
      C[A[r]] -= mn
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
import collections

N = int(input())
A = sorted(list(map(int,input().split())))
C = collections.Counter(A)
A = sorted(list(C.keys()))
#print(C)
#print(A)

ans = 0
for i in range(len(A)-1,-1,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  if a == b:
    ans += C[a]//2
    C[a] -= C[a]//2*2
  else:
    r = bisect.bisect_left(A[:i], b)
    if r < i and A[r] == b:
      mn = min(C[a],C[A[r]])
      ans += mn
      C[a] -=  mn
      C[A[r]] -= mn
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
A = sorted(list(C.keys()))
#print(C)
#print(A)

ans = 0
for i in range(len(A)-1,-1,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  if a == b:
    ans += C[a]//2
    C[a] -= C[a]//2*2
  else:
    r = bisect.bisect_left(A[:i], b)
    if r < i and A[r] == b:
      mn = min(C[a],C[A[r]])
      ans += mn
      C[a] -=  mn
      C[A[r]] -= mn
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
A = sorted(list(C.keys()))
#print(C)
#print(A)

ans = 0
for i in range(len(A)-1,-1,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  r = bisect.bisect_left(A[:i+1], b)
  #print(i,a,b,r)
  if r <= i and A[r] == b:
    if a == A[r]:
      ans += C[a]//2
      C[a] -= C[a]//2*2
    else:
      mn = min(C[a],C[A[r]])
      ans += mn
      C[a] -=  mn
      C[A[r]] -= mn
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import math
  import bisect
  import sys
  input = sys.stdin.readline

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

  ans = 0
  while(len(A)>1):
    a = A.pop()
    b = (1<<(int(math.log(a,2))+1))-a
    #print(a,b)
    r = bisect.bisect_left(A, b)
    if r < len(A) and A[r] == b:
      ans += 1
      del A[r]
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

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

ans = 0
while(len(A)>1):
  a = A.pop()
  b = (1<<(int(math.log(a,2))+1))-a
  #print(a,b)
  r = bisect.bisect_left(A, b)
  if r < len(A) and A[r] == b:
    ans += 1
    del A[r]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

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

ans = 0
while(len(A)>1):
  a = A[-1]
  del A[-1]
  b = (1<<(int(math.log(a,2))+1))-a
  #print(a,b)
  r = bisect.bisect_left(A, b)
  if r < len(A) and A[r] == b:
    ans += 1
    del A[r]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

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

ans = 0
while(len(A)>1):
  a = A[-1]
  A = A[:-1]
  b = (1<<(int(math.log(a,2))+1))-a
  #print(a,b)
  r = bisect.bisect_left(A, b)
  if r < len(A) and A[r] == b:
    ans += 1
    if r == 0:
      A = A[1:]
    elif r == len(A)-1:
      A = A[:r]
    else:
      A = A[:r]+A[r+1:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=[]
for i in range(1,50):
  b.append(2**i)
ct=0
check=[0]*n
for i in range(n-1,-1,-1):
  if check[i]==0:
    check[i]=1
    x=math.floor(math.log2(a[i]))
    x=b[x]-a[i]
    y=bisect.bisect_left(a,x)
    z=bisect.bisect_right(a,x)
    if a[y]==x:
      if check[y]==0:
        check[y]=1
        ct+=1
      else:
        for j in range(y,z):
          if a[j]==x and check[j]==0:
            check[j]=1
            ct+=1
            break
print(ct)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=[]
for i in range(1,50):
  b.append(2**i)
ct=0
check=[0]*n
for i in range(n-1,-1,-1):
  if check[i]==0:
    check[i]=1
    x=math.floor(math.log2(a[i]))
    x=b[x]-a[i]
    y=bisect.bisect_left(a,x)
    if a[y]==x:
      if check[y]==0:
        check[y]=1
        ct+=1
      else:
        while a[y]==x:
          if a[y]==x and check[y]==0:
            check[y]=1
            ct+=1
            break
          y+=1
          if y==n:
            break
print(ct)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.append(-float("inf"))
n = len(A)

A.sort()
s = 2
while s <= A[-1]+A[-2]:
    s *= 2
s //= 2

U = [0] * n

ans = 0
while s > 0:
    ll = 0
    rr = n-1
    while rr >= 1 and rr-ll >= 2:
        # print("rr",rr,"ll",ll)
        t = s - A[rr]
        if t>s:
            break
        # print("s",s,"t",t)
        l = ll
        r = rr-1
        m = (r+l)//2
        while r-l > 1:
            # print("r",r,"l",l,"m",m)
            if A[m] >= t:
                r = m
            else:
                l = m
            m = (r+l)//2
        if A[l+1] == t:
            ans += 1
            U[l+1] = 1
            U[rr] = 1
            # print(ans)
            A[l+1] = -float("inf")
        ll = l
        rr -= 1
        # print(A)
    s //= 2

    B = []
    for i in range(len(A)):
        if U[i] == 0:
            B.append(A[i])
    A = B
    n = len(A)
    U = [0] * n
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.append(-float("inf"))
n = len(A)

A.sort()
s = 2
while s <= A[-1]+A[-2]:
    s *= 2
s //= 2

U = [0] * n

ans = 0
while s > 0:
    ll = 0
    rr = n-1
    while rr >= 1 and rr-ll >= 2:
        # print("rr",rr,"ll",ll)
        t = s - A[rr]
        # print("s",s,"t",t)
        l = ll
        r = rr-1
        m = (r+l)//2
        while r-l > 1:
            # print("r",r,"l",l,"m",m)
            if A[m] >= t:
                r = m
            else:
                l = m
            m = (r+l)//2
        if A[l+1] == t:
            ans += 1
            U[l+1] = 1
            U[rr] = 1
            # print(ans)
            A[l+1] = -float("inf")
        ll = l
        rr -= 1
        # print(A)
    s //= 2

    B = []
    for i in range(len(A)):
        if U[i] == 0:
            B.append(A[i])
    A = B
    n = len(A)
    U = [0] * n
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import bisect

"""
def wantp(n):

    wq = []
    while p[n] != n:
        wq.append(n)
        n = p[n]

    for i in wq:
        p[i] = n

    return n
"""


N = int(input())

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

"""
p = [i for i in range(N)]
rank = [1] * N
"""
used = [False] * N
ans = 0

for i in range(N):

    i = N - 1 - i
    now = 2 ** 33

    while A[i] * 2 < now:
        now //= 2

    na = A[-1]
    del A[-1]

    if used[i]:
        continue

    ind = bisect.bisect_left(A,now-na)

    while ind < i and used[ind] and na + A[ind] == now:
        ind += 1

    if ind < i and na + A[ind] == now:
        used[ind] = True
        ans += 1

    #print (now,na,ind)

print (ans)

Submission status: Time Limit Exceeded

Solution code:

import bisect

"""
def wantp(n):

    wq = []
    while p[n] != n:
        wq.append(n)
        n = p[n]

    for i in wq:
        p[i] = n

    return n
"""


N = int(input())

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

"""
p = [i for i in range(N)]
rank = [1] * N
"""
used = [False] * N
ans = 0

for i in range(N):

    i = N - 1 - i
    now = 2 ** 33

    while A[i] * 2 < now:
        now //= 2

    na = A[-1]
    del A[-1]

    if used[i]:
        continue

    ind = bisect.bisect_left(A,now-na)

    while ind < i and used[ind]:
        ind += 1

    if ind < i and na + A[ind] == now:
        used[ind] = True
        ans += 1

    #print (now,na,ind)

print (ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int,input().split()))
a_=sorted(a,key=lambda x:-x)
ans=0
from collections import Counter
c=Counter(a_)
for i in a_:
    if c[i]==0:
        continue
    c[i]-=1
    for n in range(i):
        if i<2**n:
            t=n
            break
        elif i==2**n:
            t=n+1
            break
    j=2**t-i
    if j in c and c[j]>0:
        ans+=1
        c[j]-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int,input().split()))
a_=sorted(a)
ans=0
while len(a_)>1:#1になった時点で終わり。
    x,y=0,0
    for n in range(a_[-1]):
        if a_[-1]<=2**n:
            t=n
            break
    if 2**t==a_[-1]:
    #これは、2,4,8とか2のべき乗だけが引っかかる条件
        if a_[-1]==a_[-2]:
        #2のべきでも、きちんと2個存在するならおｋ
            a_.pop()
            a_.pop()
            ans+=1
        else:
            a_.pop()
    else:
        x+=a_[-1]
        y+=2**t-a_[-1]
        #inが遅すぎるかもしれない。ちょっと高速化
        #上で被りうる奴は排除できている。
        for j in range(1,len(a_)+1):
            if y==a_[-j]:
                ans+=1
                a_.pop(-j)
                a_.pop()
                break
            elif y<a_[-j]:#常に下回るときを考慮できていなかった
                if j==len(a_):
                    a_.pop()
            else:
                a_.pop()
                break
        
                #可能性なしがわかったらすぐ切る！！
print(ans)
#removeって探して削除なので遅い。popに変更してみよう
#forにしたことでインデックスも取得できるので。