Submission #503331

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
503331	2022-01-07T16:32:27 Z	LucaIlie	XOR (IZhO12_xor)	C++17	0 / 100	2000 ms	69652 KB

xor

#include <iostream>
#include <algorithm>
#include <vector>

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, maxVal;
    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 i;

        sort( v, v + size );

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


struct AINT {
    vector <int> aint;

    void init( int size ) {
        int i;

        for ( i = 0; i < 4 * size; i++ )
            aint.push_back( MAX_N + 1 );
    }

    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( norm.maxVal );

    maxLen = 0;
    poz = -1;
    for ( i = 1; i <= n; i++ ) {
        ind.update( 0, 0, norm.maxVal, norm.ans_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 {

                if ( xor_part[i] & (1 << p) )
                    y += (1 << p);

                j = ind.query( 0, 0, norm.maxVal, norm.ans_temp[i][p][0], norm.ans_temp[i][p][1] );
                for ( j = 0; j < i; j++ ) {
                    if ( norm.ans_temp[i][p][0] <= norm.ans_xor_part[j] && norm.ans_xor_part[j] <= norm.ans_temp[i][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, norm.maxVal, norm.ans_xor_x[i], norm.ans_xor_x[i] );
        for ( j = 0; j < i; j++ ) {
            if ( norm.ans_xor_x[i] == norm.ans_xor_part[j] ) {
                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;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	460 KB	Output is correct
4	Correct	7 ms	1356 KB	Output is correct
5	Correct	460 ms	9288 KB	Output is correct
6	Correct	1058 ms	13400 KB	Output is correct
7	Correct	810 ms	12644 KB	Output is correct
8	Correct	1088 ms	13892 KB	Output is correct
9	Execution timed out	2078 ms	69652 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-