Submission #315702

#	Time	Username	Problem	Language	Result	Execution time	Memory
315702		Trickster	XOR (IZhO12_xor)	C++14	0 / 100	1 ms	384 KiB

xor

#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>
 
#define N 1000010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <int, int>
 
using namespace std;

int n, k, sz;
int v[N], F[N];
map <int, int> M;

void upd(int x, int val)
{
	for(; x > 0; x -= (x&(-x))) F[x] = min(F[x], val);
}
int tap(int x)
{
	int ret = 1e9;
	for(; x > 0; x -= (x&(-x))) ret = min(ret, F[x]);
	
	return ret;
}

int main()
{
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++) {
		cin >> v[i], v[i] ^= v[i-1];
		
		M[v[i]] = M[v[i]^k] = 1;
	}
	
	M[0] = 1;
	for(auto &i: M) i.ss = ++sz;
	
	for(int i = 1; i <= sz; i++) F[i] = 1e9;
		
	int ans = 0, in = n+1;
	for(int i = 1; i <= n; i++) {
		upd(M[v[i-1]], i-1);
		
		int pos = tap(M[v[i]^k]);
		
		if(i - pos > ans) {
			ans = i - pos;
			in = pos+1;
		} 
		if(i - pos == ans && in > pos) in = pos+1;
	}
	cout << in << " " << ans;
	
}
/*
4 6
6 1 2 4
*/

• Subtask 1: 0 / 100