Submission #1020921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020921		Minbaev	XOR (IZhO12_xor)	C++17	0 / 100	1 ms	348 KiB

xor

// C++ program for a Trie based O(n) solution to find max
// subarray XOR
#include<bits/stdc++.h>
using namespace std;

// Assumed int size
#define INT_SIZE 32

int k;

// A Trie Node
struct TrieNode
{
	int value, ind; // Only used in leaf nodes
	TrieNode *arr[2];
};

TrieNode *newNode()
{
	TrieNode *temp = new TrieNode;
	temp->value = 0;
	temp->ind = -1;
	temp->arr[0] = temp->arr[1] = NULL;
	return temp;
}

void insert(TrieNode *root, int pre_xor, int id)
{
	TrieNode *temp = root;

	for (int i=INT_SIZE-1; i>=0; i--)
	{
		
		bool val = pre_xor & (1<<i);

		if (temp->arr[val] == NULL)
			temp->arr[val] = newNode();

		temp = temp->arr[val];
	}
	temp->ind = id;
	temp->value = pre_xor;
}

int query(TrieNode *root, int pre_xor, int r)
{
	TrieNode *temp = root;
	int mx = 0;
	for (int i=INT_SIZE-1; i>=0; i--)
	{
		bool val = pre_xor & (1<<i);

		if (temp->arr[1-val]!=NULL)
			temp = temp->arr[1-val];

		else if (temp->arr[val] != NULL)
			temp = temp->arr[val];
		
		
		//~ cout << r << " " << temp->value << "\n";
		
	//~ cout << temp->ind << " " << r << " " << temp->value << " " << pre_xor  << " " << (pre_xor^(temp->value)) << " " << r-(temp->ind)+1 << "\n";
	}
	if((temp->ind) > -1 && (pre_xor^(temp->value)) >= k)mx = max(mx, r-(temp->ind));	
	//~ cout << temp->ind << " " << r << " " << temp->value << " " << pre_xor  << " " << (pre_xor^(temp->value)) << " " << "\n";
	return mx;
}

// Returns maximum XOR value of a subarray in arr[0..n-1]
pair<int,int> maxSubarrayXOR(vector<int> arr, int n)
{
	// Create a Trie and insert 0 into it
	TrieNode *root = newNode();
	insert(root, 0, -1);

	int result = INT_MIN, pre_xor =0;
	int ind = 0;

	for (int i=0; i<n; i++)
	{
		pre_xor = pre_xor^arr[i];
		insert(root, pre_xor, i);

		if(query(root, pre_xor, i) > result){
			result = query(root, pre_xor, i);
			ind = i - result + 2;
		}
	}
	return {ind,result};
}

// Driver program to test above functions
int main()
{	
	int n;
	cin >> n >> k;
	vector<int>arr(n);
	for(int i = 0;i<n;i++)cin >> arr[i];
	pair<int,int> p = maxSubarrayXOR(arr, n);
	cout << p.first << " " << p.second << "\n";
	return 0;
}

• Subtask 1: 0 / 100