제출 #1369995

#제출 시각아이디문제언어결과실행 시간메모리
1369995ropraiteXOR (IZhO12_xor)C++20
100 / 100
161 ms56644 KiB
// That is not your swag, I swear you fake hard
#define Mo2 ios_base::sync_with_stdio(false) , cin.tie(NULL) , cout.tie(NULL);
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define tru ? cout<<"YES\n" : cout<<"NO\n"
#define int long long
const int N = 1e5+5 , OO = 0x3f3f3f3f3f3f3f3f , mod = 1e9+7;

// math problems are solved using math
// slow is smooth, smooth is fast

int k;

struct trie {
    struct node {
        node*ch[2];
        int min_idx;
        node () {
            memset(ch,0,sizeof ch);
            min_idx = OO;
        }
    };
    node*root = new node();
    void insert (int x , int indx) {
        node*cur = root;
        vector <node*> path;
        for(int i = 30 ; ~i ; --i) {
            bool idx = x >> i & 1;
            if(cur->ch[idx] == 0) cur->ch[idx] = new node();
            cur = cur->ch[idx];
            path.push_back(cur);    
        }
        for(auto &p : path) p->min_idx = min(p->min_idx,indx);
    }
    int get (int x) {
        int ans = OO;
        node*cur = root;
        for(int i = 30 ; ~i ; --i) {
            bool btk = k >> i & 1;
            bool btx = x >> i & 1;
            if(!btk) {
                // u can place either 0 or 1
                int op1 = OO, op2 = OO;
                if(cur->ch[0]) op1 = cur->ch[0]->min_idx;
                if(cur->ch[1]) op2 = cur->ch[1]->min_idx;
                if(min(op1,op2) == OO) return op1;
                if(op1 < op2) ans = op1, cur = cur->ch[0];
                else ans = op2, cur = cur->ch[1];
            }
            else {
                // u should place ! btx
                if(cur->ch[!btx] == 0) return OO;
                ans = cur->ch[!btx]->min_idx;
                cur = cur->ch[!btx];
            }
        }
        return ans;
    }
}tr;

signed main() { 
    Mo2
    // انتو اعدائي
    int n,c,st=OO,XOR=0,ans=0; cin>>n>>k;
    tr.insert(XOR,0);
    for(int i = 1,x ; i <= n ; ++i) {
        cin>>x;
        XOR ^= x;
        c = i - tr.get(XOR);
        if(c > ans) {
            ans = c;
            st = i - c + 1;
        }
        else if(c == ans) st = min(st, i - c + 1);
        tr.insert(XOR,i);
    }
    cout<<st<<' '<<ans<<endl;
    return (0-0);
}   
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…