Submission #2163419


Source Code Expand

#include<bits/stdc++.h>

using namespace std;

struct TrieNode {
  int nxt[2];
  int lazy;
  int exist; // ??????????????????
  vector< int > accept; // ?????id

  TrieNode() : exist(0), lazy(0) {
    memset(nxt, -1, sizeof(nxt));
  }
};

struct Trie {
  vector< TrieNode > nodes;
  int root;

  Trie() : root(0) {
    nodes.push_back(TrieNode());
  }

  virtual void direct_action(int node, int id) {}

  virtual void child_action(int node, int child, int id) {}

  void update_direct(int node, int id) {
    ++nodes[node].exist;
    nodes[node].accept.push_back(id);
    direct_action(node, id);
  }

  void update_child(int node, int child, int id) {
    ++nodes[node].exist;
    child_action(node, child, id);
  }

  void push(int str_index, int node_index) {
    const int c = (nodes[node_index].lazy >> str_index) & 1;
    if(c) swap(nodes[node_index].nxt[0], nodes[node_index].nxt[1]);
    if(~nodes[node_index].nxt[0]) nodes[nodes[node_index].nxt[0]].lazy ^= nodes[node_index].lazy;
    if(~nodes[node_index].nxt[1]) nodes[nodes[node_index].nxt[1]].lazy ^= nodes[node_index].lazy;
    nodes[node_index].lazy = 0;
  }

  void add(const int str, int str_index, int node_index, int id) {
    if(str_index == -1) {
      update_direct(node_index, id);
    } else {
      const int c = (str >> str_index) & 1;
      if(nodes[node_index].nxt[c] == -1) {
        nodes[node_index].nxt[c] = (int) nodes.size();
        nodes.push_back(TrieNode());
      }
      add(str, str_index - 1, nodes[node_index].nxt[c], id);
      update_child(node_index, nodes[node_index].nxt[c], id);
    }
  }

  void add(const int str, int id) {
    add(str, 25, 0, id);
  }

  void xorpush(const int str) {
    nodes[0].lazy ^= str;
  }

  pair< int, int > query(int str_index, int node_index, int bit) {
    if(str_index == -1) {
      if(nodes[node_index].accept.empty()) throw (0);
      return {bit, nodes[node_index].accept[0]};
    } else {
      push(str_index, node_index);
      if(~nodes[node_index].nxt[1]) {
        return (query(str_index - 1, nodes[node_index].nxt[1], bit | (1 << str_index)));
      } else {
        return (query(str_index - 1, nodes[node_index].nxt[0], bit));
      }
    }
  }
};

int main() {
  int N;
  cin >> N;
  Trie trie;
  trie.add(0, 0);
  int ret = -1;
  pair< int, int > lr(-1, -1);
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    trie.xorpush(x);
    auto get = trie.query(25, 0, 0);
    if(get.first > ret) {
      ret = get.first;
      lr = {get.second, i};
    } else if(get.first == ret) {
      lr = min(lr, {get.second, i});
    }
    trie.add(0, i + 1);
  }
  cout << ret << " " << lr.first + 1 << " " << lr.second + 1 << endl;
}

Submission Info

Submission Time
Task F - Maximum Segment XOR
User ei13333
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2780 Byte
Status WA
Exec Time 88 ms
Memory 7416 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 7
WA × 24
Set Name Test Cases
All 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 4, 5, 6, 7, 8, 9
Case Name Status Exec Time Memory
1 AC 1 ms 256 KB
10 WA 2 ms 384 KB
11 WA 2 ms 384 KB
12 WA 2 ms 384 KB
13 WA 6 ms 748 KB
14 WA 8 ms 968 KB
15 WA 9 ms 964 KB
16 AC 44 ms 1804 KB
17 WA 27 ms 1668 KB
18 WA 88 ms 7416 KB
19 WA 1 ms 256 KB
2 AC 1 ms 256 KB
20 WA 1 ms 256 KB
21 AC 1 ms 256 KB
22 WA 1 ms 256 KB
23 WA 1 ms 256 KB
24 WA 1 ms 256 KB
25 WA 4 ms 384 KB
26 WA 2 ms 384 KB
27 WA 7 ms 512 KB
28 WA 53 ms 1280 KB
29 WA 63 ms 3068 KB
3 AC 1 ms 256 KB
30 WA 37 ms 1024 KB
31 WA 77 ms 1284 KB
4 AC 1 ms 256 KB
5 AC 1 ms 256 KB
6 WA 1 ms 256 KB
7 WA 1 ms 256 KB
8 WA 1 ms 256 KB
9 WA 2 ms 384 KB