제출 #1141112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141112		b0udy	XOR (IZhO12_xor)	C++20	0 / 100	4 ms	1864 KiB

xor

#include <bits/stdc++.h>
#include <numeric>



#define Body  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define files    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define clo cout << "Time execute: " << clock()/ (double)CLOCKS_PER_SEC << " sec" << endl;
#define all(ele)  ele.begin(), ele.end()
#define fo(i , n) for (long long int i =0 ; i < n ; i++)
#define ll long long int
#define ull unsigned long long
#define MX INT_MAX
#define MN INT_MIN
#define LMX  LONG_LONG_MAX
#define LMN LONG_LONG_MIN
#define i128 __int128
#define yes cout << "YES";
#define no cout << "NO";
#define X first
#define Y second
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

const int N = 1e5+7, mod = 1e9+7 ;

int k ;

map<int,int>dp[32][2];

struct trie {
    trie *ls[2];
    int cnt;
    int front;
    trie() {
        memset(ls, 0, sizeof(ls));
        cnt = 0;
        front = MX ;
    }
    void insert(ll x , int index) {
        trie *root = this;
        for (int j = 30; ~j; j--) {
            int bit = (x >> j) & 1;
            if (root->ls[bit] == nullptr) root->ls[bit] = new trie();
            root = root->ls[bit];
            root->cnt++;
            root->front = min(root->front , index);
        }
    }

    ll XOR(ll x) {
        trie *root = this;
        return calc(30 , x , 0 , root);
    }
    int calc(int j , int x , int cas , trie* root){
        if (root == nullptr){
            return N ;
        }
        if (cas){
            return root->front;
        }
        if (j == -1) return root->front;
        int res = N ;
        int bit = (x >> j)&1 , bitk = (k >> j)&1 ;
        if (cas == 0){  // care
            if ((bit^bitk) == 0){
                if (bit)
                    res = calc(j-1 , x , 0 , root->ls[0]);
                else
                    res = min(calc(j-1 , x , 0 , root->ls[0]) , calc(j-1 , x , 1 , root->ls[1]));
            }else if (bit){
                res = min(calc(j-1 , x , 1 , root->ls[0]) , calc(j-1 , x , 0 , root->ls[bit]));
            }else{ // bitk == 1
                res = calc(j-1 , x , 0 , root->ls[1]);
            }
        }else{ // not care
            res = min(calc(j-1 , x , cas , root->ls[0]) , calc(j-1 , x , cas , root->ls[1]));
        }
        return res ;
    }
};

void burn() {
    int n ;
    cin >> n >> k ;
    int arr[n+1]{};
    fo(i , n){
        cin >> arr[i+1];
        arr[i+1] ^= arr[i];
    }
    trie trie;
    int idx = 0 , ln = 0 ;
    fo(i , n+1){
        trie.insert(arr[i] , i);
        if (i){
            int st = trie.XOR(arr[i]);
            if (i-st >= ln) idx = st+1 , ln = i-st ;
//            cout << trie.XOR(arr[i]) << ' ';
        }
    }
    cout << idx << ' ' << ln ;

}

int main() {
    Body
//#ifndef ONLINE_JUDGE
//    files
//#endif
    int cas = 1 ;
//    cin >> cas ;
    while (cas--) {
        burn();
        cout << endl;
    }
    return 0;
}

• Subtask 1: 0 / 100