QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#453751#8823. Game: Battle of Menjis5abAC ✓59ms4056kbC++201.2kb2024-06-24 10:30:332024-06-24 10:30:34

Judging History

你现在查看的是测评时间为 2024-06-24 10:30:34 的历史记录

  • [2024-06-27 11:29:29]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:43ms
  • 内存:4036kb
  • [2024-06-27 11:29:18]
  • hack成功,自动添加数据
  • (/hack/704)
  • [2024-06-24 10:30:34]
  • 评测
  • 测评结果:100
  • 用时:59ms
  • 内存:4056kb
  • [2024-06-24 10:30:33]
  • 提交

answer

/* name: K
 * author: 5ab
 * created at: 2024-06-24
 */
#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };

using ll = long long;
const int N = 1e5, lgA = 30;

int a[N], c[lgA];

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int cas, n, k;
	
	auto lb = [&](int x) { return __lg(x & -x); };
	auto gm = [&](int x) { return (1 << (x + 1)) - 1; };
	auto ad = [&](int x, int v)
	{
		if (x != 0)
			c[lb(x)] += v;
	};
	
	cin >> cas;
	while (cas--)
	{
		cin >> n >> k;
		fill(c, c + lgA, 0);
		
		int sm = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> a[i];
			ad(a[i], 1);
			sm ^= a[i];
		}
		int ans = 0;
		for (int i = 0; i < n; i++)
		{
			int cv = sm, lbc = lb(a[i] + 1);
			ad(a[i], -1), ad(a[i] + 1, 1);
			for (int j = 0; j < lgA; j++) if (c[j])
			{
				chmin(cv, sm ^ gm(j) ^ gm(lbc));
				// cerr << j << " " << lbc << " " << cv << endl;
			}
			chmax(ans, cv);
			ad(a[i], 1), ad(a[i] + 1, -1);
		}
		cout << ans << endl;
	}
	
	return 0;
}
// started coding at: 06-24 10:09:52

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

4
2 3
1 1
4 4
0 0 0 0
4 1
1 2 4 8
13 5
1 1 4 5 1 4 1 9 1 9 8 1 0

output:

0
0
9
11

result:

ok 4 number(s): "0 0 9 11"

Test #2:

score: 0
Accepted
time: 59ms
memory: 3640kb

input:

100000
1 5
0
4 5
4 4 3 5
5 2
0 1 7 5 4
4 1
6 4 4 4
1 5
3
2 2
1 1
3 1
5 4 0
2 4
0 3
2 2
1 7
3 1
2 1 6
2 4
5 1
3 1
3 7 0
4 4
7 5 4 4
3 3
1 1 5
1 3
3
3 2
3 7 4
4 1
3 1 0 5
5 3
6 2 3 6 3
3 1
2 6 6
4 4
5 4 1 3
2 1
4 4
4 5
0 1 6 5
4 5
0 7 7 5
2 4
4 0
5 1
7 0 2 6 0
3 4
5 2 3
2 3
4 3
3 2
1 0 1
2 2
6 5
5 1
6...

output:

0
2
7
2
3
0
1
3
6
5
4
4
2
5
3
0
7
2
0
3
0
2
5
4
3
4
7
0
3
2
4
4
4
2
4
6
1
3
2
7
4
7
4
6
2
4
4
3
7
0
2
2
1
0
6
7
0
0
1
7
1
3
3
6
2
1
5
5
5
1
6
4
1
2
0
7
1
4
3
6
7
7
0
1
7
0
0
4
0
4
7
7
7
4
6
2
5
4
7
4
1
6
4
4
3
4
7
5
4
4
3
6
1
2
5
4
2
1
1
0
0
0
0
6
1
3
4
0
1
4
6
3
1
3
5
1
0
6
3
2
1
4
5
2
1
2
2
7
6
7
...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 22ms
memory: 3652kb

input:

