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: Runtime Error

Solution code:
import math
N=int(input())
lis=list(map(int,input().split()))
lis.sort()
dic={}
i=0
for x in lis:
    dic[i]=x
    i+=1
lis=[]
for i in range(1,27):
    lis.append(pow(2,i))
sum=0
i=N-1
while i>=0:
    if dic[i]==0:
        i-=1
        continue
    else:
        first=dic.get(i)
        dic[i]=0
        i-=1
        k=0
        while(lis[k]<=first):
            k+=1
        second=lis[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: Runtime Error

Solution code:
from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
G = {}
for i in range(N-1,0,-1):
    a = A[i]
    kmin = 0
    while 2**kmin<=a:
        kmin += 1
    kmax = 0
    while 2**kmax<=2*a:
        kmax += 1
    for k in range(kmin,kmax):
        b = 2**k-a
        ind = bisect_left(A[:i],b)
        if A[ind]==b and ind<i:
            if 2**k not in G:
                G[2**k] = []
            G[2**k].append((i,ind))
            ind += 1
            while A[ind]==b:
                G[2**k].append((i,ind))
                ind += 1
C = sorted([[a,len(G[a])] for a in G],key=lambda x:x[1],reverse=True)
hist = [0 for _ in range(N)]
cnt = 0
for c in C:
    a,_ = c
    for x in G[a]:
        i,j = x
        if hist[i]==0 and hist[j]==0:
            cnt += 1
            hist[i] = 1
            hist[j] = 1
print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
ball = list(map(int, input().split()))
ball.sort(reverse = True)
ok = {}
for x in ball:
    if x in ok:
        dic[x] += 1
    else:
        dic[x] = 1
ans = 0
for x in ball:
    if ok[x] != 0:
        y = 2**(x.bit_length()) - x
        if ok[y] != 0:
            if y == x and ok[y] == 1: 
                continue
            ans += 1
            dic[x] -= 1
            dic[y] -= 1
print(ans)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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):
        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: Runtime Error

Solution code:
import bisect
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):
        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: Runtime Error

Solution code:
#[allow(unused_macros)]
macro_rules! input_byline {
    ($($r:tt)* ) => {
        let stdin = std::io::stdin();
        let mut q = std::collections::VecDeque::new();
        let mut next = || {
            if q.is_empty() {
                let mut s = String::new();
                stdin.read_line(&mut s);
                for v in s.split_whitespace() {
                    q.push_back(v.to_string());
                }
            }
            q.pop_front().unwrap()
        };
        input_inner!{next, $($r)*}
    };

}

#[allow(unused_macros)]
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

trait Printable {
    fn p(&self);
}

impl<T: std::fmt::Display> Printable for T {
    fn p(&self) {
        println!("{}", self);
    }
}

impl<T: std::fmt::Display> Printable for [T] {
    fn p(&self) {
        for i in 0..self.len() {
            if i != 0 {
                print!(" ");
            }
            print!("{}", self[i]);
        }
        println!("");
    }
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap};

#[allow(dead_code)]
type Graph = Vec<Vec<usize>>;
#[allow(dead_code)]
const M: usize = 1e9 as usize + 9;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }

    let mut cnt = HashMap::new();

    for i in 0..n {
        *cnt.entry(a[i]).or_insert(0) += 1;
    }

    let mut v = cnt.keys().cloned().collect::<Vec<_>>();
    v.sort();
    v.reverse();

    let mut ans = 0;

    for i in 0..v.len() {
        let mut x = 1;
        if *cnt.get(&v[i]).unwrap() == 0 {
            continue;
        }
        while x <= v[i] {
            x *= 2;
        }
        let nx = x - v[i];
        if v[i] == nx {
            let c = *cnt.get_mut(&v[i]).unwrap();
            ans += c / 2;
            continue;
        }
        let add = min(*cnt.get(&v[i]).unwrap(), *cnt.get(&nx).unwrap_or(&0));
        if add > 0 {
            *cnt.get_mut(&v[i]).unwrap() -= add;
            *cnt.get_mut(&nx).unwrap() -= add;
            ans += add;
        }
    }
    println!("{}", ans);
}

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left

N = I()
A = III()

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

