Submission #1146914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146914		yasser	XOR (IZhO12_xor)	C++17	0 / 100	0 ms	320 KiB

xor

#include <bits/stdc++.h>
using namespace std;

void Yasser() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}

struct Node {
    int childs[2]{};
    int pre;
    int &operator[](int x) {
        return childs[x];
    }
};

struct Trie {
    vector<Node> trie;
    int newNode() {
        trie.emplace_back();
        return trie.size() - 1;
    }
    void clear() {
        trie.clear();
    }
    Trie() {
        clear();
        newNode();
    }
    bool sz(int node) {
        return (trie[node].pre > 0);
    }
    void insertOrremove(int x, int op) {
        int node = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = x >> i & 1;
            if (trie[node][bit] == 0) {
                trie[node][bit] = newNode();
            }
            node = trie[node][bit];
            trie[node].pre += op;
        }
    }

    int Query(int x) {
        int res = 0;
        int node = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = x >> i & 1;
            if (trie[node][1 - bit]) {
                res |= (1 << i);
                node = trie[node][1 - bit];
            } else {
                node = trie[node][bit];
            }
        }
        return res;
    }
};

void solve() {
    ifstream cin("c.in");
    ofstream cout("c.out");
    
    int n, x;
    cin >> n >> x;
    map<int, vector<int>> idxs;
    idxs[0].emplace_back(0);
    vector<int> arr(n + 1);
    
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        arr[i] ^= arr[i - 1];
        idxs[arr[i]].emplace_back(i);
    }
    
    Trie triee;
    triee.insertOrremove(0, +1);
    int max_xor = 0, length = 0, start_index = 0;
    
    for (int i = 1; i <= n; i++) {
        int max_possible = triee.Query(arr[i]);
        if ((max_possible ^ arr[i]) >= x) {
            int candidate_length = i - *idxs[max_possible].begin();
            if (candidate_length > length) {
                length = candidate_length;
                start_index = *idxs[max_possible].begin();
            }
        }
        triee.insertOrremove(arr[i], +1);
    }
    
    cout << start_index + 1 << ' ' << length << endl;
}

signed main() {
    int test_cases = 1;
    //cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    return 0;
}

• Subtask 1: 0 / 100