Cerinta completa

Xorq has invented an encryption algorithm which uses bitwise XOR operations extensively. This encryption algorithm uses a sequence of non-negative integers as its key. To implement this algorithm efficiently, Xorq needs to find maximum value of for given integers , and , such that, . Help Xorq implement this function.

For example, , , and . We test each for all values of between and inclusive:

j   x[j]    x[j]^4
1   3       7
2   5       1
3   9       13

Our maximum value is .

Function Description

Complete the xorKey function in the editor below. It should return an integer array where each value is the response to a query.

xorKey has the following parameters:

  • x: a list of integers
  • queries: a two dimensional array where each element is an integer array that consists of for the query at indices and respectively.

Input Format

The first line contains an integer , the number of test cases.
The first line of each test case contains two space-separated integers and , the size of the integer array and the number of queries against the test case.
The next line contains space-separated integers .
Each of next lines describes a query which consists of three integers and .

Constraints




Output Format

For each query, print the maximum value for , such that, on a new line.

Sample Input 0

1
15 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 6 10
1023 7 7
33 5 8
182 5 10
181 1 13
5 10 15
99 8 9
33 10 14

Sample Output 0

13
1016
41
191
191
15
107
47

Explanation 0

  • First Query (10 6 10): . The maximum is .

  • Second Query (1023 7 7):

  • Third Query (33 5 8):

  • Fourth Query (182 5 10):

Limbajul de programare folosit: cpp14

Cod:

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define MAXN 100000
#define MAXQ 50000
#define MAXB 15

struct Trie {
    Trie * next[2];
    vector<int> i;

    Trie() {
        this->next[0] = NULL;
        this->next[1] = NULL;
    }
};

int N, Q;
int n[MAXN];
int a[MAXQ];
int p[MAXQ];
int q[MAXQ];
int m[MAXQ];

Trie * t;

void fill(int v, int i, Trie * c, int r = MAXB) {
    int s = (v & (1 << r)) >> r;

    if (c->next[s] == NULL)
        c->next[s] = new Trie();

    c->i.push_back(i);

    if (r >= 0)
        fill(v, i, c->next[s], r - 1);
}

void calculateMaxValues() {
    memset(m, 0, sizeof(m));
    t = new Trie();

    for (int i = 0; i < N; i++)
        fill(n[i], i + 1, t);

    for (int i = 0; i < Q; i++) {
        int best = 0;

        Trie * c = t;
        for (int j = 15; j >= 0; j--) {
            int b = !((a[i] & (1 << j)) >> j);
            if (c->next[b] != NULL &&
                lower_bound(c->next[b]->i.begin(), c->next[b]->i.end(), p[i]) !=
                upper_bound(c->next[b]->i.begin(), c->next[b]->i.end(), q[i])) {
                best |= b << j;
                c = c->next[b];
            } else {
                best |= (!b) << j;
                c = c->next[!b];
            }
        }

        m[i] = best ^ a[i];
    }
}

int main() {
    int T;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> N >> Q;

        for (int j = 0; j < N; j++)
            cin >> n[j];

        for (int j = 0; j < Q; j++) {
            cin >> a[j];
            cin >> p[j];
            cin >> q[j];
        }

        calculateMaxValues();

        for (int j = 0; j < Q; j++)
            cout << m[j] << endl;
    }

    return 0;
}

Scor obtinut: 1.0

Submission ID: 464613051

Link challenge: https://www.hackerrank.com/challenges/xor-key/problem

XOR key