Submission #1107979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107979		vjudge1	XOR (IZhO12_xor)	C++17	100 / 100	154 ms	58444 KiB

xor

#include <bits/stdc++.h>
#define ll long long
#define deb(x) cout << #x << " : " << x << endl;
#define take_input(a)                                                          \
  for (auto &x : a)                                                            \
    cin >> x;
#define _output(a)                                                             \
  for (auto &x : a)                                                            \
    cout << x << " ";                                                          \
  cout << endl;
#define srt(a) sort(a.begin(), a.end())
#define nl "\n"
using namespace std;

struct Node {
  Node *childrens[2];
  int indx;

  Node(int i) : indx(i) {};
  bool containsKey(int i) { return childrens[i] != NULL; }
  Node *get(int i) { return childrens[i]; };
  void put(int i, Node *node) { childrens[i] = node; };
};

class Trie {
private:
  Node *root;

public:
  Trie() { root = new Node(0); }

  void insert(int num, int indx) {
    Node *node = root;

    for (int i = 30; i >= 0; i--) {
      bool bit = (num >> i) & 1 ? true : false;
      if (!node->containsKey(bit)) {
        node->put(bit, new Node(indx));
      }
      node = node->get(bit);
    }
  }

  pair<int, int> query(int num, int k, int idx) {
    int start = -1;
    int len = 0;

    Node *node = root;
    for (int i = 30; i >= 0; i--) {
      bool bit = (num >> i) & 1 ? true : false;
      bool Kbit = (k >> i) & 1 ? true : false;

      if (node->containsKey(1 - bit)) {
        if (!Kbit) {
          int sz = idx - node->childrens[1 - bit]->indx;
          // cout << node->childrens[1 - bit]->indx + 1 << " " << sz << endl;
          if (len < sz) {
            start = node->childrens[1 - bit]->indx + 1;
            len = sz;
            // cout << "updated " << len << nl;
          }

          if (node->containsKey(bit))
            node = node->get(bit);
          else
            return {start, len};
        }

        else
          node = node->get(1 - bit);
      }

      else {
        if (Kbit) {
          return {start, len};
        } else
          node = node->get(bit);
      }
    }

    if (idx - node->indx > len) {
      start = node->indx + 1;
      len = idx - node->indx;
      // cout << "updated " << len << nl;
    }
    return {start, len};
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  // cin >> T;

  while (T--) {
    int n, k;
    cin >> n >> k;

    int xr = 0;
    pair<int, int> ans{-1, -1};
    Trie t;
    t.insert(0, 0);

    for (int i = 1; i <= n; i++) {
      int temp;
      cin >> temp;
      xr = xr ^ temp;
      // deb(xr);
      pair<int, int> p = t.query(xr, k, i);
      // cout << "rec " << p.second << nl;
      if (p.second > ans.second)
        ans = p;
      t.insert(xr, i);
    }

    cout << ans.first << " " << ans.second << endl;
  }

  return 0;
}

• Subtask 1: 100 / 100