QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#512218#8322. 魔法手杖kymmykym0 975ms30900kbC++141.1kb2024-08-10 13:51:482024-08-10 13:51:50

Judging History

你现在查看的是最新测评结果

  • [2024-08-10 13:51:50]
  • 评测
  • 测评结果:0
  • 用时:975ms
  • 内存:30900kb
  • [2024-08-10 13:51:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100005;
int n,m,k;
int A[maxn],B[maxn];
const int oo = 1'000'000'000'000'000'000ll;
typedef pair<int,int>pi;
int dpdp(int bit, vector<pi>&vec, int adder){
	if(bit==-1)return min(0ll,adder);
	if(vec.empty())return adder;
	
	vector<pi>lf,rg;
	for(auto x:vec){
		if(x.first&(1<<bit))rg.push_back(x);
		else lf.push_back(x);
	}
	if(lf.empty()){
		if(adder>=oo)return (1<<bit)+dpdp(bit-1,rg,adder);
		else {
			return max((1<<bit)+dpdp(bit-1,rg,adder-(1<<bit)), dpdp(bit-1,rg,oo));
		}
	} 
	if(rg.empty()){
		return (1<<bit) + dpdp(bit-1,lf,adder);
	}
	return max(dpdp(bit-1,lf,adder+(1<<bit)), dpdp(bit-1,rg,adder+(1<<bit)));
}
void solve(){
	cin>>n>>m>>k; 
	--k;
	for(int i=1;i<=n;i++)cin>>A[i];
	for(int i=1;i<=n;i++)cin>>B[i];
	if(n==1){
		if(B[1] == 1){
			cout<<A[1] + (1<<(k+1))-1<<"\n";	
		} 
		return;
	}
	vector<pi>as;
	int adder=oo;
	for(int i=1;i<=n;i++){
		if(B[i] == 2)as.push_back({A[i],B[i]});
		else adder=A[i];
	}
	cout<<dpdp(k,as,adder)<<"\n";
}
int32_t main(){
	int c,t;cin>>c>>t;
	while(t--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3584kb

input:

1 2
1 1 10
69
0
9 1000000000 10
244 710 380 144 439 863 870 166 346
495676227 842003627 148079269 750582321 584950601 767126829 909307499 254106473 942938842

output:

346

result:

wrong answer 1st lines differ - expected: '1092', found: '346'

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 3800kb

input:

2 2
1 1 10
523
0
9 1000000000 10
848 862 206 186 563 318 692 557 937
922116005 577545690 363781833 81032507 443868714 352716275 50542823 305806582 28805127

output:

937

result:

wrong answer 1st lines differ - expected: '1546', found: '937'

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 3548kb

input:

3 2
1 1 10
98
0
9 1000000000 10
329 357 633 469 110 721 457 238 51
40948203 144541423 719902898 403414385 625735025 473335146 107749900 238792543 449945390

output:

51

result:

wrong answer 1st lines differ - expected: '1121', found: '51'

Test #4:

score: 0
Wrong Answer
time: 158ms
memory: 5020kb

input:

4 5
100000 0 30
76630934 108936482 130420626 131855744 105346843 128458246 108243259 68059982 126654362 129080907 113416035 106976866 67840827 131702105 31856035 114313339 128664146 83795983 89307173 119627353 87072570 90008429 101830816 86771207 109365348 78483596 96660700 94183829 84341841 6114378...

output:

102110943
218122143
8488607
26053439
253816243

result:

wrong answer 1st lines differ - expected: '939540479', found: '102110943'

Test #5:

score: 0
Wrong Answer
time: 160ms
memory: 5160kb

input:

5 5
100000 0 30
76630412 108936989 130419821 131855908 105346921 128458123 108243250 68060024 126653456 129080620 113415939 106976648 67840659 131702589 31855988 114313916 128664271 83796359 89307559 119627595 87072119 90007889 101830798 86770759 109365415 78484075 96661493 94184047 84342493 6114315...

output:

102110495
1038108575
8488607
26053293
493940147

result:

wrong answer 1st lines differ - expected: '939540479', found: '102110495'

Test #6:

score: 0
Wrong Answer
time: 157ms
memory: 5136kb

input:

6 5
100000 0 30
76630333 108936734 130420608 131855493 105346592 128458438 108243159 68059640 126653892 129080993 113415838 106976338 67840970 131701923 31855999 114313236 128664302 83796315 89307977 119627172 87072644 90007888 101831307 86771011 109365285 78483904 96661399 94183858 84341903 6114386...

output:

102110849
985679775
8488607
26053415
160492979

result:

wrong answer 1st lines differ - expected: '939540479', found: '102110849'

Test #7:

score: 0
Wrong Answer
time: 975ms
memory: 3588kb

input:

7 250000
2 1 16
40654 60936
1 2
2 1 5
29 18
1 2
2 1 9
367 278
1 2
2 1 6
32 40
1 2
2 1 28
211414711 120442951
1 2
2 1 9
440 62
1 2
2 1 2
2 2
1 2
2 1 6
60 1
1 2
2 1 1
0 0
1 2
2 1 16
39195 9530
1 2
2 1 19
260304 52003
1 2
2 1 12
1492 2878
1 2
2 1 22
2112709 2056045
1 2
2 1 30
840827142 778131799
1 2
2 ...

output:

65527
31
511
55
268435455
511
3
63
1
65535
524287
4093
4194303
1073741823
1015
268435455
1073741823
31
16777213
16777207
262143
31
131071
262143
8190
33554430
1
16777215
0
536870911
1048574
255
67108862
126
7
1023
8388605
536870907
3
262139
1
1
16383
2047
8388607
63
16777213
63
4194301
65534
3355443...

result:

wrong answer 1st lines differ - expected: '55295', found: '65527'

Test #8:

score: 0
Wrong Answer
time: 945ms
memory: 3776kb

input:

8 250000
2 1 24
7245747 7751903
1 2
2 1 18
7301 21614
1 2
2 1 2
1 3
1 2
2 1 3
0 4
1 2
2 1 22
1946046 3459042
1 2
2 1 1
0 1
1 2
2 1 27
110608129 62075905
1 2
2 1 7
79 78
1 2
2 1 1
0 0
1 2
2 1 8
190 156
1 2
2 1 29
213608577 61390223
1 2
2 1 21
194242 1613306
1 2
2 1 8
46 195
1 2
2 1 12
2674 3172
1 2
2...

output:

16777214
262141
2
3
4194301
0
134217727
127
1
255
536870911
2097149
254
4091
1
126
524285
131071
131071
2097151
67108861
4194303
2045
61
4194302
2047
14
8388607
7
65535
16382
524283
1
30
2047
2047
16383
255
268435455
7
2043
33554427
33554423
1
15
62
65534
2097151
2047
16777214
127
8388606
63
3
511
2...

result:

wrong answer 1st lines differ - expected: '16515071', found: '16777214'

Test #9:

score: 0
Wrong Answer
time: 605ms
memory: 30900kb

input:

9 40003
100000 1 30
76630623 108936745 130419844 131856358 105346889 128458736 108243812 68059447 126654184 129080977 113416077 106976936 67840619 131702296 31855896 114313546 128664506 83796193 89307481 119627719 87072176 90007912 101831608 86771305 109366220 78484119 96661356 94183598 84341931 611...

output:

939540479
1073610765
1073641824
3005
536870911
4091
992
4194303
469762047
33554429
22429
3071
2046
10
28671
127
1048575
4194303
0
3
4194303
65535
67108855
1073741822
16777215
94
8189
849298282
268435455
402653183
7
4194302
65535
524287
4194303
196607
31
1023
8389241
148759809
100663295
131071
178412...

result:

wrong answer 6th lines differ - expected: '3255', found: '4091'

Test #10:

score: 0
Wrong Answer
time: 590ms
memory: 30752kb

input:

10 40003
100000 1 30
76630457 108937083 130420232 131855828 105346260 128458262 108242996 68059167 126653670 129080772 113416051 106976793 67840568 131702468 31855850 114313412 128664110 83796459 89307450 119627418 87071762 90007680 101831024 86771509 109365868 78483555 96661066 94183460 84342625 61...

output:

939540479
1073610765
1073641824
119200937
1048575
67108863
6300883
33554431
383
4095
31
100663295
1023
75124094
33554431
8175
65535
3071
20334
2830
30
24575
511
98303
1048575
29
134217727
524287
65534
57202
8388606
95
524287
1187963
65535
2
536870911
31
262139
7
255
268435454
5
360447
63
2046
255
0
...

result:

wrong answer 16th lines differ - expected: '6557', found: '8175'

Test #11:

score: 0
Wrong Answer
time: 401ms
memory: 17892kb

input:

11 40003
100000 1 30
76630674 108936653 130420433 131856265 105346983 128458653 108243409 68059656 126653505 129080757 113415755 106976914 67840002 131701979 31855773 114313774 128664187 83796634 89307850 119627507 87071827 90007813 101831495 86771399 109365557 78483822 96660811 94184023 84342680 61...

output:

939573247
1073610783
1073641829
31
63
2720
33554431
1
32767
7
2097151
2097151
895
67108863
255
8388606
386790
268435455
4194303
4194303
3
16382
7
268435455
31
8388607
1073741823
5
4194303
33554429
7
15
511
786431
5
174918809
126847731
31498
1
12582911
33554431
16383
8388543
54
67108863
3145727
19601...

result:

wrong answer 1st lines differ - expected: '939540479', found: '939573247'

Test #12:

score: 0
Wrong Answer
time: 420ms
memory: 18228kb

input:

12 40003
100000 1 30
76630775 108937143 130420127 131855472 105346114 128458369 108243185 68060064 126653745 129080952 113415931 106976535 67841016 131701837 31855974 114313669 128664055 83796306 89307860 119626895 87072131 90008292 101831649 86771064 109366112 78484048 96660693 94184079 84342338 61...

output:

939564031
1073610783
1073641831
511
509
13031
131071
12287
131071
3
8388607
4194301
382
0
114079
65535
3839
11431108
47
1964794
294356
59
3670015
12287
511
12287
524287
4095
8388607
1073741823
4095
105
7
125829119
258312620
1073741823
0
3670015
49151
469762047
12277531
446
7
4095
16383
268435455
134...

result:

wrong answer 1st lines differ - expected: '939540479', found: '939564031'

Test #13:

score: 0
Wrong Answer
time: 383ms
memory: 17932kb

input:

13 40003
100000 1 30
76630774 108936584 130420001 131856305 105347060 128457982 108243169 68059620 126654022 129081029 113415335 106976790 67840471 131702040 31855824 114314232 128663903 83796420 89307827 119626984 87072029 90008558 101830939 86770995 109365419 78483800 96660514 94183753 84342755 61...

output:

939556863
1073610783
1073641827
16379
16777215
131071
1126331
221158213
1048575
619401751
524287
4194303
2035055117
33554431
7
511
383
510
16375
126
196607
262142
2097151
2
54
115993780
7
16351
3
10465754
60798644
4194303
7
8190
1331759
219604519
2047
13
127
3645676
30
4095
191
536870911
4095
15
191...

result:

wrong answer 1st lines differ - expected: '939540479', found: '939556863'

Test #14:

score: 0
Wrong Answer
time: 1ms
memory: 3764kb

input:

14 5
100 1000000000 30
13132 1189 129473 100435 99142 27988 125913 84108 88618 104500 18510 127909 33713 41539 73168 52981 93666 111173 97215 18318 116125 48796 66468 68341 66995 8141 6453 78522 5137 102161 79767 83305 55735 35923 57672 40415 26124 3517 89580 103805 63333 70578 15006 115257 25327 11...

output:

4446
133169237
626347
130404
872415232

result:

wrong answer 1st lines differ - expected: '1073641471', found: '4446'

Test #15:

score: 0
Wrong Answer
time: 1ms
memory: 3584kb

input:

15 5
100 1000000000 30
13147 1100 129952 101117 98742 27859 125802 84826 88433 104546 18804 127522 33108 41885 72848 52261 94114 110852 97024 17835 116004 48702 65612 68427 67541 7813 6415 78436 5289 102296 78964 83467 56256 36720 58141 39956 25783 3977 89405 104251 63057 69881 14546 115008 24936 10...

output:

4228
1006633045
626242
130412
538968064

result:

wrong answer 1st lines differ - expected: '1073641471', found: '4228'

Test #16:

score: 0
Wrong Answer
time: 28ms
memory: 3956kb

input:

16 4003
10000 1000000000 60
6301301488220013 13036910415217886 3587708952967093 9679001900905121 15370074903700843 10699351669343223 3693263165367499 11069887286230748 16712579672850495 7401912839403587 2739985286259605 4571772340856038 7048969239142713 1894459710006182 17112800883496323 12320029364...

output:

11637232262225084
747667906896148
292211797833931
8346001
3056255361
3957435538
954458618
893424
1435
766845
265787931
2944718223
4200074318
28102111
958201901
136506182
1956508121
861517
3088222135
4
4164557731
2649
198426670
295211869
4003602797
718068957
3568464529
1481744391
3344737888
305967350...

result:

wrong answer 1st lines differ - expected: '1134974176306659327', found: '11637232262225084'

Test #17:

score: 0
Wrong Answer
time: 31ms
memory: 3960kb

input:

17 4003
10000 1000000000 60
6301301819534654 13036910822653667 3587709968963537 9679000983663529 15370074961371554 10699347928378657 3693263473368908 11069883997526525 16712580951412763 7401916234416503 2739986911540418 4571770484223398 7048969495053322 1894461412350279 17112799936179837 12320030978...

output:

11637231732654358
455197813907732
292212209409853
12052039
2527728349
28049715
3438502658
845140900
1937725989
2851265389
31
794520
1217
1
0
1648360219
1033102
431158937
2471342782
23
2072352231
13185
66111
4245405551
3090378296
20
3508865
2374018588
68355
2
2190997073
1123185099
3897877377
64794339...

result:

wrong answer 1st lines differ - expected: '1134973076795031551', found: '11637231732654358'

Test #18:

score: 0
Wrong Answer
time: 23ms
memory: 3748kb

input:

18 4003
10000 1000000000 60
6301305150188370 13036910274580735 3587707298181505 9679004703165232 15370075141428877 10699349494581236 3693260766091278 11069885717856260 16712580184551432 7401916423007610 2739984412836669 4571773004118082 7048970479824295 1894458866748282 17112803260092779 12320029000...

output:

11637233747053412
730075720851732
292211607403314
200429
428620
3491167865
1777
215987409
181678
3201829911
2
2895437564
6714842
183968424
777582902
3235943927
11118674
652573067
441612
1307739251
289966546
2
119212
102045417
3948848618
1720212031
1699270565
471
637213733
7916988
2769994185
7
930519...

result:

wrong answer 1st lines differ - expected: '1134977474841542655', found: '11637233747053412'

Test #19:

score: 0
Time Limit Exceeded

input:

19 62501
100000 1000000000 120
1154838249421518343773531773357597778 1154838249421518343773531773357629327 1154838249421518343773531773357650307 1154838249421518343773531773357651709 1154838249421518343773531773357625821 1154838249421518343773531773357648391 1154838249421518343773531773357628650 115...

output:


result:


Test #20:

score: 0
Time Limit Exceeded

input:

20 62501
100000 1000000000 120
323632031276481459143358069001495634 323632031276481459143358069001527183 323632031276481459143358069001548163 323632031276481459143358069001549565 323632031276481459143358069001523677 323632031276481459143358069001546247 323632031276481459143358069001526506 3236320312...

output:


result:


Test #21:

score: 0
Time Limit Exceeded

input:

21 62501
100000 1000000000 120
94863733210630102424008628084424216 134857169996406520360367913319523910 161452665267901932764497978184577026 163229916633468866695669655916793917 130413130894076501442669761804067887 159024080878679252370015542440688101 133998758779238309221865949392709341 84253191505...

output:


result:


Test #22:

score: 0
Time Limit Exceeded

input:

22 120001
100000 1000000000 120
47471234275189825886337730002101330 47471234275189825886337730002132879 47471234275189825886337730002153859 47471234275189825886337730002155261 47471234275189825886337730002129373 47471234275189825886337730002151943 47471234275189825886337730002132202 4747123427518982...

output:


result:


Test #23:

score: 0
Time Limit Exceeded

input:

23 120001
100000 1000000000 120
10384594543745281933157089286344285 10384595087221325583432181750603761 10384596344313448100419024142756824 10384597896452402824418716086599406 10384599662161038685053136018241571 10384600136159512396111755729028709 10384601958291386084902861505361244 1038460344973912...

output:


result:


Test #24:

score: 0
Time Limit Exceeded

input:

24 120001
100000 1000000000 120
10384594585679242355840829886289379 10384595083750076569134324633632941 10384596423425537641166720528386677 10384598270636404608178558554968102 10384598723408000881156593449465505 10384600392016296777984789088889743 10384602014485619490959986853506329 1038460298717050...

output:


result:


Test #25:

score: 0
Time Limit Exceeded

input:

25 120001
100000 1000000000 120
10384594059032377855972206804990515 10384595922446112233978399250497752 10384596677646074836565734489994716 10384597585175584397302672981127521 10384599121981302637859909713499899 10384600188980133483790411300324684 10384601157708131158985167495674683 1038460244379676...

output:


result: