Submission #966142

#	Time	Username	Problem	Language	Result	Execution time	Memory
966142		dosts	XOR (IZhO12_xor)	C++17	100 / 100	106 ms	24716 KiB

xor

//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 2e5+100,inf = INT_MAX,MOD = 1e9+7,LIM = 3e7+1;

int curnode = 1;
struct Node {
    int c[2],mx;
};

Node nds[LIM];
int walk(Node* cur, int x,int k,int bit = 29) { 
    if (bit == -1) return k?0:cur->mx;
    //x ile xor layınca en az k gelmesi lzm
    if (k & (1<<bit)) {
        int go = !(x&(1<<bit));
        if (cur->c[go]) return walk(nds+cur->c[go],x,k^(1<<bit),bit-1);
        else return 0;
    }
    else {
        int go = !(x&(1<<bit));
        int ans = 0;
        if (cur->c[go]) ans = max(ans,nds[cur->c[go]].mx);
        ans = max(ans,walk(nds+cur->c[!go],x,k,bit-1));
        return ans;
    }
}
 
void insert(int x,int p) {
    Node* cur = nds+1;
    for (int i=29;i>=-1;i--) {
        cur->mx = max(cur->mx,p);
        if (i > -1) {
            bool go = !!(x&(1<<i));
            if (!cur->c[go]) cur->c[go] = ++curnode;
            cur = nds+cur->c[go];
        }
    }
}

 



void solve() {
    int n,x;
    cin >> n >> x;
    vi a(n+1),p(n+1,0);
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<=n;i++) p[i] = p[i-1]^a[i];
    int ans = 0,start = 0;
    for (int i=n;i>=1;i--) {
        insert(p[i],i);
        int xx = walk(nds+1,p[i-1],x);
        if (xx-i+1 >= ans) {
            ans = xx-i+1;
            start = i;
        }
    }
    cout << start sp ans << endl;
}
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

• Subtask 1: 100 / 100