Submission #346972

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
346972	2021-01-11T13:05:07 Z	nicolaalexandra	XOR (IZhO12_xor)	C++14	100 / 100	345 ms	59528 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	13 ms	1912 KB	Output is correct
6	Correct	17 ms	2156 KB	Output is correct
7	Correct	18 ms	2156 KB	Output is correct
8	Correct	21 ms	2412 KB	Output is correct
9	Correct	114 ms	28012 KB	Output is correct
10	Correct	111 ms	28140 KB	Output is correct
11	Correct	112 ms	28012 KB	Output is correct
12	Correct	109 ms	27948 KB	Output is correct
13	Correct	114 ms	28116 KB	Output is correct
14	Correct	111 ms	28120 KB	Output is correct
15	Correct	113 ms	28012 KB	Output is correct
16	Correct	120 ms	28012 KB	Output is correct
17	Correct	345 ms	59428 KB	Output is correct
18	Correct	299 ms	59528 KB	Output is correct
19	Correct	289 ms	59500 KB	Output is correct
20	Correct	309 ms	59372 KB	Output is correct