Submission #335147

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
335147	2020-12-11T08:58:12 Z	iulia13	XOR (IZhO12_xor)	C++14	100 / 100	230 ms	51692 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	35564 KB	Output is correct
2	Correct	24 ms	35564 KB	Output is correct
3	Correct	23 ms	35564 KB	Output is correct
4	Correct	24 ms	35692 KB	Output is correct
5	Correct	34 ms	36076 KB	Output is correct
6	Correct	37 ms	36076 KB	Output is correct
7	Correct	37 ms	36076 KB	Output is correct
8	Correct	41 ms	36096 KB	Output is correct
9	Correct	94 ms	42476 KB	Output is correct
10	Correct	98 ms	43008 KB	Output is correct
11	Correct	93 ms	42988 KB	Output is correct
12	Correct	93 ms	42988 KB	Output is correct
13	Correct	97 ms	42980 KB	Output is correct
14	Correct	94 ms	42988 KB	Output is correct
15	Correct	94 ms	42988 KB	Output is correct
16	Correct	95 ms	42988 KB	Output is correct
17	Correct	230 ms	51692 KB	Output is correct
18	Correct	226 ms	51584 KB	Output is correct
19	Correct	225 ms	51564 KB	Output is correct
20	Correct	229 ms	51564 KB	Output is correct