for i in range(N)[::-1]:
    s = math.floor(math.log2(2*A[i]))
    p = bisect_left(A, 2**s-A[i])
    if p<=N-1 and A[p]==2**s-A[i] and p!=i and used[p]==False and used[i]==False:
        ans += 1
        used[p],used[i] = True, True

print(ans)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
l = sorted(list(map(int,input().split())))
c = 0
b = {}
for i in range(len(l)):
    if l[i] in b:
        b[l[i]] += 1
    else:
        b[l[i]] = 1

for i in range(len(l) - 1, -1, -1):
    if  b[l[i]] == 0:
        continue
    t = l[i]
    b[l[i]] -= 1
    s = 2 ** math.floor(math.log2(temp))
    st = 2*s - t 
    if l == []:
        break
    if st in b and b[st] > 0:
        b[2 * s - t] -= 1
        c += 1
print(c)

Submission status: Runtime Error

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

j = len(b) - 1
for j in range(N - 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: Runtime Error

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(30):
  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:
        ctb=0
  else:
    ct+=ctb//2
    ctb=0
ct+=ctb//2

print(ct)

Submission status: Runtime Error

Solution code:
import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n-1):
    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:
        continue
    else:
        if l[p]==g:
            l.pop(n-i-1)
            l.pop(p)
            n-=2
            ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self,data):
        self.data=data
        self.left=None
        self.right=None
class BST:
    def __init__(self,number_list):
        self.root=None
        for node in number_list:
            self.insert(node)
    def insert(self,data):
        n=self.root
        if n is None:
            self.root=Node(data)
            return
        else:
            while True:#これ抜けてた。やばい。
                entry=n.data
                if data<entry:
                    if n.left is None:
                        n.left=Node(data)
                        return
                    n=n.left
                elif data>entry:
                    if n.right is None:
                        n.right=Node(data)
                        return
                    n=n.right
                else:
                    n.data=data
                    return
    def search(self,target):
        n = self.root
        if n is None:
            return None
        else:#深さ優先探索
            lst = []
            lst.append(n)
            while len(lst) > 0:
                node = lst.pop()
                if node is None:
                    return False
                elif node.data == target:
                    self.node_recreate(node)
                    node=None
                    return True
                elif node.data < target :
                    lst.append(node.right)
                elif node.data > target:
                    lst.append(node.left)
            return False
        
    def node_recreate(self,node):
        #ノード再作成機能を装着
        num_lst=[]
        node_lst=[node]
        while len(node_lst)>0:
            node_=node_lst.pop()
            if node_.right is not None:
                node_lst.append(node_.right)
                num_lst.append(node_.right.data)
            if node_.left is not None:
                node_lst.append(node_.left)
                num_lst.append(node_.left.data)
        for num in num_lst:
            self.insert(num)
            
                
    
import math
N=int(input())
a=list(map(int,input().split()))
t_max=int(math.log2(max(a)*2)+1)
ans=0
bst=BST(a)
for t in range(t_max,0,-1):
    i=0
    while i<len(a):
    #forだとout of rangeしてしまうので。
        x,y=0,0
#         bst=BST(a)#二分木も更新しないと。
#更新を削除に変更。大分計算回数は減るはず。
        if bst.search(2**t-a[i]):
            if a[i]!=2**t-a[i]:
                #同じだったらNG
                ans+=1
                x+=a[i]
                y+=2**t-a[i]
                #IDを共有すると、インデックスがずれる。
                a.remove(x)
                bst.search(x)#削除を兼ねて
                print(bst.search(y))
                print(x,y)
                a.remove(y)
            else:
                i+=1#これ忘れてた....sampleも通らないよ
        else:
            i+=1 #ペアが見つからなかったときだけ進めばいい。
print(ans)

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self,data):
        self.data=data
        self.left=None
        self.right=None
