IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
266 . 當堅果遇上隨機
TopCoder
Tags
Description
你各位知道，BK 跟 YP 分別是誰嘛？
BK ，身為 LYB 的專業真解王，是今年 IOICamp 負責講隨機、近似的講師。
YP ，身為 LYB 的假專業碼農，是今年 IOICamp 負責講根號算法的講師。
BK 非常喜歡堅果（因為堅果很好吃），而 YP 非常喜歡隨機（因為隨機很有趣）。
而且，在 LYB 的 ICPC 生涯中， YP 曾經用了被 BK 證明答對機率是百分之零的作法，AC 了一題 2018 年緬甸站的題目。從此之後........，就沒有從此之後了。
而當堅果遇上隨機，會產生出什麼新題目呢？
BK 和 YP 現在很衰的拿到了 $10^ {18}$ 顆過期堅果 $1, 2, \dots, 10^ {18}$，第 $i$ 顆過期堅果的過期程度為 $i$ ，過期的日期也是 $i$ 。
雖然堅果很好吃，但如果 BK 和 YP 一口氣吃下了第 $a$ 天的過期堅果到第 $b$ 天的過期堅果，BK 和 YP 就會得到噁度 $a \oplus (a + 1) \oplus \dots \oplus b$ 。 $a \oplus b$ 代表 $a$ XOR $b$ 。注意到 BK 和 YP 吃下去的過期堅果過期的日期必須是連續的 。
而在接下來的 $Q$ 天， BK 和 YP 又要來決鬥了。在每次決鬥中， BK 和 YP 會先決定用第 $L$ 天的過期堅果到第 $R$ 天的過期堅果之間決鬥，以及一個噁心程度上限 $C$ 。BK 和 YP 希望在吃下去的堅果的噁心程度不超過 $C$ 的情況下，吃下盡量多的過期堅果。
正式的來說，你會有 $Q$ 組測試資料，每組測試資料會給你 $L, R, C$ ，請找到 $l, r$ ，滿足：
- $L \le l \le r \le R$
- $l \oplus (l + 1) \oplus \dots \oplus r \le C$
- $r - l + 1$ 要盡可能的大
Input Format
輸入的第一行包含一個正整數 $Q$ ，代表接下來 BK 和 YP 要進行決鬥的天數。
接下來的 $Q$ 行，每行都代表一次的決鬥。每行都會包含三個整數 $L, R, C$ ，變數的意義已經在題目敘述說明過了。
- $1 \le Q \le 5 \times 10^ 5$
- $1 \le L \le R \le 10^ {18}$
- $0 \le C \le 2 \times 10^ {18}$
Output Format
對於每次的決鬥，請輸出最多能吃的過期堅果。如果 BK 和 YP 沒有辦法吃下任何堅果時，請輸出 $-1$ 。
Sample Input 1
1 1 0
2 2 2
8787878787878787 8888888888888888 123456789
Sample Output 1
1
101010101010100
Hints
Problem Source
IOICamp 2020 Day5 pC
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~4 | 無額外限制 | 100 |