10000
45 41
124 126 8 59 3 89 75 2 88 65 17 107 90 92 113 103 122 7 87 89 61 78 4 27 61 117 9 122 40 114 80 54 63 111 19 4 89 77 99 12 93 28 34 106 75
47 50
49 52 96 35 99 61 126 80 122 33 96 67 99 44 29 4 126 64 0 111 31 84 8 52 16 112 103 85 13 50 4 42 70 76 121 96 96 3 21 118 116 50 90 63 15 69 0...

output:

55
7
110
84
12
57
76
48
4
76
8
97
37
18
72
6
37
70
20
17
55
31
118
118
3
78
67
62
18
97
14
24
86
49
81
33
84
95
78
47
80
51
64
55
86
105
96
64
67
29
14
42
94
49
34
78
27
5
8
59
68
43
23
108
78
67
99
84
109
5
75
29
48
42
102
37
87
68
81
87
101
111
10
34
106
90
52
8
67
37
36
9
71
76
79
108
25
49
107
9...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 35ms
memory: 3740kb

input:

100
4991 710173979
194350399 308253661 453535140 859535540 237118582 491883070 203713206 876045568 179614490 762427255 600586096 195805957 619372254 837564280 46030125 818656915 624958658 579965169 315157532 507369398 223649057 730321515 87001797 103914474 146001643 169828188 694735418 411534273 158...

output:

895973929
644710414
718127976
764287680
427180528
89428087
633652199
202995551
1019972853
492532509
856424472
740558823
71451464
522956950
559048723
352180449
357679270
737527068
105530653
703884103
744126411
991785031
92210383
423071396
825321389
911136722
406765701
757424811
1045423355
312227835
6...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 39ms
memory: 4056kb

input:

5
99923 692526850
715084131 984147203 17386228 785452545 982653579 705503250 519275489 706775608 799238095 351240081 520684482 896504393 520155812 883104115 42870024 735387097 365091799 214533775 762045747 566889361 577707360 474682304 386471939 908932293 291557432 740983423 444227029 754037318 5809...

output:

566935826
841956871
997917453
927747273
280103635

result:

ok 5 number(s): "566935826 841956871 997917453 927747273 280103635"

Test #6:

score: 0
Accepted
time: 47ms
memory: 3588kb

input:

100000
1 5
3
2 1
0 3
4 1
0 4 7 6
3 1
4 0 5
5 3
0 0 7 7 7
5 4
3 6 7 7 0
1 1
2
3 5
5 0 0
4 4
4 0 4 0
5 2
7 7 7 0 7
2 1
2 4
2 3
7 2
4 2
6 0 3 7
2 5
7 5
5 2
7 7 2 0 0
1 1
7
2 2
3 0
2 1
7 0
4 1
0 3 4 7
4 5
7 7 3 3
4 1
0 0 7 0
1 1
0
5 3
7 0 3 3 6
3 4
2 4 0
1 1
0
2 5
2 6
1 1
0
4 5
3 0 4 5
1 2
4
3 3
7 2 3
1...

output:

3
3
5
1
7
5
2
5
0
0
4
5
2
2
2
7
3
7
0
0
7
0
1
4
0
4
0
2
4
6
0
0
2
7
1
0
3
1
1
6
3
3
4
0
4
0
4
0
0
0
0
1
3
3
1
3
0
7
4
3
0
3
4
0
7
0
7
5
3
3
3
3
7
4
0
3
7
2
4
1
0
3
2
4
5
7
3
7
3
7
1
6
3
1
3
7
6
2
3
4
1
6
0
2
1
0
4
1
4
0
6
3
1
0
5
0
7
7
7
7
0
0
6
0
3
0
5
4
3
0
3
0
7
4
3
4
0
6
7
2
0
5
7
2
7
6
7
7
3
1
...

result:

ok 100000 numbers

Test #7:

score: 0
Accepted
time: 19ms
memory: 3712kb

input:

10000
45 41
120 28 111 121 96 64 11 24 31 55 0 24 0 127 16 15 79 127 0 0 127 64 31 10 95 0 0 96 71 40 0 123 31 11 32 32 0 11 76 127 0 96 47 100 0
49 49
6 64 96 64 32 63 127 112 32 64 127 63 13 124 71 8 0 47 0 64 119 127 55 15 31 12 23 15 112 112 71 0 63 0 127 127 0 0 122 111 96 19 80 26 0 96 64 63 0...

