oj.uz

Submission #855022

# Submission time Handle Problem Language Result Execution time Memory
855022 2023-09-29T21:07:00 Z smirichto XOR (IZhO12_xor) C++17
0 / 100
 58 ms 67412 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 ll N = 1e6+5 ;
ll a[N] ;
ll to[N][2] , mn[N][2] ;

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

}

ll query(ll val , ll x)
{
    ll ret = 1e12 ;
    ll t = 0 ;
    for(ll bit = 30 ; bit>=0 ; bit--){
        if(t==-1) break ;
        ll 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() {
    ll n , x ;
    cin>>n>>x ;
    for(ll i = 0 ; i<N ; i++){
        for(ll j = 0 ; j<2 ; j++){
            to[i][j] = -1 ;
            mn[i][j] = 1e12 ;
        }
    }
    ll ans = 0 , idx = 0 ;
    insert(0 , 0) ;
    for(ll i = 1 ; i<=n ; i++){
        cin>>a[i] , a[i] ^= a[i-1] ;
        ll 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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33372 KB Output is correct
2 Correct 5 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 5 ms 33372 KB Output is correct
5 Correct 8 ms 33476 KB Output is correct
6 Correct 9 ms 33372 KB Output is correct
7 Correct 10 ms 33372 KB Output is correct
8 Correct 11 ms 33460 KB Output is correct
9 Correct 26 ms 33476 KB Output is correct
10 Correct 27 ms 33372 KB Output is correct
11 Correct 26 ms 33476 KB Output is correct
12 Correct 27 ms 33472 KB Output is correct
13 Correct 26 ms 33372 KB Output is correct
14 Correct 27 ms 33372 KB Output is correct
15 Correct 31 ms 33372 KB Output is correct
16 Correct 28 ms 33368 KB Output is correct
17 Runtime error 58 ms 67412 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -