Submission #418431

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
418431	2021-06-05T11:21:40 Z	Runtime_error_	XOR (IZhO12_xor)	C++14	0 / 100	9 ms	1996 KB

xor

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

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

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

        if(cnt == 0 || bit == -1)
            return MinIdx;
        bool PreBit = PreXor & (1<<bit);
        bool KBit = k & (1<<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();

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",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));
    }
    printf("%d %d\n",ans.second-ans.first+1,ans.first);
}

Compilation message

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

Subtask #1

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	460 KB	Output is correct
5	Incorrect	9 ms	1996 KB	Output isn't correct
6	Halted	0 ms	0 KB	-