제출 #1171291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171291		hanoon	XOR (IZhO12_xor)	C++20	100 / 100	83 ms	24980 KiB

xor

#include <bits/stdc++.h>

#define ll long long
#define db long double
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int>>
#define vpi vector<pair<int,int>>
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) (int)v.size()
#define fix(n, num) fixed<<setprecision(num)<<n
using namespace std;
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {-1, 1, 0, 0, 1, -1, 1, -1};
const ll N = 5000 + 5, mod = 1e9 + 7, inf = 1e18;

struct node{
    int ch[2]={};
    int idx=1e7;

    int &operator[](int x){
        return ch[x];
    }

};

int k;
struct Trie{
    vector<node>trie;

    void clear(){
        trie.clear();
        trie.emplace_back();
    }
    Trie() {clear();}
    int newNode(){
        trie.emplace_back();
        return sz(trie)-1;
    }

    void insert(int x,int idx){
        int u=0;
        for(int i=30;i>=0;--i){
            int b=x>>i&1;
            if(trie[u][b]==0)
                trie[u][b]=newNode();
            u=trie[u][b];
            trie[u].idx=min(trie[u].idx,idx);
        }
    }

    int calc(int x){
        int u=0;
        int ret=1e7;
        for(int i=30;i>=0;--i){
            int bx=x>>i&1,bk=k>>i&1;
            if(bx+bk==1){
                if(bx) ret=min(ret,trie[trie[u][0]].idx);
                u=trie[u][1];
            }
            else{
                if(!bk) ret=min(ret,trie[trie[u][1]].idx);
                u=trie[u][0];
            }
            if(!u) break;
        }
        return min(ret,trie[u].idx);
    }

};

void TC() {
    int n,p=0;
    cin>>n>>k;
    int ct=0,idx=-1;

    Trie t;
    t.insert(0,0);
    for (int i = 1; i <=n ; ++i) {
        int x;
        cin>>x;
        p^=x;
        int j=t.calc(p);
        if(i-j>ct){
            ct=i-j;
            idx=j;
        }
        t.insert(p,i);
    }

    cout<<idx+1<<' '<<ct;


}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t = 1;
   // cin >> t;
    for (int i = 1; i <= t; ++i) {
        TC();
    }

    return 0;
}

• Subtask 1: 100 / 100