Submission #763578

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
763578	2023-06-22T13:14:49 Z	GrindMachine	XOR (IZhO12_xor)	C++17	100 / 100	108 ms	109896 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	105964 KB	Output is correct
2	Correct	39 ms	105980 KB	Output is correct
3	Correct	39 ms	105936 KB	Output is correct
4	Correct	37 ms	105984 KB	Output is correct
5	Correct	42 ms	106180 KB	Output is correct
6	Correct	42 ms	106280 KB	Output is correct
7	Correct	43 ms	106364 KB	Output is correct
8	Correct	45 ms	106340 KB	Output is correct
9	Correct	59 ms	107464 KB	Output is correct
10	Correct	71 ms	107556 KB	Output is correct
11	Correct	71 ms	107444 KB	Output is correct
12	Correct	60 ms	107476 KB	Output is correct
13	Correct	59 ms	107480 KB	Output is correct
14	Correct	60 ms	107540 KB	Output is correct
15	Correct	60 ms	107552 KB	Output is correct
16	Correct	59 ms	107472 KB	Output is correct
17	Correct	103 ms	109776 KB	Output is correct
18	Correct	108 ms	109888 KB	Output is correct
19	Correct	105 ms	109872 KB	Output is correct
20	Correct	108 ms	109896 KB	Output is correct