Submission #514818

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
514818	2022-01-18T14:09:04 Z	Be_dos	XOR (IZhO12_xor)	C++17	100 / 100	262 ms	59436 KB

xor

#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

struct Node {
    Node* left = nullptr, *right = nullptr;
    int32_t min = INT32_MAX;
};

#define BITS 30

void add(Node* root, int32_t x, int32_t val) {
    for(int32_t i = BITS - 1; i >= 0; i--) {
        root->min = std::min(root->min, val);
        if(x & (1 << i)) {
            if(root->right == nullptr)
                root->right = new Node;
            root = root->right;
        } else {
            if(root->left == nullptr)
                root->left = new Node;
            root = root->left;
        }
    }
    root->min = std::min(root->min, val);
}

int32_t get_min(Node* root, int32_t x, int32_t not_less_than) {
    int32_t ans = INT32_MAX;
    for(int32_t i = BITS - 1; i >= 0; i--) {
        if(not_less_than & (1 << i)) {
            ;
        } else {
            if(x & (1 << i)) {
                if(root->left != nullptr)
                    ans = std::min(ans, root->left->min);
            } else {
                if(root->right != nullptr)
                    ans = std::min(ans, root->right->min);
            }
        }

        if((not_less_than ^ x) & (1 << i)) {
            if(root->right == nullptr)
                return ans;
            root = root->right;
        } else {
            if(root->left == nullptr)
                return ans;
            root = root->left;
        }
    }
    ans = std::min(ans, root->min);
    return ans;
}

int main() {
    int32_t n, x;
    std::cin >> n >> x;

    int32_t* arr = new int32_t[n];
    for(int32_t i = 0; i < n; i++)
        std::cin >> arr[i];

    int32_t pref_xor = 0;
    Node* root = new Node;
    add(root, 0, 0);
    int32_t left = -1, right = -2;
    for(int32_t i = 0; i < n; i++) {
        pref_xor ^= arr[i];

        int32_t opt = get_min(root, pref_xor, x);
        if(right - left + 1 < i + 1 - opt) {
            left = opt;
            right = i;
        }
        add(root, pref_xor, i + 1);
    }
    std::cout << left + 1 << " " << right - left + 1;
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	10 ms	1888 KB	Output is correct
6	Correct	17 ms	2076 KB	Output is correct
7	Correct	13 ms	2124 KB	Output is correct
8	Correct	14 ms	2124 KB	Output is correct
9	Correct	88 ms	27908 KB	Output is correct
10	Correct	85 ms	27956 KB	Output is correct
11	Correct	105 ms	27804 KB	Output is correct
12	Correct	104 ms	27932 KB	Output is correct
13	Correct	85 ms	27972 KB	Output is correct
14	Correct	85 ms	28016 KB	Output is correct
15	Correct	89 ms	27968 KB	Output is correct
16	Correct	86 ms	27844 KB	Output is correct
17	Correct	235 ms	59296 KB	Output is correct
18	Correct	262 ms	59332 KB	Output is correct
19	Correct	232 ms	59436 KB	Output is correct
20	Correct	223 ms	59332 KB	Output is correct