QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#902518 | #10010. Kids And Sequence Game | open your brain (Zhi Zhang, Yanru Guan, Jianfeng Zhu)# | AC ✓ | 224ms | 307000kb | C++14 | 1.2kb | 2025-02-16 16:06:33 | 2025-02-16 16:06:33 |
Judging History
answer
#include <bits/stdc++.h>
const int mod=998244353;
using namespace std;
int n,a[3150010],cnt,f[3150010];
priority_queue<int>q[3150010];
vector<int>E[3150010];
void qmo(int &x){
x+=(x>>31)&mod;
}
int ed=0;
void dfs(int u){
f[u]=0;
while(q[u].size()) q[u].pop();
for(int v:E[u]){
dfs(v);
f[u]-=f[v];
if(q[u].size()<q[v].size()) q[u].swap(q[v]);
while(q[v].size()) q[u].push(q[v].top()),q[v].pop();
}
int nw=a[u];
while((int)q[u].size()>=2&&nw<q[u].top()){
int x=q[u].top();q[u].pop();
int y=q[u].top();q[u].pop();
nw=nw+y-x;
}
if(q[u].size()&&nw<q[u].top()) ed+=nw-q[u].top(),q[u].pop();
else q[u].push(nw);
}
void sol(){
scanf("%d",&n);
a[cnt=0]=0,E[0].clear();
for(int i=1;i<=n;i++){
long long w;
scanf("%lld",&w);
int nw=0;
while(w){
a[++cnt]=w&1,E[nw].push_back(cnt),E[cnt].clear(),nw=cnt;
w/=2;
}
}
dfs(0);
int ans=(cnt&1?ed:-ed);
for(int i=0;q[0].size();i^=1,q[0].pop()){
if(i) ans-=q[0].top();
else ans+=q[0].top();
}
printf("%d\n",-ans);
}
int main(){
int T=1;
// scanf("%d",&T);
while(T--) sol();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 21ms
memory: 178856kb
input:
5 13 29 10 1 26
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 103ms
memory: 235504kb
input:
21417 7840302172680170307 5321573529083198387 8214462622877325148 1143008495081213578 6262491513147717806 5039611704168873788 8094944116872031972 2567428672066144766 6056648091050202450 3565740003036766392 2925999037919145749 5542147304038247878 862707825558040953 4471890990246559484 263325942648568...
output:
67086
result:
ok 1 number(s): "67086"
Test #3:
score: 0
Accepted
time: 41ms
memory: 193732kb
input:
4842 6276531128253719151 61508240822203132 999202787753211522 6951790220915338640 56095670132388071 8927118903603678475 8509775824215215960 1940125042287078921 6095082227332506633 2438456117711026831 909577236975672789 4182111456976047968 5628926892437643194 8445067540173562511 4422141394268167047 7...
output:
14877
result:
ok 1 number(s): "14877"
Test #4:
score: 0
Accepted
time: 104ms
memory: 231764kb
input:
20970 4712760083827267995 4024814989415983686 3007314993778840999 3537199909894687894 3073071855381899551 3591254070478674650 8924607531558399948 1312821408213045781 6133516363614810815 1311172232385287271 8116527468592008341 2822075609913848059 1171773926757436923 3194872061835724322 62110233663456...
output:
64678
result:
ok 1 number(s): "64678"
Test #5:
score: 0
Accepted
time: 110ms
memory: 236664kb
input:
21690 3148989043695784136 7988121738009764240 5015427195509503181 122609598874037147 6090048044926378328 7478761274208446634 116067202046808128 685517778433979936 6171950499897114997 183888342764580415 6100105667648535380 1462039762851648149 5937992993637039165 7168048616057694645 799990533842306288...
output:
67559
result:
ok 1 number(s): "67559"
Test #6:
score: 0
Accepted
time: 174ms
memory: 278220kb
input:
37818 1585217994974365684 2728056445453801689 7023539401535132659 5931391329003129505 9107024238765824401 2142896441083442809 530898909389992116 58214148654914091 6210384636179419180 8279976494293616662 4083683862410095124 102003915789448239 1480840027956832894 1917853133424889160 565415273645734990...
output:
116854
result:
ok 1 number(s): "116854"
Test #7:
score: 0
Accepted
time: 106ms
memory: 235572kb
input:
21242 21446954842881824 6691363194047582243 9031651603265794840 2516801017982478758 2900628391455527370 6030403640518247496 945730612438208808 8654282551435656759 6248818772461723362 7152692604672909806 2067262057171654868 7965340105582024137 6247059094836435135 5891029691941826779 23542972457231829...
output:
66039
result:
ok 1 number(s): "66039"
Test #8:
score: 0
Accepted
time: 176ms
memory: 274328kb
input:
37370 7681047947271206477 1431297905786586989 1816391772436648510 8325582739521636524 5917604585294973443 694538811688210968 1360562324076360092 8026978921656590914 6287252908744027544 6025408719347170245 50840256228181907 6605304254224856932 1789906124861261568 640834205014053998 414317921780063082...
output:
-116099
result:
ok 1 number(s): "-116099"
Test #9:
score: 0
Accepted
time: 179ms
memory: 276680kb
input:
38090 6117276902844755321 5394604654380367542 3824503982757245283 4910992428500985777 8934580774839452219 4582046011123015655 1775394027124576784 7399675287582557774 6325687045026331726 4898124838316397981 7257790487844517459 5245268407162657022 6556125191740863809 4614010763530991617 59320611855831...
output:
117724
result:
ok 1 number(s): "117724"
Test #10:
score: 0
Accepted
time: 35ms
memory: 188628kb
input:
4218 4553505862713271462 134539357529437696 5832616184487907465 1496402117480335031 2728184927529155188 8469553214852787638 2190225734467760772 6772371653508524633 6364121181308635909 3770840948695691125 5241368686901044499 3885232560100457112 2098972226060657539 8587187313457994644 7720943157660559...
output:
12957
result:
ok 1 number(s): "12957"
Test #11:
score: 0
Accepted
time: 203ms
memory: 295984kb
input:
45451 3737589410856458211 4577988173692643476 246168402134338305 2687448292630876839 2487426397312444598 5392695302984426734 4167827064131207496 9119651724166194970 923268868619740625 7374190067254097527 6442143898547197083 3054389169291312224 8437184414367356593 4711851611710314484 1516353378594103...
output:
-142125
result:
ok 1 number(s): "-142125"
Test #12:
score: 0
Accepted
time: 66ms
memory: 208320kb
input:
11579 2173818370724974352 8541294922286424030 2254280612454935078 8496230018465001901 5504402586856923375 56830469859422910 4582658767179424188 8492348094387129126 961703000607077511 6246906177633390670 4425722097603724123 1694353322229112314 3980031448687150322 8685028165932284807 33052353506715519...
output:
-36258
result:
ok 1 number(s): "-36258"
Test #13:
score: 0
Accepted
time: 202ms
memory: 295156kb
input:
45003 610047326298523196 3281229634025428776 4262392814185597260 5081639711739318451 8521378776401402152 3944337673589194893 4997490478817575472 7865044456018128689 1000137136889381694 5119622296602618406 2409300292365283867 334317475166912404 8746250511271785267 3434832683299479322 5094117322748999...
output:
140170
result:
ok 1 number(s): "140170"
Test #14:
score: 0
Accepted
time: 133ms
memory: 251376kb
input:
28427 8269648318726847848 7244536382619209329 6270505020211226737 1667049400718667704 2314982933386072417 7831844877318966876 5412322181865792164 7237740826239062845 1038571273171685876 3992338411276878846 392878487126843610 8197653664959488303 4289097545591578997 7408009241816416941 688299929482644...
output:
-88190
result:
ok 1 number(s): "-88190"
Test #15:
score: 0
Accepted
time: 77ms
memory: 211772kb
input:
11851 6705877274300396693 1984471090063246779 8278617221941888919 7475831122257825470 5331959122930551194 2495980039898995756 5827153889208976152 6610437196459997000 1077005409453990058 2865054521656171989 7599828718743179162 6837617817897288393 9055316612471181238 2157813754888644160 86718812626089...
output:
36523
result:
ok 1 number(s): "36523"
Test #16:
score: 0
Accepted
time: 136ms
memory: 250416kb
input:
27979 5142106229873945537 5947777838657027333 1063357391112742589 4061240811237174723 8348935316769997266 6383487247923735035 6241985596552160140 5983133562385963860 1115439545736294240 1737770636330432429 5583406917799706202 5477581970835088483 4598163646790974967 6130990313405581779 12373911978316...
output:
-86665
result:
ok 1 number(s): "-86665"
Test #17:
score: 0
Accepted
time: 137ms
memory: 252956kb
input:
28699 3578335185447494382 687712546101064782 3071469592843404770 646650500216523977 2142539469459700235 1047622410503763914 6656817303895344128 5355829932606898015 1153873682018598423 610486746709725572 3566985112561265945 4117546119477921277 141010676815801400 880794830772776294 3026273169909048385...
output:
-89127
result:
ok 1 number(s): "-89127"
Test #18:
score: 0
Accepted
time: 201ms
memory: 293788kb
input:
44827 2014564145316010522 4651019290399878040 5079581798869034248 6455432230345616334 5159515659004179012 4935129614233535898 7071649011238528116 4728526302827832170 1192307818300902605 8706574898238761820 1550563311617792985 2757510272415721368 4907229747990370938 4853971384994746617 48151551419864...
output:
-139334
result:
ok 1 number(s): "-139334"
Test #19:
score: 0
Accepted
time: 137ms
memory: 251560kb
input:
28251 450793100889559366 8614326038993658594 7087694000599696429 3040841919324965588 8176491852843625085 8822636817963307881 7486480718581712104 4101222668753799030 1230741954583206787 7579291012913022260 8757513538939161241 1397474425353521458 450076778015197371 8827147939216716940 6604037118358911...
output:
87706
result:
ok 1 number(s): "87706"
Test #20:
score: 0
Accepted
time: 203ms
memory: 293020kb
input:
44379 8110394093317884019 3354260750732663339 9095806206625325907 8849623645159090650 1970096001238360758 3486771984838304056 7901312425924896092 3473919038974733185 1269176090865510970 6452007127587282699 6741091737995688280 37438573996354252 5216295844894799612 3576952456583911455 8392919090436359...
output:
-138028
result:
ok 1 number(s): "-138028"
Test #21:
score: 0
Accepted
time: 202ms
memory: 293056kb
input:
44566 5572168088844850397 7094264124416206694 4471758243703450473 3340416922280475232 3410132279364898591 351732354396549993 8122322037313339039 930508937487548004 7277152342296219743 1830695345238928530 8366473277280580048 6155030434493416027 476710472953574590 9046515444424318286 13281581828597224...
output:
138377
result:
ok 1 number(s): "138377"
Test #22:
score: 0
Accepted
time: 20ms
memory: 179052kb
input:
1 6136626533043186517
output:
7
result:
ok 1 number(s): "7"
Test #23:
score: 0
Accepted
time: 224ms
memory: 307000kb
input:
50000 8611549887664082048 6148916907439641941 1537237468907737773 7680226634281299278 3074469073735211860 6140454311515793835 2158953246983364099 6148914645400464682 72057624119467520 2568283487819208252 1713726314003241937 436815163887272888 6077232397167536810 7877734128787278546 85020078278772240...
output:
223750
result:
ok 1 number(s): "223750"
Test #24:
score: 0
Accepted
time: 66ms
memory: 202676kb
input:
10656 16777215 9187344210229985295 8589934591 8796093022207 9223368721140532225 16383 70364449202431 8589934591 36028797153181695 24576 4845679438727423969 144115188075855871 72057602594308097 3 31522173702045715 9007164895010819 268369920 4399120220671 36024398972453112 576425567932383231 347621596...
output:
-8507
result:
ok 1 number(s): "-8507"
Test #25:
score: 0
Accepted
time: 89ms
memory: 231992kb
input:
18198 6154403407462980178 6136905092230239573 6146053040460092757 6149195982961988949 6148914691236517210 6148936773095738037 6148867778740398762 6149289991205464746 6148911744905733461 6100876295211231914 6148915057740393130 6148914691236517205 6100499986999039274 6148914691236516517 53802998050761...
output:
-253855
result:
ok 1 number(s): "-253855"
Test #26:
score: 0
Accepted
time: 80ms
memory: 203844kb
input:
11376 143561034752327679 281474439839744 8795020328959 72057594037927935 4504684098240639 4504690553253944 16777215 283726785098547136 576460220264349680 103095991303 72057594033733632 567456295117684799 31525197391855615 10009679384264328 252223296569359871 135799564992245766 562949953421311 171796...
output:
-9038
result:
ok 1 number(s): "-9038"
Test #27:
score: 0
Accepted
time: 27ms
memory: 182940kb
input:
1622 6244968027039028570 3074458078626010458 2642018047901349162 6154919399113708885 6136905641986009781 6136905275470994090 5572442210809042283 7902310369965331659 6148914691236517205 6148914691236517205 6725363715590675797 7656916831674471717 6148914691236517205 6171456054001052501 595074890204114...
output:
-22885
result:
ok 1 number(s): "-22885"
Test #28:
score: 0
Accepted
time: 125ms
memory: 241028kb
input:
27504 4571170915466856447 70368742097026303 4468075684437820 4610564447982059392 1023 67556193433804863 35184367894531 2199022994431 144114638320041984 144115187807682304 576460752303292416 134217727 138572816449472 7 281474440101887 34359738366 35046933135360 288089638663356416 4503049871557631 115...
output:
22210
result:
ok 1 number(s): "22210"
Test #29:
score: 0
Accepted
time: 91ms
memory: 229588kb
input:
17750 7301836195842667861 6004013764798864037 6533221859433207125 6148914691236516522 6148911805018494294 6148920555298532010 6148914691225332394 6148914691236517205 6148914507984491861 6148914691236517205 6150415891115103573 3122873974001412758 5380300354831952553 6148914692668216666 61489146912337...
output:
-248466
result:
ok 1 number(s): "-248466"
Test #30:
score: 0
Accepted
time: 64ms
memory: 202268kb
input:
10928 4398029733888 2198754820096 1048575 114349175750655 3 1119135815193067395 9223372036854253519 1099511365632 140737488093215 108103966063067263 536870911 17179868160 1080864047471001600 144115188075855871 9222809087169758207 2251782667370495 36028797018963840 576460752303423487 1117104887160888...
output:
8704
result:
ok 1 number(s): "8704"
Test #31:
score: 0
Accepted
time: 85ms
memory: 232712kb
input:
18470 7662159729754724170 6148914691236517205 6148914691236517205 6148914691236517205 6172934623688567466 6176033320096606889 7878390987887432537 6148867778740398762 5424244535684410069 6148914966472338090 6148727058342456018 6148914691236517205 6148914691594431146 5427590899340497239 61489146912365...
output:
-259797
result:
ok 1 number(s): "-259797"
Test #32:
score: 0
Accepted
time: 131ms
memory: 240188kb
input:
27056 481304772096 1048575 2251795652903360 63 137405399039 9187343248293625852 67106876 2304787684342615235 17591049388031 4503599627239487 18013850901133313 8864279314176 133143986207 17609363816448 1082332806119 576354170540392463 4467570830384956415 31 481069891583 540432504633442303 98516241848...
output:
-21722
result:
ok 1 number(s): "-21722"
Test #33:
score: 0
Accepted
time: 144ms
memory: 279536kb
input:
34598 6154884306367589033 6145912336246593097 6148915057740393122 6148914691236517034 6245554432882600618 7337865359364893397 6149008699570170538 7685768155702666586 6148914691236517205 5956761107135374677 6148914679783271082 6148913969670826645 6149290002658710869 6149288525189786282 61489146912337...
output:
486429
result:
ok 1 number(s): "486429"
Test #34:
score: 0
Accepted
time: 138ms
memory: 244472kb
input:
27776 2305834238890475520 4398046511103 8589934591 8944076534804877210 287106675234697342 9082914992467742464 2047996558885907571 2296835809958956999 424340630270208 71498914901004287 2272066012008411136 281474976710656 4294967295 13510815789871100 72127945602244096 2305843008743930880 8866461766393...
output:
22323
result:
ok 1 number(s): "22323"
Test #35:
score: 0
Accepted
time: 24ms
memory: 180700kb
input:
726 6245742084656638634 6094868563677768362 6172933829119617705 7301930020835605293 6148914691236605269 5374294822321040042 5956755243073361238 6148841287561030315 6148914691236517205 5933164122700690790 6148914782840466101 6148920460719510874 6148915790815253842 7734181571113342291 6148914691236518...
output:
10191
result:
ok 1 number(s): "10191"
Test #36:
score: 0
Accepted
time: 183ms
memory: 276164kb
input:
43904 3394896786382852 142989305348882304 8785339798898358599 255078107709440 144115188075855871 17523969884670 8589934464 67108863 271341877549072383 16651386879 136109059798581255 8589934591 288230376151711740 549755813880 8935220574819491839 15032386017 31 8388607 8070450532264706040 703687357890...
output:
-34988
result:
ok 1 number(s): "-34988"
Test #37:
score: 0
Accepted
time: 29ms
memory: 183032kb
input:
1446 5283385047681554262 6148914691236517205 6148911759107730090 6148913956886588074 2978197484878845268 6148911759205509802 6257270829146002730 6148914691236517205 6580509827235400362 6148914691236517205 6148914691236517205 6148938880492328266 5452357994682865066 6148914691236517205 629216826306000...
output:
-20044
result:
ok 1 number(s): "-20044"
Test #38:
score: 0
Accepted
time: 57ms
memory: 200660kb
input:
10032 15144086147069 1 16777215 2305843009212645376 8994006998464636 216172803584425999 8589934591 535597454457856 1152903946780410876 34358689792 35993621236777983 4503599627370495 70368744175616 4176387163824193532 1970316247048190 144678104609128447 18014402796322811 4095 35184371564671 865878776...
output:
7929
result:
ok 1 number(s): "7929"
Test #39:
score: 0
Accepted
time: 86ms
memory: 232968kb
input:
17574 384298371949958277 6148914691236517194 7686155081431165514 6148914691236517205 6147788659550229845 6148914691236517205 6173215362799457605 7686143364045646506 6004799503161011541 6148914691236517205 3839998824050602666 6172980068736127661 6148164102751693482 7590488051453088042 653374973955255...
output:
-248121
result:
ok 1 number(s): "-248121"
Test #40:
score: 0
Accepted
time: 189ms
memory: 274560kb
input:
43456 9218937706459979776 1152920954976862080 6917529575251509120 2305843009081573248 4611686018427387903 68719476735 1889260069453619197 71985026271479680 18014396363046784 8589934576 1152886322382241791 288230238712758272 8556380175 523953446911 4486007172894719 549755752192 8718898441360506880 14...
output:
-35108
result:
ok 1 number(s): "-35108"
Test #41:
score: 0
Accepted
time: 24ms
memory: 182296kb
input:
998 6148911736299017386 7734181760070931797 6148914691236517205 6148914691236517546 6148914782907227542 6148913958228776277 5380300353400294058 6148914691236517205 6148914690520690005 6136905092230892458 5920744026787172906 6148914691236517205 6533409601050203562 6148914691236517205 6533221858007143...
output:
-13822
result:
ok 1 number(s): "-13822"
Test #42:
score: 0
Accepted
time: 182ms
memory: 273460kb
input:
42817 288221580058689536 36028797018505151 422216759638022 1152586986771447807 576460215432577016 4611686017353875456 1156862703903375879 143842509192167168 9007198180997121 206159413248 4467575228396994560 4398046511103 7 281473904017407 138485671378026744 2047 2305702288368861183 45756667433509210...
output:
-34389
result:
ok 1 number(s): "-34389"
Test #43:
score: 0
Accepted
time: 116ms
memory: 254284kb
input:
26195 6148870710726666922 6290038473066457773 6148914691236517205 6148913958223178410 6148914691236517205 6148914691236517205 1915530856845708053 6148914782862136661 6533221309325104469 6244992216294795562 3122491378046981482 6148914691594429781 6149265800517997909 6148914691236343146 61504158911165...
output:
-371625
result:
ok 1 number(s): "-371625"