Submission #261599

#	Time	Username	Problem	Language	Result	Execution time	Memory
261599		sckmd	XOR (IZhO12_xor)	C++14	100 / 100	260 ms	59512 KiB

xor

    #include <bits/stdc++.h>
     
    using namespace std;
    #define MAXN 500005
    int a[MAXN];
     
    struct node
    {
      node* nula;
      node* kec;
      int minpos=9999999;
      //bool leaf;
    };
    node* root;
     
    void update(int br,int pos)
    {
      node* now = root;
      for(int i = 31; i >= 0; i--)
      {
        //if(now->minpos == NULL)now->minpos = 999999999;
        now->minpos = min(now->minpos,pos);
        if(br&(1<<i))
        {
          if(now->kec == NULL)now->kec = new node();
          now = now->kec;
        }
        else
        {
          if(now->nula == NULL)now->nula = new node();
          now = now->nula;
        }
      }
      //if(now->minpos == NULL)now->minpos = 999999999;
      now->minpos = min(now->minpos,pos);
    }
    int query(int br,int x)
    {
      //br je trazeni
      //x je mojbroj
      node* now = root;
      int res = 9999999;
      int i;
      for(i = 31; i >= 0; i--)
      {
        if(br & (1<<i))
        {
          if(x & (1<<i))
          {
            if(now->nula == NULL)break;
            now = now->nula;
          }
          else
          {
            if(now->kec == NULL)break;
            now = now->kec;
          }
        }
        else
        {
          if(x & (1<<i))
          {
            if(now->nula != NULL)res = min(res,now->nula->minpos);
            if(now->kec == NULL)break;
            now = now->kec;
          }
          else
          {
            if(now->kec != NULL)res = min(res,now->kec->minpos);
            if(now->nula == NULL)break;
            now = now->nula;
          }
        }
      }
      if(i==-1)res = min(res,now->minpos);
      return res;
    }
     
    int main()
    {
      ios_base::sync_with_stdio(false);
      int n,x;
      cin >> n >> x;
      root = new node();
      update(0,1);
      for(int i = 1; i <= n; i++)
      {
        cin >> a[i];
        a[i]^=a[i-1];
      }
      int ans = 0;
      int j = 0;
      for(int i = 1; i <= n; i++)
      {
      	int tr = i-query(x,a[i]);
      	if(tr > ans)ans=tr,j=i;
        update(a[i],i);
      }
      cout << j-ans+1 << " " << ans;
      return 0;
    }

• Subtask 1: 100 / 100