cf-282e
C - Sausage Maximization
Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64uSubmit Status
Practice CodeForces 282E
Description
The Bitlandians are quite weird people. They have their own problems and their own solutions. They have their own thoughts and their own beliefs, they have their own values and their own merits. They have their own dishes and their own sausages! In Bitland a sausage is an array of integers! A sausage's deliciousness is equal to the bitwise excluding OR (the xor operation) of all integers in that sausage. One day, when Mr. Bitkoch (the local cook) was going to close his BitRestaurant, BitHaval and BitAryo, the most famous citizens of Bitland, entered the restaurant and each ordered a sausage. But Mr. Bitkoch had only one sausage left. So he decided to cut a prefix (several, may be zero, first array elements) of the sausage and give it to BitHaval and a postfix (several, may be zero, last array elements) of the sausage and give it to BitAryo. Note that one or both pieces of the sausage can be empty. Of course, the cut pieces mustn't intersect (no array element can occur in both pieces). The pleasure of BitHaval and BitAryo is equal to the bitwise XOR of their sausages' deliciousness. An empty sausage's deliciousness equals zero. Find a way to cut a piece of sausage for BitHaval and BitAryo that maximizes the pleasure of these worthy citizens.
Input
The first line contains an integer n (1 ≤ n ≤ 105). The next line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 1012) — Mr. Bitkoch's sausage. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64dspecifier.
Output
Print a single integer — the maximum pleasure BitHaval and BitAryo can get from the dinner.
Sample Input
Input
21 2
Output
삼
Input
31 2 3
Output
삼
Input
21000 1000
Output
천 1 #include <stdio.h>
2 #include <algorithm>
3 using namespace std;
4 typedef __int64 LL;
5 const int maxn = 100000+100;
6 int ch[maxn*40][2], cnt, root, n;
7 LL num[maxn], ans;
8 void Insert(LL tar)
9 {
10 int cur = root;
11 for(int i = 40; i >= 1; i--)
12 {
13 int id = ((tar & (1LL<<(i-1))) ? 1 : 0);
14 if(ch[cur][id] == -1)
15 {
16 ch[cnt][0] = ch[cnt][1] = -1;
17 ch[cur][id] = cnt++;
18 }
19 cur = ch[cur][id];
20 }
21 }
22 void Find(LL tar)
23 {
24 int cur = root;
25 LL ret = 0;
26 for(int i = 40; i >= 1; i--)
27 {
28 int id = ((tar & (1LL<<(i-1))) ? 1 : 0);
29 if(ch[cur][id^1] != -1)
30 {
31 ret |= (1LL << (i-1));
32 cur = ch[cur][id^1];
33 }
34 else
35 cur = ch[cur][id];
36 }
37 ans = max(ans, ret);
38 }
39 int main()
40 {
41 LL pre, suf;
42 while(scanf("%d", &n) != EOF)
43 {
44 pre = suf = cnt = 0;
45 ch[cnt][0] = ch[cnt][1] = -1;
46 root = cnt++;
47 Insert(0LL);
48 for(int i = 0; i < n; i++)
49 {
50 scanf("%I64d", &num[i]);
51 suf ^= num[i];
52 }
53 ans = suf;
54 for(int i = 0; i < n; i++)
55 {
56 pre ^= num[i];
57 suf ^= num[i];
58 Insert(pre);
59 Find(suf);
60 }
61 printf("%I64d
", ans);
62 }
63 return 0;
64 }
65 /*
66 #include <stdio.h>
67 #include <algorithm>
68 using namespace std;
69 typedef __int64 LL;
70 const int maxn = 100000+100;
71 int ch[maxn*40][2], cnt, root, n;
72 LL num[maxn], ans;
73 void Insert(LL tar)
74 {
75 int cur = root;
76 for(int i = 40; i >= 1; i--)
77 {
78 int id = ((tar & (1LL<<(i-1))) ? 1 : 0);
79 if(ch[cur][id] == -1)
80 {
81 ch[cnt][0] = ch[cnt][1] = -1;
82 ch[cur][id] = cnt++;
83 }
84 cur = ch[cur][id];
85 }
86 }
87 void Find(LL tar)
88 {
89 int cur = root;
90 LL ret = 0;
91 for(int i = 40; i >= 1; i--)
92 {
93 int id = ((tar & (1LL<<(i-1))) ? 1 : 0);
94 if(ch[cur][id^1] != -1)
95 {
96 ret |= (1LL << (i-1));
97 cur = ch[cur][id^1];
98 }
99 else
100 cur = ch[cur][id];
101 }
102 ans = max(ans, ret);
103 }
104 int main()
105 {
106 LL pre, suf;
107 while(scanf("%d", &n) != EOF)
108 {
109 pre = suf = cnt = 0;
110 ch[cnt][0] = ch[cnt][1] = -1;
111 root = cnt++;
112 Insert(0LL);
113 for(int i = 0; i < n; i++)
114 {
115 scanf("%I64d", &num[i]);
116 suf ^= num[i];
117 }
118 ans = suf;
119 for(int i = 0; i < n; i++)
120 {
121 pre ^= num[i];
122 suf ^= num[i];
123 Insert(pre);
124 Find(suf);
125 }
126 printf("%I64d
", ans);
127 }
128 return 0;
129 }
1 #include <stdio.h>
2
3 typedef __int64 LL;
4 const int maxn = 100000 + 100;
5 int memory[maxn*40][2], allocp, root, n;
6 LL num[maxn], ans;
7 void Insert(LL tar)
8 {
9 LL cur = root;
10 for(int i = 39; i >= 0; i--) {
11 int k = (((1LL<<i) & tar)?1:0);
12 if(memory[cur][k] == -1) {
13 memory[allocp][0] = memory[allocp][1] = -1;
14 memory[cur][k] = allocp++;
15 }
16 cur = memory[cur][k];
17 }
18 }
19 void Find(LL x)
20 {
21 LL ret = 0;
22 int cur = root;
23 for(int i = 39; i >= 0; i--) {
24 int k = (x & (1LL<<i))?1:0;
25 if(memory[cur][k^1] != -1) {
26 ret |= (1LL << i);
27 cur = memory[cur][k^1];
28 } else {
29 cur = memory[cur][k];
30 }
31 }
32 ans = (ans>ret)?ans:ret;
33 }
34 int main()
35 {
36 LL pre, suf;
37 while(~scanf("%d", &n)) {
38 pre = suf = allocp = 0;
39 memory[allocp][0] = memory[allocp][1] = -1;
40 root = allocp++;
41 Insert(0LL);
42 for(LL i = 0; i < n; i++) {
43 scanf("%I64d", &num[i]);
44 suf ^= num[i];
45 }
46 ans = suf;
47 for(int i = 0; i < n; i++)
48 {
49 pre ^= num[i];
50 suf ^= num[i];
51 Insert(pre);
52 Find(suf);
53 }
54 printf("%I64d
", ans);
55 }
56 return 0;
57 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
1 #include <stdio.h>
2 #include <algorithm>
3 using namespace std;
4 typedef __int64 LL;
5 const int maxn = 100000+100;
6 int ch[maxn*40][2], cnt, root, n;
7 LL num[maxn], ans;
8 void Insert(LL tar)
9 {
10 int cur = root;
11 for(int i = 40; i >= 1; i--)
12 {
13 int id = ((tar & (1LL<<(i-1))) ? 1 : 0);
14 if(ch[cur][id] == -1)
15 {
16 ch[cnt][0] = ch[cnt][1] = -1;
17 ch[cur][id] = cnt++;
18 }
19 cur = ch[cur][id];
20 }
21 }
22 void Find(LL tar)
23 {
24 int cur = root;
25 LL ret = 0;
26 for(int i = 40; i >= 1; i--)
27 {
28 int id = ((tar & (1LL<<(i-1))) ? 1 : 0);
29 if(ch[cur][id^1] != -1)
30 {
31 ret |= (1LL << (i-1));
32 cur = ch[cur][id^1];
33 }
34 else
35 cur = ch[cur][id];
36 }
37 ans = max(ans, ret);
38 }
39 int main()
40 {
41 LL pre, suf;
42 while(scanf("%d", &n) != EOF)
43 {
44 pre = suf = cnt = 0;
45 ch[cnt][0] = ch[cnt][1] = -1;
46 root = cnt++;
47 Insert(0LL);
48 for(int i = 0; i < n; i++)
49 {
50 scanf("%I64d", &num[i]);
51 suf ^= num[i];
52 }
53 ans = suf;
54 for(int i = 0; i < n; i++)
55 {
56 pre ^= num[i];
57 suf ^= num[i];
58 Insert(pre);
59 Find(suf);
60 }
61 printf("%I64d
", ans);
62 }
63 return 0;
64 }
65 /*
66 #include <stdio.h>
67 #include <algorithm>
68 using namespace std;
69 typedef __int64 LL;
70 const int maxn = 100000+100;
71 int ch[maxn*40][2], cnt, root, n;
72 LL num[maxn], ans;
73 void Insert(LL tar)
74 {
75 int cur = root;
76 for(int i = 40; i >= 1; i--)
77 {
78 int id = ((tar & (1LL<<(i-1))) ? 1 : 0);
79 if(ch[cur][id] == -1)
80 {
81 ch[cnt][0] = ch[cnt][1] = -1;
82 ch[cur][id] = cnt++;
83 }
84 cur = ch[cur][id];
85 }
86 }
87 void Find(LL tar)
88 {
89 int cur = root;
90 LL ret = 0;
91 for(int i = 40; i >= 1; i--)
92 {
93 int id = ((tar & (1LL<<(i-1))) ? 1 : 0);
94 if(ch[cur][id^1] != -1)
95 {
96 ret |= (1LL << (i-1));
97 cur = ch[cur][id^1];
98 }
99 else
100 cur = ch[cur][id];
101 }
102 ans = max(ans, ret);
103 }
104 int main()
105 {
106 LL pre, suf;
107 while(scanf("%d", &n) != EOF)
108 {
109 pre = suf = cnt = 0;
110 ch[cnt][0] = ch[cnt][1] = -1;
111 root = cnt++;
112 Insert(0LL);
113 for(int i = 0; i < n; i++)
114 {
115 scanf("%I64d", &num[i]);
116 suf ^= num[i];
117 }
118 ans = suf;
119 for(int i = 0; i < n; i++)
120 {
121 pre ^= num[i];
122 suf ^= num[i];
123 Insert(pre);
124 Find(suf);
125 }
126 printf("%I64d
", ans);
127 }
128 return 0;
129 }
1 #include <stdio.h>
2
3 typedef __int64 LL;
4 const int maxn = 100000 + 100;
5 int memory[maxn*40][2], allocp, root, n;
6 LL num[maxn], ans;
7 void Insert(LL tar)
8 {
9 LL cur = root;
10 for(int i = 39; i >= 0; i--) {
11 int k = (((1LL<<i) & tar)?1:0);
12 if(memory[cur][k] == -1) {
13 memory[allocp][0] = memory[allocp][1] = -1;
14 memory[cur][k] = allocp++;
15 }
16 cur = memory[cur][k];
17 }
18 }
19 void Find(LL x)
20 {
21 LL ret = 0;
22 int cur = root;
23 for(int i = 39; i >= 0; i--) {
24 int k = (x & (1LL<<i))?1:0;
25 if(memory[cur][k^1] != -1) {
26 ret |= (1LL << i);
27 cur = memory[cur][k^1];
28 } else {
29 cur = memory[cur][k];
30 }
31 }
32 ans = (ans>ret)?ans:ret;
33 }
34 int main()
35 {
36 LL pre, suf;
37 while(~scanf("%d", &n)) {
38 pre = suf = allocp = 0;
39 memory[allocp][0] = memory[allocp][1] = -1;
40 root = allocp++;
41 Insert(0LL);
42 for(LL i = 0; i < n; i++) {
43 scanf("%I64d", &num[i]);
44 suf ^= num[i];
45 }
46 ans = suf;
47 for(int i = 0; i < n; i++)
48 {
49 pre ^= num[i];
50 suf ^= num[i];
51 Insert(pre);
52 Find(suf);
53 }
54 printf("%I64d
", ans);
55 }
56 return 0;
57 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.