답안 #855022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855022	2023-09-29T21:07:00 Z	smirichto	XOR (IZhO12_xor)	C++17	0 / 100	58 ms	67412 KB

xor

#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

#	결과	실행 시간	메모리	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	-