fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define db long double
  5. #define vi vector<int>
  6. #define vl vector<ll>
  7. #define vvi vector<vector<int>>
  8. #define vpi vector<pair<int,int>>
  9. #define pb push_back
  10. #define all(v) v.begin(),v.end()
  11. #define rall(v) v.rbegin(),v.rend()
  12. #define sz(v) (int)v.size()
  13. #define fix(n, num) fixed<<setprecision(num)<<n
  14. using namespace std;
  15. int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
  16. int dy[] = {-1, 1, 0, 0, 1, -1, 1, -1};
  17. const ll N = 5000 + 5, mod = 1e9 + 7, inf = 1e18;
  18.  
  19. struct node{
  20.     int ch[2]={};
  21.     int idx=1e7;
  22.  
  23.     int &operator[](int x){
  24.         return ch[x];
  25.     }
  26.  
  27. };
  28.  
  29. int k;
  30. struct Trie{
  31.     vector<node>trie;
  32.  
  33.     void clear(){
  34.         trie.clear();
  35.         trie.emplace_back();
  36.     }
  37.     Trie() {clear();}
  38.     int newNode(){
  39.         trie.emplace_back();
  40.         return sz(trie)-1;
  41.     }
  42.  
  43.     void insert(int x,int idx){
  44.         int u=0;
  45.         for(int i=30;i>=0;--i){
  46.             int b=x>>i&1;
  47.             if(trie[u][b]==0)
  48.                 trie[u][b]=newNode();
  49.             u=trie[u][b];
  50.             trie[u].idx=min(trie[u].idx,idx);
  51.         }
  52.     }
  53.  
  54.     int calc(int x){
  55.         int u=0;
  56.         int ret=1e7;
  57.         for(int i=30;i>=0;--i){
  58.             int bx=x>>i&1,bk=k>>i&1;
  59.             if(bx+bk==1){
  60.                 if(bx) ret=min(ret,trie[trie[u][0]].idx);
  61.                 u=trie[u][1];
  62.             }
  63.             else{
  64.                 if(!bk) ret=min(ret,trie[trie[u][1]].idx);
  65.                 u=trie[u][0];
  66.             }
  67.             if(!u) break;
  68.         }
  69.         return min(ret,trie[u].idx);
  70.     }
  71.  
  72. };
  73.  
  74. void TC() {
  75.     int n,p=0;
  76.     cin>>n>>k;
  77.     int ct=0,idx=-1;
  78.  
  79.     Trie t;
  80.     t.insert(0,0);
  81.     for (int i = 1; i <=n ; ++i) {
  82.         int x;
  83.         cin>>x;
  84.         p^=x;
  85.         int j=t.calc(p);
  86.         if(i-j>ct){
  87.             ct=i-j;
  88.             idx=j;
  89.         }
  90.         t.insert(p,i);
  91.     }
  92.  
  93.     cout<<idx+1<<' '<<ct;
  94.  
  95.  
  96. }
  97.  
  98. int32_t main() {
  99.     ios_base::sync_with_stdio(false);
  100.     cin.tie(0), cout.tie(0);
  101.  
  102.     int t = 1;
  103.    // cin >> t;
  104.     for (int i = 1; i <= t; ++i) {
  105.         TC();
  106.     }
  107.  
  108.     return 0;
  109. }
  110.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/hq1Nfs
language:
C++ (gcc 8.3)
created:
19 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!