Submission #1304412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304412		Robert_junior	XOR (IZhO12_xor)	C++20	100 / 100	127 ms	50660 KiB

xor

#include <bits/stdc++.h>
using namespace std;
#define pb push_back  
#define all(x) x.begin(), x.end()
#define ins insert
#define F first
#define S second
#define ld double
#define bt bitset<15001>bt;
const int N = 3e5, inf = 1e18, mod = 1e9 + 7;
int L[N * 30], R[N * 30], t[N * 30], timer = 1, a[N];
void add(int x, int vl){
    int v = 1;
    for(int i = 30; i >= 0; i--){
        t[v] = min(t[v], vl);
        if((x>>i) & 1){
            if(!L[v]) L[v] = ++timer;
            v = L[v];
        }
        else{
            if(!R[v]) R[v] = ++timer;
            v = R[v];
        }
        t[v] = min(t[v], vl);
    }
}
int get(int vl, int x){
    int v = 1, cur = 0, res = INT_MAX;
    for(int i = 30; i >= 0; i--){
        if(cur + (1<<i) >= x){
            if((vl>>i) & 1){
                res = min(res, t[R[v]]);
                v = L[v];
            }
            else{
                res = min(res, t[L[v]]);
                v = R[v];
            }
        }
        else{
            cur |= (1<<i); 
            if((vl>>i) & 1){
                v = R[v];
            }
            else{
                v = L[v];
            }
        }
    }
    return res;
}
void solve(){
    for(int i = 0; i < N * 30; i++){
        t[i] = INT_MAX;
    }
    add(0, 0);
    int n, x;
    cin>>n>>x;
    pair<int, int>ans = {0, 0}; 
    int cur = 0;
    for(int i = 1; i <= n; i++){
        cin>>a[i]; 
        cur ^= a[i];
        int l = get(cur, x);
        add(cur, i);
        if(i - l > ans.S){
            ans = {l + 1, i - l};
        }
    }
    cout<<ans.F<<' '<<ans.S<<'\n'; 
}
signed main(){
	//freopen("time.in", "r", stdin);
    //freopen("time.out", "w", stdout);
	ios_base :: sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    // abccbaabccccba
}

Compilation message (stderr)

xor.cpp:10:26: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   10 | const int N = 3e5, inf = 1e18, mod = 1e9 + 7;
      |                          ^~~~

• Subtask 1: 100 / 100