Submission #503315

# Submission time Handle Problem Language Result Execution time Memory
503315 2022-01-07T16:16:05 Z LucaIlie XOR (IZhO12_xor) C++17
0 / 100
153 ms 131584 KB
#include <iostream>
#include <algorithm>

using namespace std;

#define MAX_N 250000
#define MAX_NORM 16000000
#define MAX_LOG_A 30

int xor_part[MAX_N + 1];

/*struct normalizare {
    struct pozitie {
        int tip, i1, i2, i3;
    };
    struct element {
        int val;
        pozitie poz;

        bool operator < (const element &a) const {
            return val < a.val;
        }
    };

    int size;
    element v[MAX_NORM + 1];
    int ans_xor_part[MAX_N + 1];
    int ans_temp[MAX_N + 1][MAX_LOG_A + 1][2];
    int ans_xor_x[MAX_N + 1];

    void add( element a ) {
        v[size] = a;
        size++;
    }

    void normalizeaza() {
        int val, i;

        sort( v, v + size );

        val = 1;
        for ( i = 0; i < size; i++ ) {
            if ( v[i].poz.tip == 1 )
                ans_xor_part[v[i].poz.i1] = val;
            else if ( v[i].poz.tip == 2 )
                ans_temp[v[i].poz.i1][v[i].poz.i2][v[i].poz.i3] = val;
            else
                ans_xor_x[v[i].poz.i1] = val;
            if ( i < size - 1 && v[i].val != v[i + 1].val )
                val++;
        }
    }
};*/

struct AINT {
    int aint[4 * MAX_NORM];

    void init( int nod, int l, int r ) {
        int mid;

        mid = (l + r) / 2;

        if ( l == r ) {
            aint[nod] = MAX_N + 1;
            return;
        }

        init( nod * 2 + 1, l, mid );
        init( nod * 2 + 2, mid + 1, r );
        aint[nod] = min( aint[nod * 2 + 1], aint[nod * 2 + 2] );
    }

    int query( int nod, int l, int r, int lq, int rq ) {
        int mid;

        mid = (l + r) / 2;

        if ( l > rq || r < lq )
            return MAX_N + 1;
        if ( lq <= l && r <= rq )
            return aint[nod];
        return min( query( nod * 2 + 1, l, mid, lq, rq ), query( nod * 2 + 2, mid + 1, r, lq, rq ) );
    }

    void update( int nod, int l, int r, int p, int x ) {
        int mid;

        mid = (l + r) / 2;

        if ( l > p || r < p )
            return;
        if ( l == r ) {
            aint[nod] = x;
            return;
        }

        update( nod * 2 + 1, l, mid, p, x );
        update( nod * 2 + 2, mid + 1, r, p, x );
        aint[nod] = min( aint[nod * 2 + 1], aint[nod * 2 + 2] );
    }
};

//normalizare norm;
AINT ind;

int main() {
    int n, a, x, y, temp, maxLen, poz, p, i, j;

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

    /*for ( i = 0; i <= n; i++ )
        norm.add( { xor_part[i], { 1, i, 0, 0 } } );

    for ( i = 1; i <= n; i++ ) {
        y = 0;
        for ( p = MAX_LOG_A; p >= 0; p-- ) {
            if ( x & (1 << p) ) {
                if ( (xor_part[i] & (1 << p)) == 0 )
                    y += (1 << p);

            } else {
                temp = y;
                if ( xor_part[i] & (1 << p) )
                    y += (1 << p);
                else
                    temp += (1 << p);
                norm.add( { temp, { 2, i, p, 0 } } );
                norm.add( { temp + (1 << p) - 1, { 2, i, p, 1 } } );
            }
        }
        norm.add( { x ^ xor_part[i], { 3, i, 0, 0 } } );
    }
*/
    //norm.normalizeaza();
    ind.init( 0, 0, MAX_NORM - 1 );

    maxLen = 0;
    poz = -1;
    for ( i = 1; i <= n; i++ ) {
        ind.update( 0, 0, MAX_NORM - 1, xor_part[i - 1], i - 1 );

        y = 0;
        for ( p = MAX_LOG_A; p >= 0; p-- ) {
            if ( x & (1 << p) ) {
                if ( (xor_part[i] & (1 << p)) == 0 )
                    y += (1 << p);

            } else {
                temp = y;
                if ( xor_part[i] & (1 << p) )
                    y += (1 << p);
                else
                    temp += (1 << p);

                j = ind.query( 0, 0, MAX_NORM - 1, temp, temp + (1 << p) - 1 );
                if ( i - j > maxLen ) {
                    maxLen = i - j;
                    poz = j + 1;
                } else if ( i - j == maxLen ) {
                    if ( j + 1 < poz )
                        poz = j + 1;
                }
            }
        }
        j = ind.query( 0, 0, MAX_NORM - 1, xor_part[i] ^ x, xor_part[i] ^ x );
        if ( i - j > maxLen ) {
            maxLen = i - j;
            poz = j + 1;
        } else if ( i - j == maxLen ) {
            if ( j + 1 < poz )
                poz = j + 1;
        }
    }

    cout << poz << " " << maxLen;

    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 118 ms 131584 KB Output is correct
2 Incorrect 153 ms 131508 KB Output isn't correct
3 Halted 0 ms 0 KB -