Submission #335147

#	Time	Username	Problem	Language	Result	Execution time	Memory
335147		iulia13	XOR (IZhO12_xor)	C++14	100 / 100	230 ms	51692 KiB

xor

#include <iostream>

using namespace std;
const int NMAX = 3e5 * 30;
int trie[NMAX + 5];
int nxt[NMAX + 5][2];
int best[NMAX + 5];
int cnt = 0, x;

void add_trie(int val, int poz)
{
    int nod = 0;
    best[nod] = min(best[nod], poz);
    for (int i = 30; i >= 0; i--)
    {
        int st;
        if (val & (1 << i))
            st = 1;
        else
            st = 0;
        if (!nxt[nod][st])
            nxt[nod][st] = ++cnt;
        nod = nxt[nod][st];
        best[nod] = min(best[nod], poz);
    }
}
//int x;
int query(int val)
{
    int nod = 0, ans = 2e9, ok = 1;
    for (int i = 30; i >= 0 && ok; i--)
    {
        int st;
        if (val & (1 << i))
            st = 0;
        else
            st = 1;
        if (!(x & (1 << i)))
        {
            if (nxt[nod][st])
                ans = min(ans, best[nxt[nod][st]]);
            st = 1 ^ st;
        }
        nod = nxt[nod][st];
        if (!nod)
            ok = 0;
    }
    return ans;
}
int main()
{
    int n, xo = 0, sol = 0, ind;
    cin >> n >> x;
    for (int i = 0; i <= NMAX; i++)
        best[i] = 2e9;
    add_trie(xo, 0);
    x--;
    for (int i = 1; i <= n; i++)
    {
        int nr;
        cin >> nr;
        xo ^= nr;
        int ans = query(xo);
        add_trie(xo, i);
        if (i - ans > sol)
        {
            sol = i - ans;
            ind = ans + 1;
        }
    }
    cout << ind << " " << sol;
    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:71:20: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |     cout << ind << " " << sol;
      |                    ^~~

• Subtask 1: 100 / 100