제출 #1187458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187458		salmakaram	XOR (IZhO12_xor)	C++20	100 / 100	111 ms	56616 KiB

xor

#include <bits/stdc++.h>

#define Pc_champs ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;

#define ll long long
#define int long long
//
//
int const N = 1e5 + 1, LOG = 17, N2 = 2 * N + 1, M = 1e9 + 7, SQ = 390;

int n, k;
struct Node {
    Node *link[2];
    int id = n + 1;
};

struct Trie {
    Node *root;

    Trie() {
        root = new Node();
    }

    void insert(int x, int j) {
        Node *node = root;
        for (int i = 29; i >= 0; --i) {
            bool sg = x & (1 << i);
            if (node->link[sg] == NULL) node->link[sg] = new Node();
            node = node->link[sg];
            node->id = min(node->id, j);
        }
    }

    int mx(int x, int j) {
        Node *node = root;
        int ret{};
        for (int i = 29; i >= 0; --i) {
            bool sg = x & (1 << i);
            if (k & (1 << i)) {
                if (node->link[sg ^ 1] == NULL) return ret;
                node = node->link[sg ^ 1];
            } else {
                if (node->link[sg ^ 1] != NULL) ret = max(ret, j - node->link[sg ^ 1]->id);
                if (node->link[sg] == NULL) return ret;
                node = node->link[sg];
            }
        }
        return max(ret, j - node->id);
    }
};

void dowork() {
    cin >> n >> k;
    Trie t = Trie();
    int mx = -1, id = -1, Xor{};
    t.insert(0, -1);
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        Xor ^= x;
        int v = t.mx(Xor, i);
        if (v > mx) mx = v, id = i - v + 2;
        t.insert(Xor, i);
    }
    cout << id << ' ' << mx;
}


signed main() {
    Pc_champs
    int t = 1;
    //cin >> t;
    while (t--) {
        dowork();
        cout << "\n";
    }
}

• Subtask 1: 100 / 100