oj.uz

답안 #338395

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
338395 2020-12-23T05:07:24 Z Trickster XOR (IZhO12_xor) C++14
100 / 100
 238 ms 179564 KB 
//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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 176492 KB Output is correct
2 Correct 85 ms 176492 KB Output is correct
3 Correct 89 ms 176620 KB Output is correct
4 Correct 92 ms 176492 KB Output is correct
5 Correct 94 ms 176492 KB Output is correct
6 Correct 97 ms 176620 KB Output is correct
7 Correct 94 ms 176620 KB Output is correct
8 Correct 102 ms 176724 KB Output is correct
9 Correct 140 ms 176876 KB Output is correct
10 Correct 131 ms 177644 KB Output is correct
11 Correct 131 ms 177868 KB Output is correct
12 Correct 135 ms 177644 KB Output is correct
13 Correct 140 ms 177644 KB Output is correct
14 Correct 130 ms 177644 KB Output is correct
15 Correct 132 ms 177772 KB Output is correct
16 Correct 134 ms 177772 KB Output is correct
17 Correct 227 ms 179436 KB Output is correct
18 Correct 226 ms 179564 KB Output is correct
19 Correct 238 ms 179436 KB Output is correct
20 Correct 224 ms 179436 KB Output is correct