class BST:
    def __init__(self,number_list):
        self.root=None
        for node in number_list:
            self.insert(node)
    def insert(self,data):
        n=self.root
        if n is None:
            self.root=Node(data)
            return
        else:
            while True:#これ抜けてた。やばい。
                entry=n.data
                if data<entry:
                    if n.left is None:
                        n.left=Node(data)
                        return
                    n=n.left
                elif data>entry:
                    if n.right is None:
                        n.right=Node(data)
                        return
                    n=n.right
                else:
                    n.data=data
                    return
    def search(self,target):
        n = self.root
        if n is None:
            return None
        else:#深さ優先探索
            lst = []
            lst.append(n)
            while len(lst) > 0:
                node = lst.pop()
                if node is None:
                    return False
                if node.data == target:
                    self.node_recreate(node)
                    return True
                elif node.data < target :
                    lst.append(node.right)
                elif node.data > target:
                    lst.append(node.left)
            return False
        
    def node_recreate(self,node):
        #ノード再作成機能を装着
        num_lst=[]
        node_lst=[node]
        while len(node_lst)>0:
            node_=node_lst.pop()
            if node_.right is not None:
                node_lst.append(node_.right)
                num_lst.append(node_.right.data)
            if node_.left is not None:
                node_lst.append(node_.left)
                num_lst.append(node_.left.data)
        node=None
        for num in num_lst:
            self.insert(num)
            
                
    
import math
N=int(input())
a=list(map(int,input().split()))
t_max=int(math.log2(max(a)*2)+1)
ans=0
bst=BST(a)
for t in range(t_max,0,-1):
    i=0
    while i<len(a):
    #forだとout of rangeしてしまうので。
        x,y=0,0
#         bst=BST(a)#二分木も更新しないと。
#更新を削除に変更。大分計算回数は減るはず。
        if bst.search(2**t-a[i]):
            if a[i]!=2**t-a[i]:
                #同じだったらNG
                ans+=1
                x+=a[i]
                y+=2**t-a[i]
                #IDを共有すると、インデックスがずれる。
                a.remove(x)
                bst.search(x)#削除を兼ねて
                a.remove(y)
            else:
                i+=1#これ忘れてた....sampleも通らないよ
        else:
            i+=1 #ペアが見つからなかったときだけ進めばいい。
print(ans)

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self,data):
        self.data=data
        self.left=None
        self.right=None
class BST:
    def __init__(self,number_list):
        self.root=None
        for node in number_list:
            self.insert(node)
    def insert(self,data):
        n=self.root
        if n is None:
            self.root=Node(data)
            return
        else:
            while True:#これ抜けてた。やばい。
                entry=n.data
                if data<entry:
                    if n.left is None:
                        n.left=Node(data)
                        return
                    n=n.left
                elif data>entry:
                    if n.right is None:
                        n.right=Node(data)
                        return
                    n=n.right
                else:
                    n.data=data
                    return
    def search(self,target):
        n = self.root
        if n is None:
            return None
        else:#深さ優先探索
            lst = []
            lst.append(n)
            while len(lst) > 0:
                node = lst.pop()
                if node is None:
                    return False
                if node.data == target:
                    self.node_recreate(node)
                    return True
                elif node.data < target :
                    lst.append(node.right)
                elif node.data > target:
                    lst.append(node.left)
            return False
        
    def node_recreate(self,node):
        #ノード再作成機能を装着
        num_lst=[]
        node_lst=[node]
        while len(node_lst)>0:
            node_=node_lst.pop()
            if node_.right is not None:
                node_lst.append(node_.right)
                num_lst.append(node_.right.data)
            if node_.left is not None:
                node_lst.append(node_.left)
                num_lst.append(node_.left.data)
        node=None
        for num in num_lst:
            self.insert(num)
            
                
    
import math
N=int(input())
a=list(map(int,input().split()))
t_max=int(math.log2(max(a)*2)+1)
ans=0
bst=BST(a)
for t in range(t_max,0,-1):
    i=0
    while i<len(a):
    #forだとout of rangeしてしまうので。
        x,y=0,0
#         bst=BST(a)#二分木も更新しないと。
#更新を削除に変更。大分計算回数は減るはず。
        if bst.search(2**t-a[i]):
            if a[i]!=2**t-a[i]:
                #同じだったらNG
                ans+=1
                x+=a[i]
                y+=2**t-a[i]
                #IDを共有すると、インデックスがずれる。
                a.remove(x)
                bst.search(x)#削除を兼ねて
                a.remove(y)
        else:
            i+=1 #ペアが見つからなかったときだけ進めばいい。
print(ans)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
a=list(map(int,input().split()))
a_=sorted(a)
t_max=int(math.log2(a_[-1]+a_[-2])+1)
ans=0
for t in range(t_max,0,-1):
    i=0
    while i<len(a_):
        x,y=0,0
        if 2**t-a_[i] in a_:
            if a[i]!=2**t-a[i]:
                ans+=1
                x+=a_[i]
                y+=2**t-a_[i]
                a_.remove(x)
                a_.remove(y)
        else:
            i+=1
