同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

10215_CowXOR

2022-5-16 18:16| 发布者: Hocassian| 查看: 75| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504666819300-Problem List-采集的数据-后羿采集器.html

Pro.ID

10215

Title

Cow XOR

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=10215

AC

Submit

Ratio

45.00%

时间&空间限制

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32767/32767 K (Java/Others)

描述

Farmer John is stuck with another problem while feeding his cows. All of his N (1 ≤ N ≤ 100,000) cows (numbered 1..N) are lined up in front of the barn, sorted by their rank in their social hierarchy. Cow #1 has the highest rank; cow #N has the least rank. Every cow had additionally been assigned a non-unique integer number in the range 0..(2²¹ - 1).

Help FJ choose which cows will be fed first by selecting a sequence of consecutive cows in the line such that the bitwise "xor" between their assigned numbers has the maximum value. If there are several such sequences, choose the sequence for which its last cow has the highest rank. If there still is a tie, choose the shortest sequence.

输入

Line 1: A single integer N

Lines 2..N+1: N integers ranging from 0 to 2²¹ - 1, representing the cows' assigned numbers. Line j describes cow of social hierarchy j-1.

输出

Description

Input

Line 1: A single integer N

Lines 2..N+1: N integers ranging from 0 to 2²¹ - 1, representing the cows' assigned numbers. Line j describes cow of social hierarchy j-1.

Output

Line 1: Three space-separated integers, respectively: the maximum requested value, the position where the sequence begins, the position where the sequence ends.

Sample Input

5
1
0
5
4
2

Sample Output

6 4 5

Hint

INPUT DETAILS:

There are 5 cows. Cow #1 had been assigned with 1; cow #2 with 0; cow #3 with 5; cow #4 with 4; cow #5 with 2.

OUTPUT DETAILS:

4 xor 2 = 6 (001) xor (010) = (011)

Source

USACO training course