编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#20641 #1001. A. 神秘谜题 Accepted 100 331 ms 26092 K C++ / 1.4 K 电类809-廖原 2019-07-28 15:46:18
显示原始代码
#include <cstdio>
#include <algorithm>
#include <vector>
#define ULL unsigned long long
#define LL long long
using namespace std;
char ch;
bool fh;
inline void read(int &a) {
    for (fh = 0, ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
        if (ch == '-')
            fh = 1;
    for (a = 0; ch >= '0' && ch <= '9'; ch = getchar()) (a *= 10) += ch - '0';
    if (fh)
        a = -a;
}
struct node {
    int s[2];
    int num[2];  //当前节点左支的数字个数与右支的数字个数
};
node Trie[200010 * 34];
int num[34][2];
int top;
int A[34];
int n;
inline void newnode() { top++; }
void Plus() {
    int p, l, v;
    for (l = 0, p = 1; Trie[p].s[1]; l++, p = Trie[p].s[0]) {
        swap(Trie[p].s[0], Trie[p].s[1]);
        swap(Trie[p].num[0], Trie[p].num[1]);
        v = Trie[p].num[0] ^ Trie[p].num[1];
        num[l][0] ^= v;
        num[l][1] ^= v;
    }
    swap(Trie[p].s[0], Trie[p].s[1]);
    swap(Trie[p].num[0], Trie[p].num[1]);
    v = Trie[p].num[0] ^ Trie[p].num[1];
    num[l][0] ^= v;
    num[l][1] ^= v;
}
void insert(int w) {
    int l, p;
    for (l = 0; l < 32; l++) A[l] = 0;
    for (l = 0; w; l++, w >>= 1) A[l] = w & 1;
    for (l = 0, p = 1; l < 32; p = Trie[p].s[A[l]], l++) {
        if (!Trie[p].s[A[l]]) {
            newnode();
            Trie[p].s[A[l]] = top;
        }
        Trie[p].num[A[l]] ^= 1;
        num[l][A[l]] ^= 1;
    }
}
int ans;
void Count() {
    int l, p2;
    ans = 0;
    for (l = 0, p2 = 1; l < 32; l++, p2 <<= 1) ans += num[l][1] * p2;
}
int main() {
    read(n);
    int vi, opt, w;
    top = 1;
    for (vi = 1; vi <= n; vi++) {
        read(opt);
        if (opt == 1)
            Plus();
        else {
            read(w);
            insert(w);
        }
        Count();
        printf("%d\n", ans);
    }
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:155 ms
内存:26092 KiB

输入文件(1.in

200000
2 526767110
2 724642759
2 567837900
2 104106873
2 357915481
2 33997211
2 444788944
2 
<1586974 bytes omitted>

答案文件(1.ans

526767110
877985729
361528077
330887284
116239149
82537142
510237286
843295274
453728745
55
<2188330 bytes omitted>

用户输出

526767110
877985729
361528077
330887284
116239149
82537142
510237286
843295274
453728745
559263713
323554710
713540578
520942594
<1988302 bytes omitted>

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:176 ms
内存:26012 KiB

输入文件(2.in

200000
2 515979308
2 512702340
2 684230440
2 488136957
2 598252313
2 283603971
2 349877373
2
<1586842 bytes omitted>

答案文件(2.ans

515979308
5115816
679905408
899606653
372667236
114362215
302756634
473674072
520218589
525
<2192841 bytes omitted>

用户输出

515979308
5115816
679905408
899606653
372667236
114362215
302756634
473674072
520218589
525056845
703148326
764590712
207056035

<1992813 bytes omitted>

系统信息

Exited with return code 0