Submission #763578

#	Time	Username	Problem	Language	Result	Execution time	Memory
763578		GrindMachine	XOR (IZhO12_xor)	C++17	100 / 100	108 ms	109896 KiB

xor

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 3e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
const int LOG = 30;

int nxt[N*LOG][2];
int mn_sub[N*LOG];
int ptr = 1;

void insert(int val, int i){
    int u = 0;
    rev(j,LOG-1,0){
        int b = 0;
        if(val & (1 << j)) b = 1;

        if(nxt[u][b] == -1){
            nxt[u][b] = ptr++;
        }

        u = nxt[u][b];
        amin(mn_sub[u], i);
    }
}

int query(int val, int mn_xor){
    int u = 0;
    int res = inf1;

    bool flag = true;

    rev(j,LOG-1,0){
        int b1 = 0;
        if(val & (1 << j)) b1 = 1;

        int b2 = 0;
        if(mn_xor & (1 << j)) b2 = 1;

        if(b2 == 0){
            int other = nxt[u][b1^1];
            if(other != -1){
                amin(res,mn_sub[other]);
            }
        }

        // cout << (b1^b2);
        if(nxt[u][b1^b2] == -1){
            flag = false;
            break;
        }

        u = nxt[u][b1^b2];
    }

    if(flag){
        amin(res,mn_sub[u]);
    }

    return res;
}

void solve(int test_case)
{
    int n,x; cin >> n >> x;
    vector<int> a(n+5);
    rep1(i,n) cin >> a[i];

    vector<int> p(n+5);
    rep1(i,n) p[i] = p[i-1] ^ a[i];

    // rep(i,n+1) cout << p[i] << " ";
    // cout << endl;

    memset(nxt,-1,sizeof nxt);
    memset(mn_sub,0x3f,sizeof mn_sub);

    int mx_len = -inf1;
    int pos = -1;

    rep(i,n+1){
        if(i){
            int j = query(p[i],x);
            int len = i-j;
            if(len > mx_len){
                mx_len = len;
                pos = j+1;
            }
        }

        insert(p[i],i);
    }

    assert(mx_len >= 1);

    cout << pos << " " << mx_len << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

• Subtask 1: 100 / 100