Submission #333855

#	Time	Username	Problem	Language	Result	Execution time	Memory
333855		limabeans	XOR (IZhO12_xor)	C++17	0 / 100	1 ms	364 KiB

xor

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


struct node {
    node *ch[2];
    int mx;
    node() {
	ch[0]=ch[1]=NULL;
	mx=0;
    }
};


node *trie;

int n,x;
int a[maxn];


void insert(int idx, int val) {
    node *at = trie;
    for (int i=29; i>=0; i--) {
	at->mx = max(at->mx, idx);
	if (at->ch[val>>i&1] == NULL) {
	    at->ch[val>>i&1] = new node();
	}
	at = at->ch[val>>i&1];
    }
    at->mx = max(at->mx, idx);
}


int dfs(node *at, int i, int suf, bool higher=false) {
    if (at == NULL) {
	return -1;
    }
    if (i==-1) {
	if (!higher) return -1;
	return at->mx;
    }

    int hi = -1;
    for (int b=0; b<2; b++) {
	if (higher || ((suf>>i&1)^b) >= (x>>i&1)) {
	    hi = max(hi, dfs(at->ch[b], i-1, suf, higher || ((suf>>i&1)^b) > (x>>i&1)));
	}
    }

    return hi;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    trie = new node();

    cin>>n>>x;
    for (int i=0; i<n; i++) {
	cin>>a[i];
    }

    
    int suffix = 0;
    insert(n, suffix);

    int ansi = -1;
    int anslen = -1;
    
    for (int i=n-1; i>=0; i--) {
	suffix ^= a[i];
	int to = dfs(trie, 29, suffix, false);
	if (to-i >= anslen) {
	    ansi = i;
	    anslen = to-i;
	}
	insert(i, suffix);
    }


    cout<<ansi+1<<" "<<anslen<<endl;    
    return 0;
}

• Subtask 1: 0 / 100