제출 #1168708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168708		ZeroCool	XOR (IZhO12_xor)	C++20	0 / 100	97 ms	97344 KiB

xor

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
#define all(v) v.begin(),v.end()
#define ar array

const int M = 1e6;
const int N = 2e5 + 20;
const int LOG = 31;
const int INF = 1e18;
const int MOD = 1e9 + 7;
const ld EPS = 1e-9;
inline void mm(int &x){x = (x % MOD + MOD) % MOD;}
inline void chmin(int &x, int y){x = min(x, y);}
inline void chmax(int &x, int y){x = max(x, y);}

#pragma GCC optimize("unroll-loops,O3")

int n, x;

int g[N * LOG][2];
int T = 1;

int qry(int x,int u, int i){
    if(i < 0)return 0;
    bool j = (1ll << i) & x;
    if(g[u][j ^ 1])return (1ll << i) | qry(x, g[u][j ^ 1], i - 1);
    else if(g[u][j])return qry(x, g[u][j], i - 1);
    return 0;
}

void ins(int x,int u, int i){
    if(i < 0)return;
    bool j = (1ll << i) & x;
    //cout<<j;
    if(g[u][j])ins(x, g[u][j], i - 1);
    else ins(x, g[u][j] = T++, i - 1);
}

void orz(){
    cin>>n>>x;
    int A[n + 1] = {0};
    for(int i = 1;i <= n;i++)cin>>A[i];
    for(int i = 1;i <= n;i++)A[i] ^= A[i - 1];
    
    auto koce = [&](int mid) -> bool {
        memset(g, 0, sizeof g);
        T = 1;
        for(int i = mid;i <= n;i++){
           // cout<<A[i - mid]<<": ";
            ins(A[i - mid], 0, LOG - 1);
           // cout<<'\n';
            if(qry(A[i], 0, LOG - 1) >= x)return 1;
        }
        return 0;
    };  

    int lo = 0, hi = n + 1;
    while(hi - lo > 1){
        int mid = (lo + hi) / 2;
        if(koce(mid))lo = mid;
        else hi = mid;
    }
   // cout<<lo;
    for(int i = lo;i <= n;i++){
        if(A[i - lo] ^ A[i] >= x){
            cout<<i - lo + 1<<" "<<lo;
            return;
        }
    }
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
   
    int t = 1;
    //cin>>t;
    while(t--)orz();
} 

• Subtask 1: 0 / 100