QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369569 | #7932. AND-OR closure | JerryTcl | WA | 1ms | 11360kb | C++20 | 1.7kb | 2024-03-28 14:37:50 | 2024-03-28 14:37:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using uint64 = unsigned long long;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n; vector<uint64> a(n);
uint64 LAD = ~0, LOR = 0; vector<uint64> MSK(40, ~0);
for(uint64 &x : a) cin >> x, LAD &= x, LOR |= x;
for(int p = 0; p < n; ++p)
for(int i = 0; i < 40; ++i)
if(~(a[p] >> i) & 1) MSK[i] &= ~a[p];
bitset<40> vis(LAD | ~LOR); vector<int> keys;
for(int i = 0; i < 40; ++i) if(!vis[i])
for(int j = i + 1; j < 40; ++j)
if((MSK[i] >> j) & (MSK[j] >> i) & 1) vis[j] = 1;
for(int i = 0; i < 40; ++i) if(!vis[i]) keys.push_back(i);
n = keys.size(); vector<vector<int>> src(n);
vector<int> topo; vector<int> ind(n); int hd = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j) if(i != j)
if((MSK[keys[i]] >> keys[j]) & 1)
src[i].push_back(j), ++ind[j];
for(int i = 0; i < n; ++i) if(!ind[i]) topo.push_back(i);
while(hd < n) for(int i : src[topo[hd++]])
if(!--ind[i]) topo.push_back(i);
reverse(topo.begin(), topo.end());
vector<int> itopo(n); const int m = n / 2;
for(int i = 0; i < n; ++i) itopo[topo[i]] = i;
vector<uint64> G(n); vector<uint64> buf(1 << m, -1);
for(int i = 0; i < n; ++i) G[i] = ~(1ull << i);
for(int i = n - 1; i >= 0; --i)
for(int j : src[topo[i]]) G[i] &= G[itopo[j]];
const auto &dfs = [&](auto &&self, uint64 p) {
if(!p) return 1ull; int hi = 63 ^ __builtin_clzll(p);
if(hi < m && ~buf[p]) return buf[p];
uint64 ret = self(self, p ^ (1ull << hi)) + self(self, p & G[hi]);
return hi < m ? buf[p] = ret : ret;
};
printf("%llu", dfs(dfs, (1 << n) - 1));
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3788kb
input:
4 0 1 3 5
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
5 0 1 2 3 4
output:
8
result:
ok 1 number(s): "8"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
49 1097363587067 1096810445814 275012137504 1096739142630 1096809921522 1087071335264 829364908576 949625500192 1087142638448 1096200190829 1097292808175 1095750860656 1087144145776 1097346808827 1095734082416 1096755396578 829230678048 1095663303524 1087072842592 1096216444777 949623992864 10962714...
output:
52
result:
ok 1 number(s): "52"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
40 32 830045728951 278250692646 1021660937663 881584025918 275993636902 275953000615 327534555567 329833558447 278293950631 327534558639 893011227647 327533244718 1021660934591 1021661000703 893011161535 1030787822591 832344731831 275994947751 1073741862 329832247598 278292639782 1030787825663 10307...
output:
44
result:
ok 1 number(s): "44"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
113 995010353355 513836652779 438679050443 548477566959 507675377387 412904849600 412904919234 431506823898 1065151889147 436774574666 413152182848 438955900619 412871032896 436497750090 24159262794 419628520130 479476914639 427941630147 436493424714 412875358272 541196352 1098370744303 445117176011...
output:
143
result:
ok 1 number(s): "143"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
63 274873712607 183352984580 549655082623 549688637311 463755584628 188974231516 463789156220 183487485535 274873708508 183487464532 463789160319 188907059039 463755605631 137709486080 463822782207 181339965016 274840153820 187799217236 187799238239 463789139316 146970789464 549722255100 18897421461...
output:
63
result:
ok 1 number(s): "63"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
46 343736386052 77314129940 1099444493311 1094075521919 68724195332 353165185622 541926877791 490604139103 404722784854 1099444493023 1094142655359 410091756246 547530709727 1094142655071 352863191638 525047822943 524980689503 524678695519 547597843167 541859744639 1099511626463 507483193951 3875417...
output:
46
result:
ok 1 number(s): "46"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
49 73358378052 349495737422 73358394852 74617839076 349496261711 74433224164 74616757732 377952403438 349494672878 74618363365 74432142820 74156382272 352180764143 352180223054 77302324708 74432126020 1045287271919 377952927727 360772271598 74617822276 77302848997 1039379725807 1074829312 3494946560...
output:
49
result:
ok 1 number(s): "49"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
55 1097313795995 1065134439323 77916805395 1028593268635 305549054739 305549054720 301254054675 1099511627775 376450620179 1030774306715 375750245147 305951707931 304942973696 302332064531 304945074944 308132746011 306627064576 9196278016 13491278099 377931283227 374672235291 307730092819 3066270645...
output:
59
result:
ok 1 number(s): "59"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
140 618955644536 618880146008 618956693368 206638591281 618954923376 618881194840 619835332946 624338984050 405244424 73492646960 628566235994 210935738169 69122164752 652800941950 632935669370 550158506048 770376204155 623249907056 551251581514 618879031632 761781682043 550024288320 624342589306 61...
output:
174
result:
ok 1 number(s): "174"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
98 276234289538 276435628434 280525066271 426776261023 1097162807743 1097363685375 1087951250 859273990194 4309160351 864646910399 860553736626 276234293650 495327959007 864642715711 280525062159 4304961551 5378719759 348204339231 280529260959 1097364142527 280730595743 495529292191 1010893910463 10...
output:
110
result:
ok 1 number(s): "110"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
68 394201661537 549394440821 549394178661 1099503239159 488557772900 145090412581 144956194852 462787969060 325347967008 531641925749 462922186789 282532511777 549411354231 549680178807 325482184737 1099234144247 1099503103607 76235669600 548687389284 532212367477 256625344612 548821869173 549680314...
output:
68
result:
ok 1 number(s): "68"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
54 514313778046 514313813886 81942544928 497669898095 494448209774 357005026154 512703000431 496058917759 496596025198 514850780015 219536687652 13155959328 515387686783 8860467744 82093548392 13306954272 513239835519 497669862255 511629091694 515396075519 9011462688 512702964591 2097664 51538765094...
output:
54
result:
ok 1 number(s): "54"
Test #14:
score: 0
Accepted
time: 0ms
memory: 4024kb
input:
81 69795316278 7523011620 901144743607 275951648773 1073741828 621967642166 5372903428 71943327286 626266803766 344673223223 351120395831 540133691007 1090124320311 1090158005887 540100038327 351128829879 282400918565 896845549111 351154114303 540133723903 346821234231 348972384823 1090166407039 322...
output:
81
result:
ok 1 number(s): "81"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
44 5411176842 31453621226 5671225632 5411185610 5679614378 5671234400 856154451946 4841930890 5679876523 31453883371 858319044587 5940838656 5679885291 6217935851 832544784362 6217664938 832545046507 6217927083 5679623146 6217673706 5949236170 31991933931 858318782442 5402796864 7843953642 319916717...
output:
58
result:
ok 1 number(s): "58"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
77 481034223583 480413171607 1073807361 37616164743 443973091295 37614586113 205526744983 1030790053855 989031301087 31576366983 1074791938 480967081879 169018994451 338271866627 475782164315 164321902487 439274942299 1108348674 481036320767 480479784795 443905421075 306462265091 480412643091 342970...
output:
88
result:
ok 1 number(s): "88"
Test #17:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
82 272174463709 17246986261 18359263381 91642145429 267745274005 113252276425 547052501727 17179877396 274720403221 134592899733 821949151965 115802410369 684367587989 229089487509 113113860097 115798215937 3863741825 91637950997 409605159647 503963331095 229085293077 132978093333 1179385985 8734717...
output:
122
result:
ok 1 number(s): "122"
Test #18:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
54 2109536 921967046467 1099171741543 578354952800 921969147747 923111178111 575525625920 1219768932 1060550197119 1059408166755 991746702182 853230791490 923043938151 575525879808 575525617664 647089106497 923041836871 0 3902024260 854305581894 1060482957159 991813942142 579427641924 2829335136 142...
output:
56
result:
ok 1 number(s): "56"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
112 1099477022463 756484767267 789981003447 790140810943 22758818854 774948617763 756451505707 583822859966 584091426494 756485062187 760209286151 18388354082 573085146662 536892962 779210028583 22683321382 22683321350 789905800895 34033129142 583713806014 572514698246 33957631670 572439200806 77894...
output:
166
result:
ok 1 number(s): "166"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
35 941452556157 627065233440 907084428069 907080233248 941452687359 1099494848511 958767560703 907080365490 924399433655 901980959269 902785216544 1099494717309 901980960309 907084429109 958767429501 1047811716917 906271782192 1065126590261 902789412405 906275977013 901976765488 902789411365 9070802...
output:
35
result:
ok 1 number(s): "35"
Test #21:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
73 1099243190263 479683662551 470890992133 1029382787863 329152352773 141738639360 36523999744 141738659844 1029381715735 1099243181047 329152332289 54274314757 54274294273 0 549487376119 416616677376 470890992151 549420192311 178262659588 1029449962455 416616697860 292628332545 1020657292055 20484 ...
output:
75
result:
ok 1 number(s): "75"
Test #22:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
60 126720696480 40819253408 813920904114 1090787437562 728664138658 539305993192 728018191234 41364512928 286880 728019461042 814020322210 178258183040 262144 539851252712 728118879138 728120124338 1090921660415 1089847392255 1090787438587 40819228800 178803467168 814566827955 1089713170427 81456682...
output:
62
result:
ok 1 number(s): "62"
Test #23:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
188 632311943094 147138318536 649492156292 909358280503 237602068168 651501194752 9665777664 770858164044 790047481544 77312033330 151701820488 632169336498 787895770696 805285044222 807294082682 651643834244 701995555912 376102151731 1082331414527 649349549696 736422436040 772867235400 736565042636...
output:
306
result:
ok 1 number(s): "306"
Test #24:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
46 129997256715 78407313819 1092078581803 1040475761083 8593088515 1040479988155 78403086747 1099477925375 1094243367419 1094213711979 8590991362 1092065703979 69796366347 1099511496703 1040463210539 1040471861291 1094230489595 1099469274623 78384211978 1040488638907 3145731 78390536203 109422658980...
output:
46
result:
ok 1 number(s): "46"
Test #25:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
85 497140360702 77645758816 77780107750 217387516390 409074525691 357524431330 492299928034 409066136035 543841632739 357524562406 357532820986 409074656767 404234355175 82612019686 492174099832 78182637824 548673675751 497131839970 268435712 77578633216 353103570296 497131971046 222085079392 352692...
output:
99
result:
ok 1 number(s): "99"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
48 326495241995 330795507599 334016733071 274886350211 292135556483 1030657867759 8425473 327338874767 331634892687 1099511627775 309246072587 316763332491 480885014479 334856118159 326495295371 475749611471 326499489679 292135503107 334872895407 329720715151 326495278859 274886296835 8388609 343681...
output:
48
result:
ok 1 number(s): "48"
Test #27:
score: 0
Accepted
time: 1ms
memory: 3980kb
input:
72 41547483650 1007007095631 36042459651 35975070209 1099478072219 50170976838 1099477015451 41547221504 1013585861455 1099460008579 1099511626719 1084291304067 1099493563079 1006973541131 998316179969 36042197505 1092914830287 34901328384 998349996615 1092914797255 41581038150 1099460041611 9983833...
output:
80
result:
ok 1 number(s): "80"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
50 196608 10203109376 10219886612 1095149026559 1077969157373 1082264648957 978744990869 283468321793 1013238955157 8590200832 285097810965 559421788288 834836847745 0 8590397440 1081962626237 458752 559438827668 8589938688 9666236416 262144 869347589269 8590135296 1026425355479 834316752021 1030720...
output:
50
result:
ok 1 number(s): "50"
Test #29:
score: 0
Accepted
time: 1ms
memory: 4100kb
input:
98 990910277751 648537499794 652832471954 648537504402 927559379286 72582471680 567251847184 652681476882 552823465984 790271551923 1065149463543 1060854491383 1065151888383 622608300544 927559383894 923415411414 582888253714 622615109632 639947565200 790120561459 720327338291 576378693650 639947569...
output:
100
result:
ok 1 number(s): "100"
Test #30:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
51 551905919014 612343036974 618399793151 560500047910 596740160574 551906188326 820338606079 595280576046 594861104174 586686447150 586535149614 2149580838 614180175871 551903821824 595280576495 2147752960 612494065647 596740161023 618475290623 562379373622 596891189247 2149850150 596739891262 6124...
output:
51
result:
ok 1 number(s): "51"
Test #31:
score: 0
Accepted
time: 1ms
memory: 4040kb
input:
196 548915379187 414686890643 274949409299 274962022400 412518402563 1096523710327 518829603555 312528276099 862313483991 999882477255 450109852355 585204174423 549721734139 413341567499 2563 1068606422775 412539406867 516698929763 1068585418471 414670342835 450118535843 480187501491 450105920179 99...
output:
228
result:
ok 1 number(s): "228"
Test #32:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
60 138858799744 17525909122 718835005383 237832224707 567298668486 443819472834 224808648642 1062466994119 431056332739 138875745216 346072000 346038912 156038669954 499687604162 156194289603 774564462534 705811429318 156055615426 17542821506 512572506050 980829059015 362984384 362951296 17525942210...
output:
60
result:
ok 1 number(s): "60"
Test #33:
score: -100
Wrong Answer
time: 0ms
memory: 11360kb
input:
9363 1043131227225 785298644298 785298644426 768051666240 776706678080 767112121448 1043062021200 208361622848 775366593858 1090376130011 1043131489633 768119360840 974411488610 1043130965088 768253582699 1099503239167 758184631616 775635029450 225541496128 768253578587 1064614976979 768116743232 10...
output:
84
result:
wrong answer 1st numbers differ - expected: '16968', found: '84'