Submission #508535

#	Time	Username	Problem	Language	Result	Execution time	Memory
508535		sidon	XOR (IZhO12_xor)	C++17	0 / 100	2077 ms	127172 KiB

xor

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

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int N, X, pref, ind, k;
unordered_map<int, int, custom_hash> t[30];

void minim(int l, int r) {
	if(l && r-l > k) k = r-l, ind = l;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> N >> X;

	for(int i = 1; i <= N + 1; i++) {
		int u = 0;
		for(int j = 30; --j >= 0; ) {
			if(X & (1<<j)) {
				if(!(pref & (1<<j))) u ^= 1<<j;
				if(!j) minim(t[j][u], i);
			} else {
				if(pref & (1<<j)) minim(t[j][u], i), u ^= 1<<j;
				else minim(t[j][u ^ (1<<j)], i);
			}
		}
		minim(t[0][u], i);
		int v = 0;
		for(int j = 30; --j >= 0; ) {
			if(pref & (1<<j)) v |= 1<<j;
			t[j][v] = t[j][v] ? : i;
		}

		cin >> v;
		pref ^= v;
	}
	if(!X) ind = 1, k = N;

	cout << ind << ' ' << k;
}

• Subtask 1: 0 / 100