Submission #418450

#	Time	Username	Problem	Language	Result	Execution time	Memory
418450		Runtime_error_	XOR (IZhO12_xor)	C++14	100 / 100	264 ms	90356 KiB

xor

#include <bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;
const int inf = 25e4+9,lg = 32;
ll n,k,a[inf],pre[inf];
pair<ll,ll> ans;

struct Trie{
    ll cnt = 0,MinIdx = inf;
    Trie *a[2] = {0};
    Trie(){
        cnt = 0,MinIdx = inf;
        a[0] = a[1] = NULL;
    }
    void insert(ll bit,ll num,ll idx){
        cnt++;
        MinIdx = min(MinIdx,idx);
        if(bit == -1)
            return ;
        bool CurBit = num & (1ll<<bit);

        if(a[CurBit] == NULL)
            a[CurBit] = new Trie();
        a[CurBit]->insert(bit-1,num,idx);
    }
    ll query(ll bit,ll PreXor){

        if(cnt == 0 || bit == -1)
            return MinIdx;
        bool PreBit = PreXor & (1ll<<bit);
        bool KBit = k & (1ll<<bit);
        if(a[0] == NULL)
            a[0] = new Trie();
        if(a[1] == NULL)
            a[1] = new Trie();
        if(KBit == 0){
            if(PreBit)
                return min(a[1]->query(bit-1,PreXor),a[0]->MinIdx);
            else
                return min(a[0]->query(bit-1,PreXor),a[1]->MinIdx);
        }
        else {
            if(PreBit)
                return a[0]->query(bit-1,PreXor);
            else
                return a[1]->query(bit-1,PreXor);
        }
    }
};
Trie *root = new Trie();

signed main(){
    scanf("%lld%lld",&n,&k);
    for(ll i=1;i<=n;i++){
        scanf("%lld",a+i);
        pre[i] = pre[i-1]^a[i];
        root->insert(lg,pre[i-1],i-1);
        ans = max(ans,mp(i - root->query(lg,pre[i]),-i));
    }
    assert(ans.first > 0 );
    printf("%lld %lld\n",-ans.second-ans.first+1,ans.first);
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%lld%lld",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
xor.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%lld",a+i);
      |         ~~~~~^~~~~~~~~~~~

• Subtask 1: 100 / 100