제출 #763592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
763592		NK_	XOR (IZhO12_xor)	C++17	100 / 100	148 ms	57476 KiB

xor

#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

const int INF = 1e9+10;

struct Trie {
	int smallest_index; // smallest index of a value in this sub-trie
	Trie* children[2]; // (either 0 or 1)
	Trie() { smallest_index = INF; children[0] = children[1] = NULL; }

	void insert_value(int value, int index, int bit = 30) {
		// inserts x into the trie
		smallest_index = min(smallest_index, index); // update smallest index in sub-trie

		if (bit == -1) return;
		int value_bit = (value >> bit) & 1;

		if (!children[value_bit]) children[value_bit] = new Trie(); // create node if needed

		children[value_bit]->insert_value(value, index, bit - 1); // recurse from child node
	}

	int find_smallest_index(int x, int y, int bit = 30) { 
		// returns smallest index such that P xor x >= y, where P is a element in the trie
	
		if (bit == -1) return INF;
		int current_answer = INF;

		int x_bit = (x >> bit) & 1, y_bit = (y >> bit) & 1; // get b-th bits of x and y

		int p_bit = x_bit ^ 1; // want to maximize P xor x hence want to have opposite bits (if possible)

		if (!children[p_bit]) p_bit ^= 1; // not possible (must go to other option)

		if ((x_bit ^ p_bit) < y_bit) {
			return INF; // cannot have (P xor x) < y at any level
		}

		if ((x_bit ^ p_bit) > y_bit) {
			// already have P xor x > y, hence all other bits don't matter

			current_answer = min(current_answer, children[p_bit]->smallest_index); 
			// take smallest index in the sub-trie

			p_bit ^= 1; // continue down other possibility 
		}

		if (!children[p_bit]) return current_answer; // cannot go further down

		if (bit == 0) { // reached equality
			current_answer = min(current_answer, children[p_bit]->smallest_index); // take possible answer
		}

		current_answer = min(current_answer, children[p_bit]->find_smallest_index(x, y, bit - 1));

		return current_answer;
	}
		
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, X; cin >> N >> X;
	vector<int> seq(N); for(auto& x : seq) cin >> x;

	Trie trie;
	int current_xor = 0; trie.insert_value(current_xor, -1);

	int answer = 0, best_index = -1;
	for(int index = 0; index < N; index++) {
		current_xor ^= seq[index];

		int position = trie.find_smallest_index(current_xor, X); // get best position 

		if (answer < (index - position)) { // check if its a better answer
			answer = (index - position);
			best_index = position + 1; // position is exclusive
		}

		trie.insert_value(current_xor, index);
	}

	cout << best_index + 1 << " " << answer << nl;

    return 0;
}

• Subtask 1: 100 / 100