Submission #1224733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224733		Kerim	XOR (IZhO12_xor)	C++17	0 / 100	0 ms	324 KiB

xor

#include "bits/stdc++.h"
#define ll long long
using namespace std;

const int N = 250005;
const int LOG = 30;

int id, tree[N*LOG][2], sub[N*LOG];
int p[N];

void add(int x, int ind){
    int cur_node = 0;
    for (int i = LOG-1; i >= 0; i--){
        int bit = (x>>i&1);
        if (!tree[cur_node][bit])
            tree[cur_node][bit] = ++id;
        cur_node = tree[cur_node][bit];
        sub[cur_node] = ind;
    }
}

// b^value >= a
//p[r]^p[l-1]>=x
int query(int a, int b){
    int cur_node = 0;
    int answer = 1e9;
    for (int i = LOG-1; i >= 0; i--){
        int a_bit = (a>>i&1);
        int b_bit = (b>>i&1);
        int to_node = 0;
        for (int v_bit = 0; v_bit < 2; v_bit += 1){
            if (!tree[cur_node][v_bit])
                continue;
            if ((b_bit ^ v_bit) > a_bit)
                answer = min(answer, sub[tree[cur_node][v_bit]]);
            else if((b_bit ^ v_bit) == a_bit)
                to_node = tree[cur_node][v_bit];
        }
        if (!to_node)
            return answer;
        cur_node = to_node;
    }
    // b^value=a
    return min(answer, sub[cur_node]);
}
int main(){
    // freopen("file.in", "r", stdin);
    int n, x;
    scanf("%d%d", &n, &x);
    for (int i = 1; i <= n; i++){
        int x;
        scanf("%d", &x);
        p[i] = p[i-1]^x;
    }
    int k = 0, ind;
    //p[r]^p[l-1]>=x
    //p[r]^value>=x, minimum(index)
    //add(p[l-1], l) = add(value, index);
    for (int r = 1; r <= n; r++){
        add(p[r-1], r);//r=l
        int l = query(x, p[r]);
        if (l <= r){
            if (r-l+1 > k)
                k = r-l+1, ind = l;
            else if(r-l+1 == k)
                ind = min(ind, l);
        }
    }
    printf("%d %d\n", ind, k);
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d%d", &n, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~
xor.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 100