Submission #1131343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131343		SSKMF	XOR (IZhO12_xor)	C++20	100 / 100	179 ms	56480 KiB

xor

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

struct Nod {
    int minim = INT32_MAX;
    Nod *stanga = NULL , *dreapta = NULL;
} *radacina = new Nod;

inline void Insert (Nod* &nod , const int valoare , const int candidat , const int putere)
{
    nod -> minim = min(nod -> minim , candidat);
    if (putere == 0)
        { return; }

    if (valoare & putere)
    {
        if (!nod -> dreapta)
            { nod -> dreapta = new Nod; }
        
        Insert(nod -> dreapta , valoare , candidat , putere >> 1);
    }
    else
    {
        if (!nod -> stanga)
            { nod -> stanga = new Nod; }
        
        Insert(nod -> stanga , valoare , candidat , putere >> 1);
    }
}

inline int Query (Nod* &nod , const int termen , const int minim , const int putere)
{
    if (nod == NULL)
        { return INT32_MAX; }

    if (putere == 0)
        { return nod -> minim; }

    if (minim & putere)
        { return Query((termen & putere) ? nod -> stanga : nod -> dreapta , termen , minim , putere >> 1); }
    
    int candidat = Query((termen & putere) ? nod -> dreapta : nod -> stanga , termen , minim , putere >> 1);
    if (((termen & putere) ? nod -> stanga : nod -> dreapta) != NULL)
        { candidat = min(candidat , ((termen & putere) ? nod -> stanga : nod -> dreapta) -> minim); }

    return candidat;
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int lungime , minim;
    cin >> lungime >> minim;

    int inceput = -1 , maxim = INT32_MIN;
    Insert(radacina , 0 , 0 , (1 << 29));
    for (int indice = 1 , valoare , suma = 0 ; indice <= lungime ; indice++)
    {
        cin >> valoare;

        suma ^= valoare;
        
        const int candidat = Query(radacina , suma , minim , (1 << 29));
        if (indice - candidat > maxim)
            { inceput = candidat + 1; maxim = indice - candidat; }

        Insert(radacina , suma , indice , (1 << 29));
    }

    cout << inceput << ' ' << maxim;
    return 0;
}

• Subtask 1: 100 / 100