제출 #1077801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1077801		MyCode	XOR (IZhO12_xor)	C++17	0 / 100	7 ms	3036 KiB

xor

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = (int) 1e4 * 25 + 10;
const int INF = (int) 1e18;

int a[N], n;

struct Node {
    int go[2], mx;
    bool term;

    Node() {
        fill(go, go + 2, -1);
        mx = -INF;
        term = false;
    }
};

vector<Node> T;

void add(int x, int ind) {
    int cur = 0;
    for (int bit = 30; bit >= 0; bit--) {
        T[cur].mx = max(T[cur].mx, ind);
        int c = ((x >> bit) & 1);
        if (T[cur].go[c] == -1)
            T[cur].go[c] = (int) T.size(), T.emplace_back();
        cur = T[cur].go[c];
    }
    T[cur].mx = max(T[cur].mx, ind);
    T[cur].term = true;
}

bool go(int cur, int c) {
    return T[cur].go[c] != -1;
}

int mx(int cur, int c) {
    return (go(cur, c) ? T[T[cur].go[c]].mx : -INF);
}

int get(int pref, int x) {
    int cur = 0, res = -INF, bit;
    for (bit = 30; bit >= 0; bit--) {
        int A = ((pref >> bit) & 1), B = ((x >> bit) & 1);
        if (A == B) {
            if (A == 0)
                res = max(res, mx(cur, 1));
            if (!go(cur, 0))
                break;
            cur = T[cur].go[0];
        } else {
            if (A == 1) {
                res = max(res, mx(cur, 0));
                if (!go(cur, 1))
                    break;
                cur = T[cur].go[1];
            } else {
                if (!go(cur, 1))
                    break;
                cur = T[cur].go[1];
            }
        }
    }
    if (bit == -1)
        res = max(res, T[cur].mx);
    return res;
}

int pref[N], x;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    T.emplace_back();

    cin >> n >> x;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    pref[0] = 0;
    for (int i = 1; i <= n; i++)
        pref[i] = a[i - 1] ^ pref[i - 1];
    int res = -INF, A = 0;
    for (int i = n; i >= 0; i--) {
        if (get(pref[i], x) - i > res - A) {
            res = get(pref[i], x);
            A = i;
        }
        add(pref[i], i);
    }
    for (int i = n; i >= 1; i--) {
        if ((pref[A] ^ pref[i]) >= x) {
            cout << A + 1 << " " << i - A;
            return 0;
        }
    }
    return 0;
}

• Subtask 1: 0 / 100