コンテンツにスキップ

牛客小白月赛138 C - AND and OR

サイト
NowCoder
コンテスト
牛客小白月赛138
問題
C - AND and OR

長さ nn の非負整数列 a1,…,ana_1, \dots, a_n と非負整数 kk が与えられます(2≤n≤2×1052 \le n \le 2 \times 10^5、0≤ai,k≤1090 \le a_i, k \le 10^9)。

(aiandaj)+(aioraj)=k(a_i \mathbin{\mathrm{and}} a_j) + (a_i \mathbin{\mathrm{or}} a_j) = k

を満たす 1≤i<j≤n1 \le i < j \le n があれば 1 つ出力し、なければ −1-1 を出力してください(nn の総和 ≤2×105\le 2 \times 10^5)。

実は、どんな非負整数 a,ba, b についても

(aandb)+(aorb)=a+b(a \mathbin{\mathrm{and}} b) + (a \mathbin{\mathrm{or}} b) = a + b

が成り立ちます。ビットごとに確かめると分かります。各ビットについて、aa と bb のそのビットの組み合わせは次の 3 通りです。

a,ba, b のビットANDORAND + ORa+ba + b
両方 0000000000
片方だけ 1100111111
両方 1111112222

どのビットでも AND と OR の寄与の和が aa と bb の寄与の和に一致するので、全体でも等しくなります。

したがって、問題は「ai+aj=ka_i + a_j = k となる i<ji < j を 1 つ見つけよ」という、よくある問題に言い換えられます。

(ai,i)(a_i, i) の組を値でソートしておきます。各要素 aia_i について、相手の値 k−aik - a_i が列にあるかを二分探索で調べます。見つかった相手が自分自身でなければ、そのペアが答えです。

k−ai=aik - a_i = a_i のときは、二分探索で見つかる最初の要素が自分自身になることがあります。ただ、同じ値がもう 1 つあれば、その要素を見たときに最初の要素が相手として見つかるので、取りこぼしはありません。

計算量はソートと二分探索で O(nlog⁡n)O(n \log n) です。

Python
import bisect
for _ in range(int(input())):
N, K = map(int,input().split())
A = list(map(int,input().split()))
Ai = [(A[i],i) for i in range(N)]
Ai.sort()
for i in range(N):
j = bisect.bisect_left(Ai,(K-Ai[i][0],-1))
if 0<=j<N and i!=j and K-Ai[i][0]==Ai[j][0]:
print(*sorted((Ai[i][1]+1,Ai[j][1]+1)))
break
else:
print(-1)

Ai は (値, 元の添字) の組をソートしたものです。(K-Ai[i][0],-1) で bisect_left すると、値が k−aik - a_i 以上である最初の位置が求まります。添字は 00 以上なので、第 2 要素に −1-1 を入れておけば、値が k−aik - a_i の組より必ず前に来ます。出力は i<ji < j の順にする必要があるので、元の添字をソートしてから出力しています。