Submission #101939

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

const int INF = 1000000000;
const int LIM = 1<<20;
// exists[bit][n]
bool exists[20][LIM];
pair<int,int> original[LIM];

void check_upd(pair<int,int> &var, pair<int,int> cand) {
    if(cand.first > cand.second) swap(cand.first, cand.second);
    if(var.first == -INF || var.first == INF || var.second == -INF || var.second == INF) {
        var = cand;
    } else if(cand.first == -INF || cand.first == INF || cand.second == -INF || cand.second == INF) {
        return;
    } else {
        var = min(var, cand);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int N;
    cin >> N;
    fill_n(original, original+LIM, make_pair(INF, -INF));
    for(int i = 0; i < 20; ++i) {
        for(int j = 0; j < LIM; ++j) {
            exists[i][j] = false;
        }
    }

    int acc = 0;
    bool all_zero = true;
    exists[19][0] = true;
    original[0] = make_pair(-1, -1);
    for(int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        if(a != 0) {
            all_zero = false;
        }
        acc ^= a;
        exists[19][acc] = true;
        //cout << acc << endl;
        original[acc].first = min(original[acc].first, i);
        original[acc].second = max(original[acc].second, i);
    }
    if(all_zero) {
        cout << "0 1 1" << endl;
        return 0;
    }
    // construct segtree
    for(int bit = 18; bit >= 0; --bit) {
        const int last = 1 << (bit+1);
        int pos = 0;
        for(int i = 0; i < last; ++i) {
            for(int j = 0; j < 2; ++j) {
                if(exists[bit+1][pos+j]) {
                    //if(!exists[bit][i]) cout << "true " << bit << ' ' << i << endl;
                    exists[bit][i] = true;
                }
            }
            pos += 2;
        }
    }

    // traverse
    pair<int,int> ans(INF, -INF);
    int ans_val = 0;
    for(int i = 0; i < LIM; ++i) {
        if(!exists[19][i]) continue;
        //cout << "for " << i  << endl;
        // [left, right)
        int left = 0, right = 1;
        for(int bit = 0; bit < 20; ++bit) {
            //cout << bit << ' ' << left << ' ' << right << endl;
            int prefer = !(i & (1<<(19-bit)));
            int prefer_idx = (prefer == 0) ? left : right;
            int next = -1;
            if(exists[bit][prefer_idx]) {
                next = prefer_idx;
            } else if(exists[bit][left]) {
                next = left;
            } else if(exists[bit][right]) {
                next = right;
            } else {
                assert(0);
            }
            left = next*2;
            right = left+1;
        }
        const int pos = left/2;
        assert(exists[19][pos]);
        //cout << "select " << pos << endl;
        const int val = i ^ pos;
        if(val >= ans_val) {
            if(val > ans_val) {
                ans = make_pair(INF, -INF);
            }
            const auto &a = original[i];
            const auto &b = original[pos];
            auto cand = make_pair(original[i].first, original[pos].first);
            check_upd(cand, make_pair(original[i].first, original[pos].second));
            check_upd(cand, make_pair(original[i].second, original[pos].first));
            check_upd(cand, make_pair(original[i].second, original[pos].second));
            ans = min(ans, cand);
            //cout << "ans became " << ans.first << ' ' << ans.second << endl;
            ans_val = val;
        }
    }
    cout << ans_val << ' ' << ans.first+2 << ' ' << ans.second+1 << endl;
    return 0;
}

Submission Info

Judge Result