Submission #384586

#	Time	Username	Problem	Language	Result	Execution time	Memory
384586		zoooma13	XOR (IZhO12_xor)	C++14	100 / 100	162 ms	23404 KiB

xor

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 250005

int tr[3][30*MAX_N] ,root ,nn ,k;
void add(int&p ,int a ,int i ,int b = 30){
    if(p == 0){
        p = ++nn;
        tr[2][p] = i;
    }
    if(b == -1)
        return;
    add(tr[a>>b&1][p] ,a ,i ,b-1);
}
int ask(int&p ,int a ,int b = 30){
    if(p == 0) return 1e9;
    if(b == -1) return tr[2][p];
    int ret = 1e9;
    bool s = k>>b&1 ,t = a>>b&1;
    if(s)
        ret = min(ret ,ask(tr[!t][p] ,a ,b-1));
    else
        ret = min({ret ,tr[2][tr[!t][p]] ,ask(tr[t][p] ,a ,b-1)});
    return ret;
}

int main()
{
    int n ,xr = 0;
    scanf("%d%d",&n,&k);
    tr[2][0] = 1e9;
    add(root ,0 ,0);
    pair <int ,int> ans = {-1e9 ,-1e9};
    for(int a ,i=1; i<=n; i++){
        scanf("%d",&a) ,xr ^= a;
        int b = ask(root ,xr);
        ans = max(ans ,make_pair(i-b ,-b-1));
        add(root ,xr ,i);
    }
    printf("%d %d\n",-ans.second,ans.first);
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100