Scribd
Upload
11 views2 pages

Solution

The document contains a C++ program that implements a class called XORBasis, which is used to maintain a basis for the XOR operation. It allows inserting integers into the basis and provides a method to maximize the sum of elements by using the XOR operation. The main function reads an integer array, populates the XORBasis, and outputs the maximum possible sum using the basis.

Uploaded by

Irfan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views2 pages

Solution

The document contains a C++ program that implements a class called XORBasis, which is used to maintain a basis for the XOR operation. It allows inserting integers into the basis and provides a method to maximize the sum of elements by using the XOR operation. The main function reads an integer array, populates the XORBasis, and outputs the maximum possible sum using the basis.

Uploaded by

Irfan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

class XORBasis {

public:

vector<int> basis;

void insert(int num) {

for (int i = 29; i >= 0; --i) {

if ((num >> i) & 1) {

if (basis[i] == 0) {

basis[i] = num;

return;

num ^= basis[i];

int maximizeSum() {

int result = 0;

for (int i = 29; i >= 0; --i) {

if ((result ^ basis[i]) > result) {

result ^= basis[i];

}
return result;

};

int main() {

int N;

cin >> N;

vector<int> A(N);

for (int i = 0; i < N; ++i) {

cin >> A[i];

XORBasis xorBasis;

for (int num : A) {

xorBasis.insert(num);

int result = xorBasis.maximizeSum();

cout << result << endl;

return 0;

You might also like