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 heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([-1*random.randint(1,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

ans=0
n=I()
a=sorted(LI())[::-1]
m=defaultdict(int)
for i in a:
    m[i]+=1
    
for i in a:
    t=len(bin(i))-2
    s=2**t-i
    if s in m:
        if (s==i and m[s]==1) or m[s]==0:
            continue
        else:
            m[s]-=1
            m[i]-=1
            ans+=1
    

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([-1*random.randint(1,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

ans=0
n=I()
a=sorted(LI())[::-1]
m={}
for i in a:
    m[i]=0
    
for i in a:
    t=len(bin(i))-2
    s=2**t-i
    if s in m:
        if m[s]==1:
            continue
        else:
            m[s]=1
            ans+=1

print(ans)

Submission status: Wrong Answer

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

c = Counter(A)
b = sorted(c.keys())

ret = 0
for j in range(len(c) - 1, -1, -1) :
    i = 2
    while c[b[j]] > 0 and i - b[j] <= b[j] :
        if b[j] != i - b[j] :
            if c[b[j]] > 0 and c[i-b[j]] :
                M = max(c[b[j]], c[i-b[j]])
                ret += M
                c[b[j]] -= M
                c[i-b[j]] -= M
        else :
            if c[b[j]] > 1 :
                ret += c[b[j]] // 2
                c[b[j]] %= 2
        i *= 2
    
print(ret)

Submission status: Wrong Answer

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

c = Counter(A)
b = sorted(c.keys())

ret = 0

i = 1 << 32
while i != 1 :
    j = len(b) - 1
    while j >= 0 and i - b[j] <= b[j] :
        if b[j] != i - b[j] :
            if c[b[j]] > 0 and c[i-b[j]] :
                M = max(c[b[j]], c[i-b[j]])
                ret += M
                c[b[j]] -= M
                c[i-b[j]] -= M
        else :
            if c[b[j]] > 1 :
                ret += c[b[j]] // 2
                c[b[j]] %= 2
        j -= 1
    i >>= 1
    
print(ret)

Submission status: Wrong Answer

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

c = Counter(A)
b = sorted(c.keys())

ret = 0

i = 1 << 32
while i != 1 :
    j = 0
    while j < len(b) and b[j] <= i - b[j] :
        if b[j] != i - b[j] :
            if c[b[j]] > 0 and c[i-b[j]] :
                M = max(c[b[j]], c[i-b[j]])
                ret += M
                c[b[j]] -= M
                c[i-b[j]] -= M
        else :
            if c[b[j]] > 1 :
                ret += c[b[j]] // 2
                c[b[j]] %= 2
        j += 1
    # print(i, c)
    i >>= 1
    
print(ret)

Submission status: Wrong Answer

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

c = Counter(A)
b = sorted(c.keys())

ret = 0

i = 2
while i <= b[-1] + b[-1] :
    j = 0
    tmp = 0
    while j < len(b) and b[j] <= i - b[j] :
        if b[j] != i - b[j] :
            tmp += c[b[j]] * c[i-b[j]]
        else :
            tmp += c[b[j]] * (c[b[j]] - 1)
        j += 1
    
    i *= 2
    ret = max(ret, tmp)
    
print(ret)

Submission status: Wrong Answer

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

c = Counter(A)
b = sorted(c.keys())

ret = 0

i = 2
while i <= A[-1] + A[-1] :
    j = 0
    tmp = 0
    while j < len(b) and b[j] <= i - b[j] :
        if b[j] != i - b[j] :
            tmp += c[b[j]] * c[i-b[j]]
        else :
            tmp += c[b[j]] * (c[b[j]] - 1)
        j += 1
    
    i *= 2
    ret = max(ret, tmp)
    
print(ret)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    bp = list(reversed([2**i for i in range(2, 32)]))
    C = Counter(A)
    ans = 0
    A.sort(reverse=True)
    for k in A:
        if C[k] <= 0:
            continue
        C[k] -= 1
        for b in bp:
            r = b-k
            if C[r] > 0:
                ans += 1
                C[r] -= 1
                break

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 2*(10**5)
    # # A = [random.randint(1, 10**9) for _ in range(N)]
    # A = list(range(1, N+1))
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    bp = list(reversed([2**i for i in range(2, 32)]))
    C = Counter(A)
    ans = 0
    A.sort(reverse=True)
    for k in A:
        if C[k] == 0:
            continue
        for b in bp:
            r = b-k
            if r <= 0:
                break
            if r == k:
                if C[k] >= 2:
                    ans += 1
                    C[k] -= 2
                    break
            elif C[r] > 0 and C[k] > 0:
                ans += 1
                C[r] -= 1
                C[k] -= 1
                break

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 2*(10**5)
    # # A = [random.randint(1, 10**9) for _ in range(N)]
    # A = list(range(1, N+1))
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    bp = list(reversed([2**i for i in range(2, 40)]))
    C = Counter(A)
    ans = 0
    A.sort(reverse=True)
    for k in A:
        if C[k] == 0:
            continue
        for b in bp:
            r = b-k
            if r <= 0:
                break
            if r == k:
                if C[k] >= 2:
                    ans += 1
                    C[k] -= 2
                    break
            elif C[r] > 0 and C[k] > 0:
                ans += 1
                C[r] -= 1
                C[k] -= 1
                break

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 2*(10**5)
    # # A = [random.randint(1, 10**9) for _ in range(N)]
    # A = list(range(1, N+1))
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    bp = list(reversed([2**i for i in range(2, 40)]))
    C = Counter(A)
    ans = 0
    A.sort(reverse=True)
    for k in A:
        if C[k] == 0:
            continue
        for b in bp:
            r = b-k
            if r == k:
                if C[k] >= 2:
                    ans += 1
                    C[k] -= 2
                    break
            elif C[r] > 0 and C[k] > 0:
                ans += 1
                C[r] -= 1
                C[k] -= 1
                break

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 2*(10**5)
    # # A = [random.randint(1, 10**9) for _ in range(N)]
    # A = list(range(1, N+1))
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    bp = list(reversed([2**i for i in range(2, 40)]))
    C = Counter(A)
    ans = 0
    A.sort(reverse=True)
    for k in A:
        for b in bp:
            r = b-k
            if r == k:
                if C[k] >= 2:
                    ans += 1
                    C[k] -= 2
                    break
            elif C[r] > 0 and C[k] > 0:
                ans += 1
                C[r] -= 1
                C[k] -= 1
                break

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 2*(10**5)
    # # A = [random.randint(1, 10**9) for _ in range(N)]
    # A = list(range(1, N+1))
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    bp = list(reversed([2**i for i in range(2, 40)]))
    C = Counter(A)
    K = list(C.keys())
    K.sort(reverse=True)
    ans = 0
    for k in K:
        if C[k] == 0:
            continue
        for b in bp:
            r = b-k
            if r == k:
                if C[k] >= 2:
                    ans += 1
                    C[k] -= 2
                    break
            elif C[r] > 0 and C[k] > 0:
                ans += 1
                C[r] -= 1
                C[k] -= 1
                break

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 2*(10**5)
    # # A = [random.randint(1, 10**9) for _ in range(N)]
    # A = list(range(1, N+1))
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    bp = list(reversed([2**i for i in range(2, 40)]))
    C = Counter(A)
    K = list(C.keys())
    K.sort(reverse=True)
    ans = 0
    for k in K:
        for b in bp:
            r = b-k
            if r == k:
                if C[k] >= 2:
                    ans += 1
                    C[r] -= 1
                    C[k] -= 1
                    break
            elif C[r] > 0 and C[k] > 0:
                ans += 1
                C[r] -= 1
                C[k] -= 1
                break

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 2*(10**5)
    # # A = [random.randint(1, 10**9) for _ in range(N)]
    # A = list(range(1, N+1))
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    bp = list(reversed([2**i for i in range(2, 40)]))
    C = Counter(A)
    K = list(C.keys())
    K.sort(reverse=True)
    ans = 0
    for k in K:
        for b in bp:
            r = b-k
            if r == k:
                if C[k] >= 2:
                    ans += 1
                    C[r] -= 1
                    C[k] -= 1
                    break
            elif C[r] > 0 and C[k] > 0:
                ans += 1
                C[r] -= 1
                C[k] -= 1
                break

    return ans


def main():
    # N = read_int()
    # A = read_int_n()
    # print(slv(N, A))

    N = 2*(10**5)
    # A = [random.randint(1, 10**9) for _ in range(N)]
    A = list(range(1, N+1))
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    bp = list(reversed([2**i for i in range(2, 40)]))
    C = Counter(A)
    K = list(C.keys())
    K.sort(reverse=True)
    ans = 0
    for k in K:
        for b in bp:
            r = b-k
            if r == k:
                if C[k] >= 2:
                    ans += 1
                    C[r] -= 1
                    C[k] -= 1
            elif C[r] > 0 and C[k] > 0:
                ans += 1
                C[r] -= 1
                C[k] -= 1

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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=[1]*n

for i in range(n-1,-1,-1):
  if a[i]==1:
    break
  if check[i]==1 and a[i] not in b:
    check[i]=0
    x=math.floor(math.log2(a[i]))
    x=b[x]-a[i]
    y=bisect.bisect_left(a,x)
    z=bisect.bisect_right(a,x)
    t=bisect.bisect_left(check[y:z],1)+y
    if t!=z:
      check[t]=0
      ct+=1

ctb=0
w=1
for i in range(n):
  if a[i] in b or a[i]==1:
    if a[i]==w:
      if check[i]==1:
        ctb+=1
    else:
      ct+=ctb//2
      w=a[i]
      if check[i]==1:
        ctb=1
  else:
    ct+=ctb//2
    ctb=0
ct+=ctb//2

print(ct)

Submission status: Wrong Answer

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=[1]*n

ctb=0
w=2
for i in range(n):
  if a[i] in b:
    if a[i]==w:
      ctb+=1
      check[i]=0
    else:
      ct+=ctb//2
      w=a[i]
      check[i]=0
      ctb=1
  else:
    ct+=ctb//2
    ctb=0
ct+=ctb//2

for i in range(n-1,-1,-1):
  if a[i]==1:
    break
  if check[i]==1:
    check[i]=0
    x=math.floor(math.log2(a[i]))
    x=b[x]-a[i]
    y=bisect.bisect_left(a,x)
    z=bisect.bisect_right(a,x)
    t=bisect.bisect_left(check[y:z],1)+y
    if t!=z:
      check[t]=0
      ct+=1

ct1=0
for j in range(i+1):
  if check[j]==1:
    ct1+=1
ct+=ct1//2

print(ct)

Submission status: Wrong Answer

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] and a[y]==x and check[y]==0:
      check[y]=1
      ct+=1
print(ct)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
p=max(a)*2
chk=[pow(2,i) for i in range(1,32) if pow(2,i)<=p]
ans=0
for i in a[::-1]:
    if d[i]>0:
        d[i]-=1
        for j in chk[::-1]:
            if j-i in d and d[j-i]>0:
                d[j-i]-=1
                ans+=1
                break
print(ans)

Submission status: Wrong Answer

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<0:
            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: Wrong Answer

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)

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

    #print (now,na,ind)

print (ans)

Submission status: Wrong Answer

Solution code:
#最大要素の相手は一意?

from collections import Counter
n = int(input())
a = list(map(int, input().split( )))
a_c = Counter(a)

a.sort(reverse = True)
ans = 0
for i in range(n):
    j = 0
    while 2**j<a[i]:
        j+=1
    if 2**j-a[i] in a_c and a_c[a[i]]:
        if a_c[2**j-a[i]]:
            a_c[2**j-a[i]] -= 1
            a_c[a[i]] -= 1#こっちも減らす
            ans += 1
    else:#test
        a_c[a[i]] -=1
print(ans)

Submission status: Wrong Answer

Solution code:
#最大要素の相手は一意?

from collections import Counter
n = int(input())
a = list(map(int, input().split( )))
a_c = Counter(a)

a.sort(reverse = True)
ans = 0
for i in range(n):
    j = 0
    while 2**j<a[i]:
        j+=1
    if 2**j-a[i] in a_c and a_c[a[i]]:
        if a_c[2**j-a[i]]:
            a_c[2**j-a[i]] -= 1
            a_c[a[i]] -= 1#こっちも等しい数と組になることがあるので減らす
            ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
#最大要素の相手は一意?

from collections import Counter
n = int(input())
a = list(map(int, input().split( )))
a_c = Counter(a)

a.sort(reverse = True)
ans = 0
for i in range(n):
    j = 0
    while 2**j<a[i]:
        j+=1
    if 2**j-a[i] in a_c and a_c[a[i]]:
        if a_c[2**j-a[i]]:
            a_c[2**j-a[i]] -= 1
            ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort(reverse = True)
d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

ans =0
for a in A:
    b = 2**(a.bit_length())-a
    if b in d:
        if d[b] >=1:
          if a == b and d[b] ==1:
            continue
          ans += 1 
          d[b]-= 1
          d[a]-= 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort(reverse = True)
d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

ans =0
for a in A:
    b = 2**(a.bit_length())-a
    if b in d:
        if d[b] >=1 and d[a] >= 1:
            ans += 1 
            d[b]-= 1
            d[a]-= 1

print(ans)

Submission status: Wrong Answer

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
    j=2**t-i
    if j in c and c[j]>0:
        ans+=1
        c[j]-=1
print(ans)

Submission status: Wrong Answer

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

#加えた工夫
# dequeにしてremoveをO(1)にした
# log2の計算をforにした