Submission #1299183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299183		ahanf	XOR (IZhO12_xor)	C++20	100 / 100	365 ms	88808 KiB

xor

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
// Macros
#define REP(i, j, n) for(int i = j; i < n; i++)
#define trav(i, a) for(auto i: a)
#define all(x) x.begin(), x.end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define F first
#define S second
#define GCD __gcd
#define DEBUG(i) cout << "DEBUG " << i << "\n";
#define CASE(i) cout << "Case " << i << ": ";
#define MEM(arr, val) memset(arr, val, sizeof(arr));
 
// Type Names
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef long double ld;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, 
tree_order_statistics_node_update> ordered_multiset;
 
// functions
template <typename T>
void pv(vector<T> &a){
    for (auto elem: a){
        cout << elem << " ";
    }
    cout << "\n";
}

// Global Variables
const ll MOD = 1e9 + 7;
const ll mod = 998244353;
const ll INF = 1e9 + 1;

ll n, k;

struct TrieNode {

    TrieNode *children[2];
    TrieNode *parent;
    int mnidx;

    TrieNode(){
        parent = nullptr;
        for (int i = 0; i < 2; i++){
            children[i] = nullptr;
        }
        mnidx = n + 1;
    }

};

void insert(TrieNode *root, ll x, int idx){

    TrieNode *curr = root;

    string key = bitset<31>(x).to_string();

    for (char c: key){
        if (curr->children[c - '0'] == nullptr){
            curr->children[c - '0'] = new TrieNode();
            curr->children[c - '0']->parent = curr;
        }
        curr = curr->children[c - '0'];
    }

    curr->mnidx = min(curr->mnidx, idx);
    while (curr->parent != nullptr){
        curr = curr->parent;
        curr->mnidx = min(curr->mnidx, idx);
    }

}

int query(TrieNode *root, ll x){

    TrieNode *curr = root;
    string key = bitset<31>(x).to_string();
    string tar = bitset<31>(k).to_string();

    int ret = n + 10;

    for (int i = 0; i < 31; i++){
        if (tar[i] == '1'){
            if (curr->children[('1' - key[i])] == nullptr) break;
            curr = curr->children[('1' - key[i])];
        }
        else {
            if (curr->children[('1' - key[i])] != nullptr) {
                ret = min(ret, curr->children[('1' - key[i])]->mnidx);
            }
            if (curr->children[key[i] - '0'] == nullptr) break;
            curr = curr->children[key[i] - '0'];
        }
    }

    return ret;

}

void solve(int tc){

    cin >> n >> k;

    if (k == 0){
        cout << 1 << " " << n << "\n";
        return;
    }

    k--;

    vll a(n), pref(n + 1);

    REP(i, 0, n) cin >> a[i];

    for (int i = 1; i <= n; i++){
        pref[i] = (a[i - 1] ^ pref[i - 1]);
    }

    TrieNode *trie = new TrieNode();

    int idx = 0, len = 0;

    insert(trie, pref[0], 0);

    for (int i = 1; i <= n; i++){
        int res = query(trie, pref[i]);
        if (i - res > len){
            idx = res + 1;
            len = i - res;
        }
        insert(trie, pref[i], i);
    }

    cout << idx << " " << len << "\n";

}   




int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    // pre();
    // freopen("inputf.in", "r", stdin);
    // freopen("outputf.out", "w", stdout);
    int i = 1;
    // int t = 1;
    // cin >> t;
    // for(i = 1; i <= t; i++)
    solve(i);
    return 0;
}

• Subtask 1: 100 / 100