제출 #1354650

#제출 시각아이디문제언어결과실행 시간메모리
1354650vjudge1XOR (IZhO12_xor)C++17
100 / 100
90 ms22476 KiB
// I ? ???
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
using namespace std;

using ll = long long;

void justDoIt();

int main() {
    // freopen("");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    justDoIt();
    return 0;
}

const int N = 3e5;
const int NUMNODE = 8e6 + 5;
const int LG = 30;

int pre[N];
int x;

struct Trie {
    struct Node {
        int child[2];
        int mx;
    } nodes[NUMNODE];
    int cur;
    Trie() : cur(0) {
        memset(nodes[0].child, -1, sizeof(nodes[0].child));
        nodes[0].mx = 0;
    };

    int new_node() {
        cur++;
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        nodes[cur].mx = 0;
        return cur;
    }

    void add(int x, int id) {
        int pos = 0;
        for (int i = LG; i >= 0; i--) {
            int c = (x >> i & 1);
            if (nodes[pos].child[c] == -1) {
                nodes[pos].child[c] = new_node();
            }
            pos = nodes[pos].child[c];
            nodes[pos].mx = max(nodes[pos].mx, id);
        }
    }

    int query(int pos, int bit, int val) {
        if (bit < 0) {return nodes[pos].mx;}
        int c = (val >> bit & 1);
        int need = (x >> bit & 1);
        int t = 0;
        if (c == 0) {
            if (need == 1) {
                if (nodes[pos].child[1] == -1) {
                    return t;
                }
                pos = nodes[pos].child[1];
            }
            else {
                if (nodes[pos].child[1] != -1) {
                    t = max(t, nodes[nodes[pos].child[1]].mx);
                }
                if (nodes[pos].child[0] == -1) {
                    return t;
                }
                pos = nodes[pos].child[0];
            }
        }
        else {
            if (need == 0) {
                if (nodes[pos].child[0] != -1) {
                    t = max(t, nodes[nodes[pos].child[1]].mx);
                }
            }
            if (nodes[pos].child[need ^ 1] == -1) {
                return t;
            }
            pos = nodes[pos].child[need ^ 1];
        }
        return max(t, query(pos, bit - 1, val));
    }
};

Trie trie;

void test() {
    int n;
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        int v; cin >> v;
        pre[i] = pre[i - 1] ^ v;
    }
    int res = 0, p = 0;
    for (int i = n; i >= 1; i--) {
        trie.add(pre[i], i);
        int r = trie.query(0, LG, pre[i - 1]);
        if (r - i + 1 >= res) {
            res = r - i + 1;
            p = i;
        }
    }
    cout << p << ' ' << res;
}

void justDoIt() {
    int t = 1;
    // cin >> t;
    for (int tests = 1; tests <= t; tests++) {
        test();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...