Submission #338395

#	Time	Username	Problem	Language	Result	Execution time	Memory
338395		Trickster	XOR (IZhO12_xor)	C++14	100 / 100	238 ms	179564 KiB

xor

//Suleyman Atayew

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
 
#define N 7500010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mod 1000000007
#define pii pair <int, int>
#define sz(a) (int)(a.size())
ll bigmod(ll a, ll b) { if(b==0)return 1; ll ret = bigmod(a, b/2); return ret * ret % mod * (b%2 ? a : 1) % mod; }

using namespace std;

int v[N];
int In[N];
int F[N][5];
int sz, n, k;

void upd(int x, int y)
{
    int nd = 0;
    for(int i = 30; i >= 0; i--) {
        int tp = 0;
        if(((1<<i) & x)) tp = 1;

        if(F[nd][tp] == -1) F[nd][tp] = ++sz;
        
        nd = F[nd][tp];
        In[nd] = min(y, In[nd]);
    }
}

int tap(int x, int y, int need, int nd)
{
    int tp = 1;
    if(((1<<y)&x)) tp = 0;

    if(need <= 0) return In[nd];
    if(y < 0) return 1e9;

    if((1<<y) < need) {
        if(F[nd][tp] == -1) return 1e9;
        return tap(x, y-1, need - (1<<y), F[nd][tp]);
    }

    if(F[nd][0] == -1 && F[nd][1] == -1) return 1e9;
    if(F[nd][0] == -1) {
        need -= (tp == 0 ? 0 : (1<<y));

        return tap(x, y-1, need, F[nd][1]);
    }
    if(F[nd][1] == -1) {
        need -= (tp == 1 ? 0 : (1<<y));

        return tap(x, y-1, need, F[nd][0]);
    }
    
    return min(tap(x, y-1, (need - (tp == 0 ? (1<<y) : 0)), F[nd][0]), tap(x, y-1, (need - (tp == 1 ? (1<<y) : 0)), F[nd][1]));
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);

    cin >> n >> k;

    for(int i = 0; i <= 7500000; i++) F[i][0] = F[i][1] = -1, In[i] = 1e9;

    for(int i = 1; i <= n; i++)
        cin >> v[i], v[i] ^= v[i-1];

    int l = 1e9, ans = 0;
    for(int i = 1; i <= n; i++) {
        int now = tap(v[i], 30, k, 0);

        upd(v[i], i);

        // cout << i << " " << now << " " << v[i] << "\n";

        if(ans < i - now) {
            ans = i - now;
            l = now+1;
        }
    }
    if(l == 1e9) l = 1, ans = 1;

    cout << l << " " << ans;
}

• Subtask 1: 100 / 100