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 |
|
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 |