제출 #346972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
346972		nicolaalexandra	XOR (IZhO12_xor)	C++14	100 / 100	345 ms	59528 KiB

xor

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

int v[DIM];
int n,i,sol,x;
struct trie{
    int poz; /// pozitia minima care ajunge prin nodul asta
    trie *f[2];
    trie (){
        f[0] = f[1] = 0;
        poz = n+1;
    }
};

trie *rad;

void add_trie (trie *&rad, int val, int bit){
    if (bit < 0){
        rad->poz = min(rad->poz,i);
        return;
    }

    int nr = 0;
    if (val & (1<<bit))
        nr = 1;

    if (rad->f[nr] == NULL)
        rad->f[nr] = new trie();

    rad->f[nr]->poz = min(rad->f[nr]->poz,i);

    add_trie (rad->f[nr],val,bit-1);

}

void query (trie *&rad, int val, int x, int bit){
    if (bit < 0){
        sol = min (sol,rad->poz);
        return;
    }

    int p = 0;
    if (val & (1<<bit))
        p = 1;

    if (x&(1<<bit)){ /// trb obligatoriu sa am 1
        if (rad->f[p^1] != NULL)
            query (rad->f[p^1],val,x,bit-1);
        else return;
    } else {
        if (rad->f[p^1] != NULL)
            sol = min (sol,rad->f[p^1]->poz);

        if (rad->f[p] != NULL) /// ma duc tot in zero
            query (rad->f[p],val,x,bit-1); /// sunt idioata
        else return;
    }
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>x;

    for (i=1;i<=n;i++){
        cin>>v[i];
        v[i] ^= v[i-1];
    }

    if (n == 1){
        cout<<"1 1";
        return 0;
    }

    rad = new trie();

    int ans = 0, poz = 0;
    for (i=0;i<=n;i++){
        if (i){

            /// care e primul bit de 0 care difera?
            sol = n+1;
            query (rad,v[i],x,30);

            if (i-sol > ans)
                ans = i-sol, poz = sol+1;

        }
        add_trie (rad,v[i],30);
    }


    cout<<poz<<" "<<ans;


    return 0;
}

• Subtask 1: 100 / 100