Submission #321610

#	Time	Username	Problem	Language	Result	Execution time	Memory
321610		iliccmarko	XOR (IZhO12_xor)	C++14	100 / 100	197 ms	140268 KiB

xor

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];}
#define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;}
#define single_case solve();
#define line cout<<"------------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); }
using namespace std;
const int N = 250005;
int n;
pair<int, int> trie[N*35][2];
int ind;
int prefix[N];
int x;

void _insert(int xx, int u)
{
    int node = 0;
    for(int i = 29;i>=0;i--)
    {
        int bit = (xx>>i)&1;
        if(trie[node][bit].second==-1) trie[node][bit] = make_pair(u, ++ind);
        else
            trie[node][bit].first = min(trie[node][bit].first, u);
        node = trie[node][bit].second;
    }
}

int resi(int u)
{
    int xx = prefix[u];
    int m = u;
    int node = 0;
    for(int i = 29;i>=0;i--)
    {
        int bit = ((x>>i)&1)^((xx>>i)&1);
        if(!((x>>i)&1))
        {
            if(trie[node][1^(((xx>>i)&1))].second!=-1)
            {
                m = min(m, trie[node][1^(((xx>>i)&1))].first);
            }
        }
        if(trie[node][bit].second==-1) {/*cout<<u<<"    "<<i<<" "<<endl;*/ return m;}
        if(i==0)
            m = min(trie[node][bit].first, m);
        node = trie[node][bit].second;
    }
    return m;
}

int main()
{
    ios
    cin>>n>>x;
    for(int i = 0;i<N*35;i++)
        trie[i][0].second = trie[i][1].second = -1;
    int last = 0;
    for(int i = 0;i<n;i++)
    {
        int xx;
        cin>>xx;
        prefix[i] = last ^ xx;
        last = prefix[i];
        _insert(prefix[i], i);
    }

    int ans = 0;
    int index;
    for(int i = 0;i<n;i++)
    {
        int k = resi(i) + 1;
        if(i - k + 1 > ans)
        {
            ans = i - k + 1;
            index = k;
        }
    }

    cout<<index+1<<" "<<ans;








    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:88:20: warning: 'index' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |     cout<<index+1<<" "<<ans;
      |                    ^~~

• Subtask 1: 100 / 100