output:

39
119
1
101
109
22
67
95
117
16
93
74
14
38
47
12
46
85
94
24
121
11
57
30
101
20
1
28
58
88
82
86
119
118
5
42
0
46
12
107
100
116
32
94
89
15
59
61
19
104
87
35
98
88
109
81
86
72
91
7
23
31
20
102
122
59
107
95
44
98
56
120
73
77
46
71
77
22
34
74
98
4
94
50
66
109
14
94
48
109
19
83
82
50
111
2...

result:

ok 10000 numbers

Test #8:

score: 0
Accepted
time: 38ms
memory: 3664kb

input:

100
4981 345654103
271056895 536870911 473956351 229113855 534118400 496205823 362817983 238026751 67108864 476615359 252973055 426702360 95525311 7733247 119537663 16777216 269481984 536870911 328204288 67108863 165849087 22020095 536870911 257982463 268435456 379563839 158931327 401113088 10616831...

output:

375646588
196120712
530324071
389523587
258272848
96526039
389694507
21615298
231064942
120412838
40426797
91846174
346651816
274396025
532233855
125617615
15515680
463100220
6712977
393632829
216352692
18895979
452122769
513009110
172803659
433540024
146587264
499919020
399197579
422726691
22109121...

result:

ok 100 numbers

Test #9:

score: 0
Accepted
time: 42ms
memory: 3972kb

input:

5
99965 925086677
462946303 195362816 440926207 490536960 459014143 489057920 417644544 67108863 268435455 214024191 271622627 159776767 268435455 262144000 514392063 287886847 257949696 247544320 377024384 130878659 390598655 355024896 405302515 302252032 391592447 124878335 394919936 385875967 692...

output:

282456931
529494087
271489722
300788235
290503299

result:

ok 5 number(s): "282456931 529494087 271489722 300788235 290503299"

Test #10:

score: 0
Accepted
time: 37ms
memory: 3624kb

input:

100
5000 1000000000
24226 18044 966 17980 3578 874 15232 5874 66263 27100 66251 16342 32006 12184 65662 24982 22510 30690 2196 14986 66121 9236 20802 13646 26192 65764 18194 29370 4922 29284 25344 9766 16026 11740 3008 16472 16276 20674 22078 4720 65738 30310 10030 26570 66468 18682 3142 66125 2014 ...

output:

6065
455436
5353175
1780645
493241
904
65737047
932834
20756929
141438
135369
4813
9189
2016035
1803189
104752
54059
190233
7226353
205342
877968
6836583
9116
25705
15270003
459643
12249
11866574
27640676
160246
45502
70702851
1066977
315843
127161
25020
2082725
18271
4203107
20132554
123
43126
5409...

result:

ok 100 numbers

Test #11:

score: 0
Accepted
time: 38ms
memory: 3864kb

input:

10
50000 1000000000
14945976 12846736 277398 7075128 12533968 13805792 7120706 3136112 1102332 14628918 33556221 9626418 3073970 7379354 4754722 14323124 8119284 13341952 4639522 33559898 8455698 33555019 2750888 15445086 12632228 112896 257198 3337600 1462910 768220 10491396 33562170 10123992 33560...

output:

16433166
26883384
14024
4484923
2655078
105987
31134
112599024
5899713
127581034

result:

ok 10 numbers

Test #12:

score: 0
Accepted
time: 36ms
memory: 4056kb

input:

5
100000 1000000000
39282 1066015 1062466 272082 58228 1049517 315024 98990 70944 149646 483724 147520 404642 302334 329860 146090 200222 197060 240026 214656 36610 310816 229774 238514 360684 403142 423786 474384 1049273 1063613 1060442 429178 405908 207638 227118 360282 1067663 232772 53846 487718...

output:

11959
81687
248175012
31990
3479

result:

ok 5 number(s): "11959 81687 248175012 31990 3479"

Extra Test:

score: 0
Extra Test Passed