Submission #697948

#	Time	Username	Problem	Language	Result	Execution time	Memory
697948		gagik_2007	XOR (IZhO12_xor)	C++17	100 / 100	173 ms	62284 KiB

xor

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

const ll K = 2;

struct Vertex {
    Vertex* to[K];
    int cnt;
    Vertex() {
        for (ll i = 0; i < K; i++) {
            to[i] = nullptr;
        }
        cnt = 1e8;
    }
};

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 1000007;
const ll LG = 29;
ll n, m, k;
Vertex p;
ll a[N];
ll pf[N];

void add(int x, int vl) {
    Vertex* v = &p;
    (*v).cnt = min((*v).cnt, vl);
    for (int i = LG; i >= 0; i--) {
        //cout << i << endl;
        int c = 0;
        if (x & (1 << i)) {
            c = 1;
        }
        if ((*v).to[c] == nullptr) {
            //cout << "baba";
            (*v).to[c] = new Vertex();
            //cout << "baba";
        }
        v = (*v).to[c];
        (*v).cnt = min((*v).cnt, vl);
    }
}

int get_cnt(int vl) {
    //cout << endl;
    int cur = 0;
    Vertex* v = &p;
    int res = N;
    for (int i = LG; i >= 0; i--) {
        //cout << res << " " << v << endl;
        if (vl & (1 << i)) {
            if (cur + (1 << i) >= k && (*v).to[0] != nullptr) {
                res = min(res, (*(*v).to[0]).cnt);
                if ((*v).to[1] == nullptr) {
                    return res;
                }
                v = (*v).to[1];
            }
            else if ((*v).to[0] != nullptr) {
                cur += (1 << i);
                v = (*v).to[0];
            }
            else if (cur + (1 << i) >= k) {
                v = (*v).to[1];
            }
            else {
                return res;
            }
        }
        else {
            if (cur + (1 << i) >= k && (*v).to[1] != nullptr) {
                //cout << "MT: 1" << endl;
                res = min(res, (*(*v).to[1]).cnt);
                if ((*v).to[0] == nullptr) {
                    return res;
                }
                v = (*v).to[0];
            }
            else if ((*v).to[1] != nullptr) {
                //cout << "MT: 2" << endl;
                cur += (1 << i);
                v = (*v).to[1];
            }
            else if (cur + (1 << i) >= k) {
                //cout << "MT: 3" << endl;
                v = (*v).to[0];
            }
            else {
                //cout << "MT: 4" << endl;
                return res;
            }
        }
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i == 1)pf[i] = a[i];
        else pf[i] = pf[i - 1] ^ a[i];
    }
    pair<int, int> ans = { -1,0 };
    add(0, 0);
    for (int i = 1; i <= n; i++) {
        int ind = get_cnt(pf[i]);
        //cout << ind << " ";
        ans = max(ans, { i - ind,-ind });
        //cout << ans << endl;
        add(pf[i], i);
        //cout << "AREC";
    }
    cout << -ans.ss + 1 << " " << ans.ff << endl;
    return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

• Subtask 1: 100 / 100