Submission #320777

#	Time	Username	Problem	Language	Result	Execution time	Memory
320777		SavicS	XOR (IZhO12_xor)	C++14	100 / 100	152 ms	35684 KiB

xor

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(), a.end()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 5000005;
const int inf = 1e9 + 5;

int n, a;

int najm[maxn];

int idx;
int lipa[maxn][2];
bool kraj[maxn];
void add(int x, int id){
    int tr = 0;
    fb(mask,29,0){
        int c = 0;
        if((1 << mask) & x)c = 1;
        if(!lipa[tr][c])lipa[tr][c] = ++idx;
        tr = lipa[tr][c];
        najm[tr] = min(najm[tr], id);
//         cout << "tr: " << tr << endl;
    }
    kraj[tr] = 1;
}
int kve(int x){
    int tr = 0;
    int ans = inf;
    fb(mask,29,0){
        // 1
//        cout << "tr: " << tr << endl;
        if((1 << mask) & a){
            if((1 << mask) & x){
                // 11
//                cout << 11 << endl;
                if(!lipa[tr][0])break;
                tr = lipa[tr][0];
            }
            else{
                // 10
//                cout << 10 << endl;
                if(!lipa[tr][1])break;
                tr = lipa[tr][1];
            }
        }
        // 0
        else{
            if((1 << mask) & x){
                // 01
//                cout << "01" << endl;
                if(lipa[tr][0])ans = min(ans, najm[lipa[tr][0]]);
                if(!lipa[tr][1])break;
                tr = lipa[tr][1];
            }
            else{
                //00
//                cout << "00" << endl;
                if(lipa[tr][1])ans = min(ans, najm[lipa[tr][1]]);
                if(!lipa[tr][0])break;
                tr = lipa[tr][0];
            }
        }
//        cout << endl;
    }
//    cout << "tr: " << tr << endl;
    if(kraj[tr])ans = min(ans, najm[tr]);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin >> n >> a;
    ff(i,0,maxn - 1)najm[i] = inf;
    add(0, 0);
    int pref = 0;
    int len = 0;
    int poz = 0;
    ff(i,1,n){
        int x;
        cin >> x;
        pref ^= x;
        int levo = kve(pref) + 1;
//        cout << "levo: " << levo << endl;
        if(i - levo + 1 > len){
            len = i - levo + 1;
            poz = levo;
        }
        add(pref, i);
    }
    cout << poz << " " << len << endl;
    return 0;
}
/**
4 6
6 1 2 4


1 6
6

4 0
5 5 5 5
**/

• Subtask 1: 100 / 100