oj.uz

Submission #429646

# Submission time Handle Problem Language Result Execution time Memory
429646 2021-06-16T08:19:39 Z SuckTinHock XOR (IZhO12_xor) C++14
100 / 100
 167 ms 25224 KB 
#include <bits/stdc++.h>

using namespace std;
const int INF = INT_MAX;
int Trie[10000005][2];
int minn[10000005];
int n, x, S[250005];
int cnt = 0;
int D[250005];
int resi, resk = 0;

void add(int k, int id)
{
    int node = 0;
    for (int i = 30; i >= 0; --i)
    {
        int c = (k >> i) & 1;
        if (Trie[node][c] == 0)
        {
            Trie[node][c] = ++cnt;
            minn[Trie[node][c]] = id;
        }
        minn[Trie[node][c]] = min(minn[Trie[node][c]], id);
        node = Trie[node][c];
    }
}

int get(int k)
{
    int node = 0;
    int res = INF;
    for (int i = 30; i >= 0; --i)
    {
        int c = (k >> i) & 1;
        int bitx = (x >> i) & 1;
        if (bitx == 1)
        {
            if (Trie[node][1 - c] == 0) return res;
            node = Trie[node][1 - c];
        }
        else
        {
            if (Trie[node][1 - c] != 0) res = min(res, minn[Trie[node][1-c]]);
            if (Trie[node][c] == 0) return res;
            node = Trie[node][c];
        }
    }
    return min(res, minn[node]);
}

void xuly()
{
    add(0,0);
    for (int i = 1; i <= n; ++i)
    {
        D[i] = get(S[i]);
        add(S[i],i);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (D[i] == INF) continue;
        if (resk < i - D[i])
        {
            resk = i - D[i];
            resi = D[i] + 1;
        }
        if (resk == i - D[i])
        {
            resi = min(resi, D[i] + 1);
        }
    }
    cout << resi << " " << resk;
}

void nhap()
{
    int t;
    cin >> n >> x;
    for (int i = 1; i <= n; ++i) cin >> t, S[i] = S[i-1] ^ t;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    nhap();
    xuly();
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 9 ms 1100 KB Output is correct
6 Correct 12 ms 1232 KB Output is correct
7 Correct 9 ms 1232 KB Output is correct
8 Correct 10 ms 1356 KB Output is correct
9 Correct 44 ms 11724 KB Output is correct
10 Correct 49 ms 11864 KB Output is correct
11 Correct 47 ms 11744 KB Output is correct
12 Correct 43 ms 11760 KB Output is correct
13 Correct 41 ms 11716 KB Output is correct
14 Correct 42 ms 11792 KB Output is correct
15 Correct 54 ms 11784 KB Output is correct
16 Correct 55 ms 11752 KB Output is correct
17 Correct 155 ms 25224 KB Output is correct
18 Correct 157 ms 25196 KB Output is correct
19 Correct 147 ms 25204 KB Output is correct
20 Correct 167 ms 25212 KB Output is correct