编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#119 #1001. A. 神秘谜题 Wrong Answer 0 434 ms 42020 K C++ 11 / 1.9 K grasszhang 2019-06-06 20:19:04
显示原始代码
#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

struct Node {
    long long sum;
    long long size;
    Node *son[2];
    Node() {
        son[0] = nullptr;
        son[1] = nullptr;
        size = 0;
        sum = 0;
    }
    Node(long long x) {
        son[0] = nullptr;
        son[1] = nullptr;
        size = 1;
        sum = x;
    }

    void inc(bool is_root) {
        Node *t0 = son[0], *t1 = son[1];
        long long t0_size = size - (son[1] == nullptr ? 0 : son[1]->size);
        if (t0 == nullptr && t1 == nullptr && t0_size > 0) {
            t0 = new Node();
            t0->size = t0_size;
            t0->sum = t0->size & 1;
        } else if (t0 != nullptr) {
            t0->sum ^= (t0->size & 1);
        }
        if (t1 == nullptr) {
            // no op
        } else {
            t1->inc(false);
        }
        son[0] = t1;
        son[1] = t0;
        sum = 0;
        sum ^= (son[0] == nullptr ? 0 : son[0]->sum);
        sum ^= (son[1] == nullptr ? 0 : son[1]->sum);
        if (!is_root)
            sum <<= 1;
    }
};

class MultiSet {
private:
    Node *root;

public:
    MultiSet() { root = new Node(); }
    long long getSum() { return root->sum; }
    void inc() { root->inc(true); }
    void insert(long long t) {
        Node *cur = root;
        root->size++;
        for (long long flag = t & 1; t; t >>= 1, cur = cur->son[flag], flag = t & 1) {
            if (cur->son[flag] != nullptr) {
                cur->son[flag]->sum ^= t;
                cur->son[flag]->size++;
            } else {
                cur->son[flag] = new Node(t);
            }
        }
        root->sum = (root->son[0] == nullptr ? 0 : root->son[0]->sum) ^
                    (root->son[1] == nullptr ? 0 : root->son[1]->sum);
    }
};

int main() {
    long long n;
    MultiSet ms;
    cin >> n;
    for (long long i = 0; i < n; ++i) {
        long long op;
        scanf("%lld", &op);
        if (op == 1) {
            ms.inc();
        } else if (op == 2) {
            long long num;
            scanf("%lld", &num);
            ms.insert(num);
        }
        printf("%lld\n", ms.getSum());
    }
    return 0;
}
子任务 #1
Wrong Answer
得分:0
测试点 #1
Wrong Answer
得分:0
用时:219 ms
内存:42020 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
<1988382 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #2
Wrong Answer
得分:0
用时:215 ms
内存:41936 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

<1992828 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0