编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#1982 #1001. A. 神秘谜题 Time Limit Exceeded 0 2084 ms 2592 K C++ 11 (NOI) / 2.7 K 计试71-殷子欣 2019-06-25 18:28:53
显示原始代码
#include <iostream>
#include <cstdio>

class TreeNode {
public:
    int num;
    TreeNode *left = NULL;
    TreeNode *right = NULL;
    bool isDelete = false;

    TreeNode(int num) { this->num = num; }
};

class Tree {
public:
    TreeNode *root = NULL;
    void insert(int num);
    void plusOne() {
        plusOne(root);
        showAnswer(true);
    }

private:
    int lastAnswer = 0;
    void showAnswer(bool needRecalculate, int newNumber = 0);
    void plusOne(TreeNode *node);
    int yuHuo(TreeNode *node, int number);
};

void Tree::insert(int num) {
    TreeNode *newNode = new TreeNode(num);

    if (root == NULL) {
        root = newNode;
        showAnswer(false, num);
        return;
    }

    TreeNode *temp = root;

    while (1) {
        if (num == temp->num) {
            temp->isDelete = true;
            showAnswer(false, num);
            return;
        } else if (num < temp->num) {
            if (temp->left == NULL) {
                temp->left = newNode;
                showAnswer(false, num);
                return;
            }

            temp = temp->left;
        } else {
            if (temp->right == NULL) {
                temp->right = newNode;
                showAnswer(false, num);
                return;
            }

            temp = temp->right;
        }
    }
}

void Tree::plusOne(TreeNode *node) {
    if (node == NULL) {
        return;
    }
    node->num++;
    plusOne(node->left);
    plusOne(node->right);
}

void Tree::showAnswer(bool needRecalculate, int newNumber) {
    if (needRecalculate == false) {
        lastAnswer ^= newNumber;
    } else {
        lastAnswer = yuHuo(root, newNumber);
    }

    std::cout << lastAnswer << std::endl;
}

int Tree::yuHuo(TreeNode *node, int number) {
    if (node == NULL) {
        return number;
    }
    number ^= node->num;
    number = yuHuo(node->left, number);
    return yuHuo(node->right, number);
}

inline int read() {
    int num = 0, sign = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            sign = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        num = num * 10 + ch - '0';
        ch = getchar();
    }

    return num * sign;
}

int main(int argc, const char *argv[]) {
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);

    int n = read();
    Tree tree = Tree();

    int funcNum, num;

    for (int i = 0; i < n; i++) {
        funcNum = read();
        if (funcNum == 1) {
            tree.plusOne();
        } else {
            num = read();
            tree.insert(num);
        }
    }
    return 0;
}
子任务 #1
Time Limit Exceeded
得分:0
测试点 #1
Time Limit Exceeded
得分:0
用时:1041 ms
内存:2592 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
<998849 bytes omitted>
测试点 #2
Time Limit Exceeded
得分:0
用时:1043 ms
内存:2484 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

<998632 bytes omitted>