Submission #831109

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
831109	2023-08-19T18:37:46 Z	yeediot	XOR (IZhO12_xor)	C++17	0 / 100	26 ms	70740 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);
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    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;
      |                      ~~^~
xor.cpp: In function 'int main()':
xor.cpp:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     freopen("c.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~
xor.cpp:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     freopen("c.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	26 ms	70740 KB	Output isn't correct
2	Halted	0 ms	0 KB	-