oj.uz

Submission #855026

# Submission time Handle Problem Language Result Execution time Memory
855026 2023-09-29T21:14:00 Z smirichto XOR (IZhO12_xor) C++17
100 / 100
 101 ms 158352 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pi pair<ll,ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define alll(x) ((x).begin()+1), (x).end()
#define clean(v) (v).resize(distance((v).begin(), unique(all(v))));
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
#define mod mod
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;

void io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

template<class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

template<class T>
bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }

void nop() {
    cout << -1 << endl;
    return;
}

const int N = (3e5+5)*33 + 5 ;
int n , x ;
int a[N] ;
int to[N][2] , mn[N][2] ;

int ndcnt = 0 ;
int nxt(){
    return ++ndcnt ;
}
void insert(int x , int pos)
{
    int t = 0 ;
    for(int bit = 30 ; bit>=0 ; bit--){
        int c = (x>>bit) & 1 ;
        if(to[t][c] == -1) to[t][c] = nxt() ;
        ckmin(mn[t][c] , pos) ;
        t = to[t][c] ;
    }

}

int query(int val , int x)
{
    int ret = 1e9 ;
    int t = 0 ;
    for(int bit = 30 ; bit>=0 ; bit--){
        if(t==-1) break ;
        int c = (val>>bit) & 1 , cx = (x>>bit) & 1 ;
        if(cx){
            t = to[t][c^1] ;
        }
        else{
            ckmin(ret , mn[t][c^1]) ;
            t = to[t][c] ;
        }
    }
    return ret ;
}

void solve() {
    cin>>n>>x ;
    for(int i = 0 ; i<N ; i++){
        for(int j = 0 ; j<2 ; j++){
            to[i][j] = -1 ;
            mn[i][j] = 1e9 ;
        }
    }
    int ans = 0 , idx = 0 ;
    insert(0 , 0) ;
    for(int i = 1 ; i<=n ; i++){
        cin>>a[i] , a[i] ^= a[i-1] ;
        int res = query(a[i] , x-1) ;
        if(ckmax(ans , i - res)) idx = res+1 ;
        insert(a[i] ,  i) ;
    }
    cout<<idx<<' '<<ans<<endl;


}

int main() {
//#ifndef ONLINE_JUDGE
//    freopen("input.in", "r", stdin);
//    freopen("output.out", "w", stdout);
//#endif
    io();
    ll tt = 1;
    //cin>>tt ;
    while (tt--) {
        solve();
    }

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 156532 KB Output is correct
2 Correct 29 ms 156564 KB Output is correct
3 Correct 30 ms 156508 KB Output is correct
4 Correct 27 ms 156520 KB Output is correct
5 Correct 31 ms 156492 KB Output is correct
6 Correct 32 ms 156496 KB Output is correct
7 Correct 32 ms 156508 KB Output is correct
8 Correct 32 ms 156508 KB Output is correct
9 Correct 47 ms 156500 KB Output is correct
10 Correct 46 ms 156508 KB Output is correct
11 Correct 48 ms 156492 KB Output is correct
12 Correct 47 ms 156496 KB Output is correct
13 Correct 47 ms 156504 KB Output is correct
14 Correct 46 ms 156524 KB Output is correct
15 Correct 54 ms 156496 KB Output is correct
16 Correct 56 ms 156500 KB Output is correct
17 Correct 101 ms 157344 KB Output is correct
18 Correct 86 ms 158352 KB Output is correct
19 Correct 86 ms 158352 KB Output is correct
20 Correct 90 ms 158352 KB Output is correct