답안 #831106

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831106	2023-08-19T18:34:51 Z	yeediot	XOR (IZhO12_xor)	C++14	0 / 100	25 ms	70704 KB

xor

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
const int mxn=3e5*30;
int n,k;
vector<int>a;
int trie[mxn][2];
int mn[mxn];
int nxt=0;
void input(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        a.pb(x);
    }
}
void init(){
    for(int i=0;i<mxn;i++){
        mn[i]=8e18;
    }
}
vector<int>conv(int x){
    vector<int>res;
    for(int i=0;i<30;i++){
        res.pb(x>>i&1);
    }
    reverse(all(res));
    return res;
}
void insert(vector<int>vec,int p){
    int v=0;
    chmin(mn[v],p);
    for(int i=0;i<30;i++){
        if(!trie[v][vec[i]])trie[v][vec[i]]=++nxt;
        v=trie[v][vec[i]];
        chmin(mn[v],p);
    }
}
int q(vector<int>vec,int p){
    int v=0;
    int res=-8e18;
    for(int i=0;i<30 and (!i or v);i++){
        int need=(k>>29-i)&1;
        int bit=vec[i];
        if(need==1)v=trie[v][1-bit];
        else{
            if(trie[v][bit])chmax(res,p-mn[v]+1);
            v=trie[v][vec[i]];
        }
    }
    if(v)chmin(res,p-mn[v]+1);
    return res;
}
void solve(){
    input();
    init();
    int prefix=0;
    int ans=-8e18;
    int p=0;
    for(int i=0;i<n;i++){
        prefix^=a[i];
        int x=q(conv(prefix),i);
        if(x>ans){
            p=i;
            ans=x;
        }
        insert(conv(prefix),i);
    }
    cout<<p<<' '<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
}
 /*
 input:
 
 */

Compilation message

xor.cpp: In function 'long long int q(std::vector<long long int>, long long int)':
xor.cpp:55:24: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   55 |         int need=(k>>29-i)&1;
      |                      ~~^~

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	25 ms	70704 KB	Output isn't correct
2	Halted	0 ms	0 KB	-