print(ans)

Submission status: Runtime Error

Solution code:
import copy
import bisect

def index(a, x):
    i = bisect.bisect_right(a, x)
    a.reverse()
    if i != len(a) and a[i] == x:
        return i
    return -1
    
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
ano_a=copy.copy(a)
ano_a.sort()
for i in range(n):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        c=index(ano_a,x)
        if x==a[i] and a[i+1]==x:
            ans+=1
            a[i]=None
            a[c]=None
        elif c>=0:
            if x!=a[i]:
                ans+=1
                a[c]=None
                a[i]=None
print(ans)

Submission status: Runtime Error

Solution code:
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    return mid


n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for i in range(n-1):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        if a[i]==x and a[i+1]==x:
            ans+=1
            a[i]=None
            c=binary_search(a,x)
            a[c]=None
print(ans)

Submission status: Runtime Error

Solution code:
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for i in range(n):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        if a[i]==x and a[i+1]==x:
            ans+=1
            a[i]=None
            a[a.index(x)]=None
print(ans)

Submission status: Runtime Error

Solution code:
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for i in range(n):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        if a[i]==x and a[i+1]==x:
            ans+=1
            a[i]=None
print(ans)

Submission status: Runtime Error

Solution code:
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for i in range(n):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        if a[i]==x and a[i+1]==x:
            ans+=1
            a[i]=None
            a[a.index(x)]=None
        elif x in a and x!=a[i]:
            ans+=1
            a[a.index(x)]=None
            a[i]=None
print(ans)

Submission status: Runtime Error

Solution code:
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for b in a:
    if b:
        bi=format(b, 'b')
        x=2**len(bi)-b
        if x==b and a.count(x)>1:
            ans+=1
            b=None
            a[a.index(x)]=None
        else:
            ans+=1
            a[a.index(x)]=None
            b=None
print(ans)

Submission status: Runtime Error

Solution code:
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for b in a:
    if b:
        bi=format(b, 'b')
        x=2**len(bi)-b
        if x==b and a.count(x)>1:
            ans+=1
            b=None
            a[a.index(x)]=None
        elif x!=b:
            ans+=1
            a[a.index(x)]=None
            b=None
print(ans)

Submission status: Runtime Error

Solution code:
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for b in a:
    if b:
        bi=format(b, 'b')
        x=2**len(bi)-b
        if x==b and a.count(x)>1:
            ans+=1
            b=None
            a[a.index(x)]=None
        elif 1>0 and x!=b:
            ans+=1
            a[a.index(x)]=None
            b=None
print(ans)

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

uint32_t ceil2(uint32_t a)
{
    uint32_t b = 1;
    while (a > b) {
        b <<= 1;
    }
    return b;
}

int main()
{
    int N;
    cin >> N;

    multiset<int> S;
    vector<int> A(N);
    for (auto &&a : A) {
        cin >> a;
        S.insert(a);
    }
    sort(rbegin(A), rend(A));

    int ans = 0;
    for (auto a : A) {
        if (S.find(a) != S.end()) {
            S.erase(a);
            int p = ceil2(a) - a;
            if (S.find(p) != S.end()) {
                S.erase(p);
                ans += 1;
            }
        }
    }

    cout << ans << '\n';
}

Submission status: Runtime Error

Solution code:
N, *A = map(int, open(0).read().split())

S = set(A)

A.sort(reverse=True)

ans = 0
for a in A:
    b = 2 ** a.bit_length() - a
    if a != b and b in S:
        S.remove(a)
        S.remove(b)
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import bisect
N = int(input())
*A, = map(int,input().split())
B = {}
for a in A:B[a] = B.get(a,0) + 1
B = sorted(map(list,B.items()))
bl = bisect.bisect_left

ans = 0
while 1:
    b,n = B.pop()
    if not B : break
    c = (1<<(len(bin(b))-2)) - b
    i = bl(B,[c,0])
    if B[i][0] == c:
        m = min(n,B[i][1])
        ans += m
        B[i][1] -= m
print(ans)

Submission status: Runtime Error

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



