Submission #58113

#	Time	Username	Problem	Language	Result	Execution time	Memory
58113		Benq	XOR (IZhO12_xor)	C++14	100 / 100	170 ms	29392 KiB

xor

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

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 250001;

int n,x,cum[MX];

template<int MX> struct tri {
    static const int MXBIT = 30;
    int trie[MX][2], mn[MX], nex = 0; // easily changed to character
    
    void ins(int ind, int a = 1) { // insert or delete
        int x = cum[ind];
        int cur = 0;
        F0Rd(i,MXBIT) {
            int t = (x&(1LL<<i))>>i;
            if (!trie[cur][t]) {
                trie[cur][t] = ++nex;
                mn[nex] = ind;
                trie[nex][0] = trie[nex][1] = 0;
            }
            cur = trie[cur][t];
        }
    }
    
    int test(int num, int cur = 0, int cbit = 29, int z = 0) {
        if (cur == 0 && cbit != 29) return MOD;
        if (z || cbit == -1) return mn[cur];
        
        int b = (num>>cbit)&1;
        
        if (b) num ^= 1<<cbit;
        if (!(x&(1<<cbit))) {
            int ret = MOD;
            ret = min(ret,test(num,trie[cur][b],cbit-1,0));
            ret = min(ret,test(num^(1<<cbit),trie[cur][b^1],cbit-1,1));
            return ret;
        } else {
            return test(num^(1<<cbit),trie[cur][b^1],cbit-1,0);
        }
    }
};

tri<10000000> t;

pi ans;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> x;
    FOR(i,1,n+1) {
        cin >> cum[i];
        cum[i] ^= cum[i-1];
    }
    FOR(i,1,n+1) {
        t.ins(i-1);
        int x = t.test(cum[i]);
        ans = max(ans,{i-x,-(x+1)});
    }
    cout << -ans.s << " " << ans.f;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• Subtask 1: 100 / 100