제출 #1062143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1062143		VMaksimoski008	XOR (IZhO12_xor)	C++17	100 / 100	1348 ms	43552 KiB

xor

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

const int M = 5e6;

int id=1, trie[M][2], n, m, v[M], pref[M];

void insert(int x) {
    int u = 0;
    for(int i=30; i>=0; i--) {
        bool b = x & (1 << i);
        if(!trie[u][b]) trie[u][b] = id++;
        u = trie[u][b];
    }
}

int XOR(int x) {
    int ans = 0, u = 0;
    for(int i=30; i>=0; i--) {
        bool b = x & (1 << i);
        if(trie[u][!b]) ans |= (1 << i), u = trie[u][!b];
        else u = trie[u][b];
    }
    return ans;
}

int main() {
    cin >> n >> m;

    vector<int> v(n+1), pref(n+1);
    for(int i=1; i<=n; i++) cin >> v[i];
    for(int i=1; i<=n; i++) pref[i] = v[i] ^ pref[i-1];

    int l=1, r=n, ans=1;
    while(l <= r) {
        int mid = (l + r) / 2;
        bool ok = 0;

        id = 1;
        memset(trie, 0, sizeof(trie));
        for(int i=mid; i<=n&&!ok; i++) {
            insert(pref[i-mid]);
            if(XOR(pref[i]) >= m) ok = 1;
        }

        if(ok) l = mid + 1, ans = mid;
        else r = mid - 1;
    }

    for(int i=ans; i<=n; i++) {
        if((pref[i] ^ pref[i-ans]) >= m) {
            cout << i-ans+1 << " " << ans << '\n';
            return 0;
        }
    }
    return 0;
}

• Subtask 1: 100 / 100