def main():
    N = int(input())
    A = list(map(int, input().split()))

    M = 2*10**5
    X = [0]*(M+1)

    for a in A:
        X[a] += 1

    c = 0

    for i in range(17, -1, -1):
        r1 = 1<<i
        r2 = r1*2

        c2 = X[r1]//2
        c += c2
        X[r1] -= c2*2        

        for j in range(r1+1, min(r2-1, M)+1):
            j2 = r2-j

            c2 = min(X[j], X[j2])
            c += c2
            
            X[j] -= c2
            X[j2] -= c2

    print(c)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect

def f(a,k):
  if len(a) <= 1:
    return k
  m = a.pop(-1)
  v = 1
  while v <= m:
    v *= 2
  r = v-m
  i = bisect.bisect_left(a,r)
  if i < len(a) and a[i] == r:
    k += 1
    a.pop(i)
    return f(a,k)
  else:
    return f(a,k)

n = int(input())
l = sorted(list(map(int,input().split())))
print(f(l,0))

Submission status: Runtime Error

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


N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set = []
num = []
a_cur = float('inf')
for a in A:
    if a != a_cur:
        A_set.append(a)
        num.append(1)
        a_cur = a
    else:
        num[-1] += 1

ans = 0
for i in range(len(A_set) - 1, -1, -1):
    if num[i] > 0:
        A_i = A_set[i]
        comp = 2 ** math.ceil(math.log2(A_i + 1)) - A_i
        j = bisect.bisect_left(A_set, comp, 0, i)
        while True:
            if A_set[j] == comp:
                if num[j] > 0:
                    if i != j:
                        ans += 1
                        num[j] -= 1
                        break
                    elif num[j] >= 2:
                        add = num[j] // 2
                        ans += add
                        num[j] = num[j] % 2
                        break
                    else:
                        break
                else:
                    break
            else:
                break

print(ans)

Submission status: Runtime Error

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


N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set = []
num = []
a_cur = float('inf')
for a in A:
    if a != a_cur:
        A_set.append(a)
        num.append(1)
        a_cur = a
    else:
        num[-1] += 1

ans = 0
for i in range(len(A_set) - 1, -1, -1):
    if num[i] > 0:
        A_i = A_set[i]
        comp = 2 ** math.ceil(math.log2(A_i + 1)) - A_i
        j = bisect.bisect_left(A_set, comp, 0, i)
        while True:
            if A_set[j] == comp:
                if num[j] > 0:
                    if i != j:
                        ans += 1
                        num[j] -= 1
                        break
                    elif num[j] >= 2:
                        ans += 1
                        num[j] -= 2
                    else:
                        break
                else:
                    break
            else:
                break

print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int n;
set<int> s;
int dp[25];
int cnt = 0;
int main()
{
    cin >> n;
    rep(i, n)
    {
        int x;
        cin >> x;
        s.insert(x);
    }
    dp[0] = 1;
    rep(i, 20)
    {
        dp[i + 1] = dp[i] * 2;
    }
    set<int>::iterator mx, p;
    while (s.size() >= 2)
    {
        mx = --s.end();
        int val = *lower_bound(dp, dp + 21, *mx);
        p = s.find(val - *mx);
        if (p != s.end())
        {
            // 発見した
            cnt++;
            s.erase(mx);
            s.erase(p);
        }
        else
        {
            s.erase(mx);
        }
    }
    cout << cnt << endl;
}

Submission status: Runtime Error

Solution code:
import math
n=int(input())
A=[int(i) for i in input().split()]
B=[]
for a in A:
  B.append(a)
A.sort(reverse=True)
count=0
for i in range(n):
  cur=A[i]
  if cur in B:
    k=int(math.log2(cur))+1
    pair=2**k-cur
    if pair in B:
      B.remove(pair)
      B.remove(cur)
      count+=1
print(count)

Submission status: Runtime Error

Solution code:
# coding:utf-8

import sys
from bisect import bisect_left, bisect_right
INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    A = LI()
    A.sort()

    res = 0
    used = [0] * n
    for p in range(1, max(A).bit_length() + 1)[::-1]:
        t = 2 ** p
        for i in range(n)[::-1]:
            a = A[i]
            if used[i]:
                continue
            if a >= t:
                break
            bi = bisect_left(A, t - a)
            if A[bi] == t - a:
                if i != bi and not used[bi]:
                    res += 1
                    used[i] = 1
                    used[bi] = 1

    print(res)


if __name__ == '__main__':
    main()