Submission #646306

#	Time	Username	Problem	Language	Result	Execution time	Memory
646306		phoenix	XOR (IZhO12_xor)	C++17	100 / 100	167 ms	59396 KiB

xor

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 250010;
int n, x;
int a[ N ], b[ N ];
 
struct node {
    node* to[ 2 ] = {0};
    int mn = 1e9;
};
node trie;
void add_num(int x, int pos) {
    node* v = &trie;
    for(int i = 29;i >= 0;i--) {
        bool bit = ((x >> i) & 1);
        if(!v->to[bit]) {
            v->to[bit] = new node();
        } 
        v = v->to[bit];
        v->mn = min(v->mn, pos);
    }
}
// x = number, k = end position 
int find(int x, int k) {
    node* v = &trie;
    for(int i = 29;i >= k;i--) {
        v = v->to[((x >> i) & 1)];
        if(!v) return 1e9; 
    }    
    return v->mn;
}
vector<bool> w;
void dfs(node* v) {
    if(!v) return;
    for(bool c : w) cout << c;
    cout << '\n';
    w.push_back(0);
    dfs(v->to[0]);
    w.pop_back();
    w.push_back(1);
    dfs(v->to[1]);
    w.pop_back();
}
 
int ans_i, ans_k;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> x;
    for(int i = 1;i <= n;i++) 
        cin >> a[ i ];
    add_num(0, 0);
    int prefXor = 0;
    for(int i = 1;i <= n;i++) {
        prefXor = (prefXor ^ a[ i ]);
        int lb = i;
        for(int j = 29;j >= 0;j--) {
            int y = (((prefXor ^ x) >> (j + 1)) << (j + 1));
            if(!((x >> j) & 1)) {
                y |= ((!((prefXor >> j) & 1)) << j);
                lb = min(lb, find(y, j));  
            }
        }
        
        lb = min(lb, find((prefXor ^ x), 0));
        if(i - lb > ans_k) ans_k = i - lb, ans_i = lb + 1;         
        else if(i - lb == ans_k) ans_i = min(ans_i, lb + 1);
        add_num(prefXor, i);
    }
    cout << ans_i << ' ' << ans_k;
}

• Subtask 1: 100 / 100