Submission #58107

#	Time	Username	Problem	Language	Result	Execution time	Memory
58107		Benq	XOR (IZhO12_xor)	C++14	0 / 100	3 ms	488 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;

template<int MX> struct tri {
    static const int MXBIT = 30;
    int trie[MX][2], nex = 0; // easily changed to character
    
    void init() {
        nex = 0;
        trie[0][0] = trie[0][1] = 0;
    }
    
    void ins(int x, int a = 1) { // insert or delete
        int cur = 0;
        F0Rd(i,MXBIT) {
            int t = (x&(1LL<<i))>>i;
            if (!trie[cur][t]) {
                trie[cur][t] = ++nex;
                trie[nex][0] = trie[nex][1] = 0;
            }
            cur = trie[cur][t];
        }
    }
    
    int test(int x) {
        if (nex == 0) return -MOD;
        int cur = 0;
        F0Rd(i,MXBIT) {
            int t = ((x&(1LL<<i))>>i) ^ 1;
            if (!trie[cur][t]) t ^= 1;
            cur = trie[cur][t];
            if (t) x ^= (1LL<<i);
        }
        return x;
    }
};

tri<10000000> t;
int n,x,cum[MX];

int get(int z) {
    t.init();
    FOR(i,1,n+1) {
        if (i >= z) {
            t.ins(cum[i-z]);
            if (t.test(cum[i]) > x) return i;
        }
    }
    return MOD;
}

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];
    }
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo+hi+1)/2;
        if (get(mid) != MOD) lo = mid;
        else hi = mid-1;
    }
    int ans = get(lo);
    cout << ans-lo+1 << " " << lo;
}

/* 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: 0 / 100