No.1577 Orihime and Hikoboshi 2
タグ : / 解いたユーザー数 48
作問者 :
kagasantwi
Problem Statement
This problem is the same as Orihime and Hikoboshi except for the constraints.
Orihime and Hikoboshi are allowed to meet only once a year, crossing the Milky Way on the night of Tanabata.
Feeling lonely about this, the two devised a plan to secretly build a bridge over the Milky Way so that they can come and go freely.
First, the two wondered whether they could build a bridge using the N types of stones that exist on Orihime's bank.
These stones hold a mysterious power: two stones can be joined when the Hamming distance between the integers representing their properties is at most 1.
(The Hamming distance is explained below.)
The ground on both banks of the Milky Way, that is, Orihime's bank and Hikoboshi's bank, is also made of stones holding the same mysterious power.
Output the minimum number of types of stones, among the N types, that must be used to build a sturdy bridge joined by the mysterious power.
If no such bridge can be built, output $-1$.
(There are infinitely many stones of each type.)
Hamming distance
The Hamming distance between two integers is the number of bits that differ when the two integers are written in binary.
↓For example, the Hamming distance between 3 and 13 is 3.
0011 (3 in decimal)
1101 (13 in decimal)
Input
$N$
$start\ end$
$stone_0\ stone_1\ ...\ stone_{N-1}$
The following information is given in the format above.
Property of the stone on Orihime's side: $start$
Property of the stone on Hikoboshi's side: $end$
Property of the $i$-th stone: $stone_i$
Constraints
$1 \le N \le 5 \times 10^4$
$0 \le start,\ end,\ stone_i \le 10^9$
$start,\ end,\ stone_i$ are all distinct
Sample
Sample 1
Input
5 2 0 8 10 5 9 7
Output
0
The bridge can be built in the following ways.
- 2→10→8→0 Written as 4-bit binary numbers, these are as follows.
- 2→0 Written as 2-bit binary numbers, these are as follows.
0010
↓
1010
↓
1000
↓
0000
10
↓
00
In this problem, it is also allowed to build the bridge using only the stones that make up the ground of the two banks.
Therefore, the answer for this sample input is $0$.
Sample 2
Input
3 2 4 6 8 1
Output
1
2→6→4 is optimal.
Sample 3
Input
3 7 6 9 1 5
Output
0
Sample 4
Input
10 21 26 27 24 18 16 17 20 13 1 12 15
Output
3
Sample 5
Input
2 2 1 5 9
Output
-1
No bridge can be built no matter which stones are used.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。