#1126. 【NFLSPC #4】reply

题目类型:传统型 时间限制:1000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:Special Judge

题目描述

有 $n$ 个人(编号为 $1$ 至 $n$)看到了相同的信息,它被表示成自然数 $x$。第 $i$ 个人将这条信息理解为 $a_i=x$ xor $i$。现在你了解到了这些人对这条信息的理解,希望知道任何一种可能的原信息。

xor 表示按位异或运算。


输入格式

第一行有一个整数 $n$,代表人数 。

第二行 $4n$ 个字符,每 $4$ 个字符表示一个数,其中第 $i$ 个数为 $b_i$。其中 $b_1$ 至 $b_n$ 为 $a_1$ 至 $a_n$ 从小到大排序后的结果。

具体来说,第二行使用 $64$ 进制来表示数字,对应关系与 base64 相同即 A 至 Z 分别对应 $0$ 至 $25$,a 至 z 分别对应 $26$ 至 $51$,0 至 9 分别对应 $52$ 至 $61$,+ 对应 $62$,/ 对应 $63$。

对于 C++ 语言,你可以把下方代码黏贴进程序,并在 main 函数开头调用 init 函数来快速读入数据。使用该代码片段进行本地测试时,需要在输入结束后输入 Ctrl+Z 或者使用文件输入输出。

char I[1048600],*Is=I,*It=I;
inline char gc(){return Is==It?((It=(Is=I)+fread(I,1,1048576,stdin))==I?EOF:*Is++):*Is++;}
int n,b[5000005];
void init(){
    char c=gc();
    while(c<48)c=gc();
    while(c>47)n=n*10+c-48,c=gc();
    register int f[130];
    for(int i='A';i<='Z';++i)f[i]=i-'A';
    for(int i='a';i<='z';++i)f[i]=i-'a'+26;
    for(int i='0';i<='9';++i)f[i]=i-'0'+52;
    f['+']=62;
    f['/']=63;
    while(c<32)c=gc();
    b[1]|=(f[c]<<18);
    b[1]|=(f[gc()]<<12);
    b[1]|=(f[gc()]<<6);
    b[1]|=f[gc()];
    for(register int i=2;i<=n;++i){
        b[i]|=(f[gc()]<<18);
        b[i]|=(f[gc()]<<12);
        b[i]|=(f[gc()]<<6);
        b[i]|=f[gc()];
    }
}

输出格式

一个整数,表示任何一种可能的原信息 $x$。

保证一定有解。


样例一

input

2
AAABAAAC

output

0

样例解释

转换完的输入为 $b_1=1$ $b_2=2$。

$0$ 和 $3$ 是全部可能的解,任意输出一个即可。


限制与约定

  • 子任务 $1$($100$ 分):保证 $2 \leq n \leq 5\times 10^6$,$0 \leq a_i \leq 2^{23}-1$。

$by\ \text{skyline}$