Submission #2163368
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(node_index == -1) {
return {-(1 << 30), -(1 << 30)};
} else if(str_index == -1) {
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;
scanf("%d", &N);
Trie trie;
int ret = -1;
pair< int, int > lr(-1, -1);
for(int i = 0; i < N; i++) {
int x;
cin >> x;
trie.xorpush(x);
trie.add(0, i);
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});
}
}
cout << ret << " " << lr.first + 1 << " " << lr.second + 1 << endl;
}
Submission Info
Submission Time
2018-03-05 18:38:39+0900
Task
F - Maximum Segment XOR
User
ei13333
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2784 Byte
Status
WA
Exec Time
91 ms
Memory
6136 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:87:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
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
91 ms
6136 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
66 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