Submission #1168581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168581		escobrand	XOR (IZhO12_xor)	C++20	100 / 100	81 ms	71752 KiB

xor

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define eb emplace_back
#define ll long long 
#define fi first
#define se second
int t,n,i,k;
const int maxn = 6e6 + 10,maxv = 30;
int a[maxn];
int mx,ans;

struct trie
{
  int co = 0;
  struct nodes
  {
    int child[2] = {};
    int c;
  }node[maxn];
  
  void add(int tmp,int id)
  {
    int pos = 0;
    for(int i = maxv - 1;i>=0;i--)
    {
      bool ch = (tmp >> i) & 1;
      if(!node[pos].child[ch])
      {
        node[pos].child[ch] = ++co;
        node[co].c = id;
      }
      pos = node[pos].child[ch];
    }
  }
  
  void cal(int tmp,int pmt,int id)
  {
    int pos = 0;
    bool cc = 1;
    for(int i = maxv - 1;i>=0;i--)
    {
      bool ch = (tmp >> i) & 1,chh = (pmt >> i)&1;
      if(ch == chh && node[pos].child[!chh])
      {
        if(mx < id - node[node[pos].child[!chh]].c)
        {
          mx = id - node[node[pos].child[!chh]].c;
          ans = node[node[pos].child[!chh]].c+1;
        }
        // cout<<node[node[pos].child[!chh]].c<<' ';
      }
      
      if(!node[pos].child[ch])
      {
        cc = 0;
        break;
      }
      
      pos = node[pos].child[ch];
    }
    if(cc && mx < id - node[pos].c)
    {
      mx = id - node[pos].c;
      ans = node[pos].c+1;
    }
  }
}tri;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>k;
    tri.add(0,0);
    for(i = 1;i<=n;i++)
    {
      cin>>a[i];
      a[i] ^= a[i-1];
      
      tri.add(a[i],i);
      tri.cal((a[i] ^ k),a[i],i);
    }
    
    cout<<ans<<' '<<mx;
    
    return 0;
}

• Subtask 1: 100 / 100