Submission #338371

#	Time	Username	Problem	Language	Result	Execution time	Memory
338371		Trickster	XOR (IZhO12_xor)	C++14	0 / 100	1 ms	364 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 250010
#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, nd, n, k;

void upd(int x, int y)
{
    int nd = 0;
    for(int i = 0; i <= 20; 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((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 = 1; i <= n; i++) F[i][0] = F[i][1] = -1, In[nd] = 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], 0, k, 0);

        upd(v[i], i);

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

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

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

• Subtask 1: 0 / 100