QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214126 | #3449. Pizza Problems | ucup-team1209 | AC ✓ | 57ms | 8364kb | C++20 | 1.9kb | 2023-10-14 17:20:03 | 2023-10-14 17:20:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std::ranges;
using std::cin, std::cout;
const int N = 10000;
std::vector<int> a[N], b[N];
std::map<std::string, int> map;
std::string li[N];
int s[N];
int cc;
std::mt19937 gen;
int get(std::string s) {
if(map.count(s)) return map[s];
li[++cc] = s;
return map[s] = cc;
}
std::vector<int> dl[N], l[N];
std::queue<int> Q;
int inq[N], cnt[N];
void flip(int x) {
s[x] ^= 1;
if(s[x]) {
for(int t : l[x]) {
cnt[t] += 1;
}
for(int t : dl[x]) {
cnt[t] -= 1;
if(cnt[t] * 3 <= a[t].size() + b[t].size() && !inq[t]) {
inq[t] = 1, Q.push(t);
}
}
} else {
for(int t : l[x]) {
cnt[t] -= 1;
if(cnt[t] * 3 <= a[t].size() + b[t].size() && !inq[t]) {
inq[t] = 1, Q.push(t);
}
}
for(int t : dl[x]) {
cnt[t] += 1;
}
}
}
int main() {
std::ios::sync_with_stdio(false), cin.tie(0);
int n; cin >> n;
for(int i = 0;i < n;++i) {
int m; cin >> m;
for(int j = 0;j < m;++j) {
std::string t; cin >> t;
if(t[0] == '+') {
t.erase(t.begin()), a[i].push_back(get(t));
} else {
t.erase(t.begin()), b[i].push_back(get(t));
}
}
for(int x : a[i]) l[x].push_back(i);
for(int x : b[i]) dl[x].push_back(i);
}
for(int i = 1;i <= cc;++i) {
s[i] = gen() % 2;
}
for(int i = 0;i < n;++i) {
for(int x : a[i]) cnt[i] += s[x];
for(int x : b[i]) cnt[i] += !s[x];
if(cnt[i] * 3 <= a[i].size() + b[i].size()) {
Q.push(i), inq[i] = 1;
}
}
for(;Q.size();) {
int i = Q.front(); Q.pop(); inq[i] = 0;
for(;cnt[i] * 3 <= (int) a[i].size() + b[i].size();) {
if(gen() % 2 && a[i].size() || !b[i].size()) {
int x = a[i][gen() % a[i].size()];
if(s[x]) continue;
flip(x);
} else {
int x = b[i][gen() % b[i].size()];
if(!s[x]) continue;
flip(x);
}
}
}
for(int i = 1;i <= cc;++i) if(s[i]) {
cout << li[i] << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5108kb
input:
1 4 +zucchini +mozzarella +mushrooms -artichoke
output:
mushrooms
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 4852kb
input:
3 3 +redbeans +soylentgreen -bluecheese 3 +redbeans -soylentgreen +bluecheese 3 -redbeans +soylentgreen +bluecheese
output:
redbeans soylentgreen bluecheese
result:
ok
Test #3:
score: 0
Accepted
time: 11ms
memory: 5948kb
input:
10000 3 +wy -lloggxqqheet -eljd 3 -zhyrg -f +dzs 3 +bw +qh +ybq 3 -f +hv -zqr 3 -kc -i -kptc 3 +hl +fiy -jez 3 +ir -qk -kml 3 -fnpxlbh +i +ide 3 +eogv +hjtngdw +jzcy 3 -dr +u -rfe 3 -htbqf +j +dk 3 +jez +gv +svwvy 3 -wvgtsbdjxpezuji -tjm -p 3 +yc -fdp +ir 3 -svwvy +gi -tjm 3 -yepw +dk -yhmc 3 -igssi...
output:
wy eljd zhyrg dzs qh ybq kc hl ir kml ide hjtngdw jzcy dr u htbqf j dk gv svwvy p gi yhmc ej vn civo nwq ts bm jb cdte rk kogao oa vg zs g rs yw eku ol qjae iagk fzdqg kqar olbw jife hoj wqm ucm hh ejr bwl zt jlihkarhvm ulfr t oybqd omlwnh sy berg mc ohwcpqrkti vl fbg vhnty poerjyr npihs y nnklu zsk...
result:
ok
Test #4:
score: 0
Accepted
time: 7ms
memory: 5700kb
input:
10000 3 +sjmwhyay -vg -tq 3 +bxwa +xdv +qca 3 -vye -emcomhp -ktsu 3 +sbdjr -rz -jj 3 -vuxo +qk +wgo 3 +bvnb -vud +co 3 +ai +dtjy -zf 3 +x -d -qca 3 +dkkpw -el +ak 3 +o +azr +layde 3 +w -rj +aedg 3 -qqvhp +n -bxwa 3 -kovijn -xt +uwj 3 +aedg -kvevzsd -jlh 3 -fob +u -dxhc 3 +emcomhp -sbi -dln 3 +quhe +...
output:
bxwa xdv ktsu qk bvnb vud co ai x d ak o layde aedg n xt uwj jlh u dxhc ze gu otobbin gm spzmvo mz utwqiqvy ic bu wrh qoq ds mwptbwkqhdmhip ldxhi winum ldnc f xfgkys aeai jn szl oz wgn fxt s gg hur fbax ebc hkpydtxrftwau e ul ajx npsapy pw wy zol vcqkusz j gvvyp pyauik xit guoi uxu nn lzexqr bxq aq ...
result:
ok
Test #5:
score: 0
Accepted
time: 12ms
memory: 5920kb
input:
10000 6 -f +stbqz -ogif +ri -coc -pamqj 6 +jmn -fww +wiloelaxsitepe -gy +lhtltwkaqlua -jf 6 +xo -woj -op +xe -qa -til 6 -p -xgqwfrn -hwh +e -cm +bx 6 -xe -zn +cl +c +lhl +r 6 +yu -qa -wqc -gy +xrevvejix -yspjg 6 -qhzgc -bcflacptz +nut -ufe +znycp -acz 6 -ny -vea -lkk +vdejahrftdf -qfrih -ibwp 6 -kna...
output:
stbqz ogif ri pamqj jmn wiloelaxsitepe gy lhtltwkaqlua jf xo woj p hwh e bx zn cl c r yu qhzgc znycp ibwp uk ij w fdp pvgu gt pupv dz phu joqy spqqvl zd rm bhier kupt gpgf qr dky dh pxc be yc re sjufcanvmyh qqognbnie hs yqdu v igpe aqq jc zva u iybxturtnr npk ti lu exby fsuwyg q zu exfklxyic hfpz xt...
result:
ok
Test #6:
score: 0
Accepted
time: 17ms
memory: 6012kb
input:
10000 6 +gj -dn +mjyt +edikb +ivdtx -mvb 6 -lbbc -c -gxq +oozajgvqgfdi +ozhk +mjyt 6 -lpupyxsfpa -gs +mjyt +exyq +dlhwqdor +ytaiv 6 +fwnnxu -dr +mjyt +qv -ejh -ptfo 6 +mjyt -co +kd +hgpkzof +g +ftlrax 6 -xtwdmh +jos -oajge +mjyt -zy -m 6 +zwzgstw +mjyt +fwnnxu -kuzi +zowg -pho 6 +kdc +weegfo -efa -p...
output:
mjyt ivdtx lbbc c oozajgvqgfdi ozhk exyq dr qv kd g oajge zwzgstw weegfo lxcnfqtcgkjz nk enbggnc wyj bjdvl pn dpnbw yl ob ubpvqfxyxwt zlr vocms nbofz hjnogqzspusqr lt wawoe kim yqm uos apmdptk akbxb jjve tby yyzl op gtyhwlrmvitgh d k evr jlcrvp gecs uv vcbc yp zffnrxu twe phs sfuipbs ynhzw vgp a jjq...
result:
ok
Test #7:
score: 0
Accepted
time: 14ms
memory: 6484kb
input:
10000 9 -hnxemecf +jfy -ax +d +olj +ngm -nsdza +bqy -ez 9 +olj +qa -nsdza +ngm +khlmq +yqn +jz -ax -ez 9 +jfy +khlmq +nsdza +c +yh -ax +ngm -h -ez 9 +ngm +qa +khlmq +ax +jfy -ez +jz +olj +c 9 +yh +olj -jfy +yxqo -jz -ax +khlmq -nsdza +c 9 +khlmq -itcx +c -jz -ngm -ez -nsdza -ax +ku 9 -ydl -nsdza +qa...
output:
hnxemecf jfy olj ngm nsdza qa khlmq yh ydl vi u o
result:
ok
Test #8:
score: 0
Accepted
time: 10ms
memory: 6180kb
input:
10000 9 -bkd +hl +a -exsgs +j +lhkfbskgeg -naj -vst +zsryqneohbu 9 -naj -m -h -hl +d -exsgs -vst -j -bkd 9 -x -nksgd -exsgs +j +bkd +zsryqneohbu -naj +d +lhkfbskgeg 9 -pdse -j +o -naj -x -exsgs +lhkfbskgeg +d -hl 9 -exsgs +zsryqneohbu +d +lhkfbskgeg -hl -bkd +a -naj +ofnis 9 -naj +vst -x +d +kv -exs...
output:
lhkfbskgeg vst m h d pdse o ixbno dr kqtmsd vaqcf zgxs
result:
ok
Test #9:
score: 0
Accepted
time: 5ms
memory: 5168kb
input:
1190 9 +nrpo -v +tv +fjxjvsozhkiqdj +ratpgn +kfh +zw +emnbcwq -wgljqjc 18 +pg -agf +drrcq +acwokozi -uscxb -hru +dexyfq +ulbja -ki -lf +tv -nbdsc -eynnlntm -hf +emnbcwq -fis -m +o 16 +pv -cfaheb -o -hru -fy +ykwgs +hv +ar +lawinp -g +tv -ruscna -mk +emnbcwq -y +t 23 +ay +emnbcwq +g +fjxjvsozhkiqdj +...
output:
tv fjxjvsozhkiqdj kfh zw emnbcwq wgljqjc pg drrcq acwokozi hru ulbja lf eynnlntm fis m fy ykwgs hv lawinp g ruscna mk ay wyesg blo ysm pj fmdbojtmd ijgbo kyu ptzh ht mc ylaud aijimhsr d gmycr jck dccho pgp jxqs vshfx f buqi chb gr osz nk ja ux lao mtst pxf qinm cmd mim ky gaxzt n h dtkd e qu fcmegch...
result:
ok
Test #10:
score: 0
Accepted
time: 15ms
memory: 6292kb
input:
4955 22 -tn +b -j -oks +bd +iow +wu -jvy +czc -ur -bdyaihjncfjp +ww -ydlq +il +zzsru +z -uz +knrzihbtbhs +v -am +vtwfkycknsuxnrw +joun 25 +jvy +defvhr -au +wo -bdyaihjncfjp +txb +tvoua +ukinvmj +rdmehqlt +s -prqupb +sf -zxf -tlkpvc -qna +w -cj -xd +us -hzwb +il -vlk -vkf -tjfulihl +zfsy 24 -tn -fpdn...
output:
bd jvy czc ur bdyaihjncfjp ww z am vtwfkycknsuxnrw au wo s prqupb tlkpvc qna w xd us fpdnto sw hc n a jm cfe cjpwkyvdrk hme pidiot dgwl lx an utqx gzg oo jij ux di yrevpod dlr zoh loytpo sh r rypab oay zzdzjuned hvqnjq vd bno idjptqpxgifm f bzkybok fh mt etdjn ssrd yj uhkaf h yiap ligln af lkyfakgx ...
result:
ok
Test #11:
score: 0
Accepted
time: 18ms
memory: 6228kb
input:
4280 28 -nmn -rsasayfz -jcudj +nabwxzdwkjip -m +ipuexauff +u -l -ekq +rgtadudiqf -h -d -idz -iknye -nfcg +egapgsj +sbyh +cry -q -cnm -cdocwq -hm +wxgi -p -bvf +tetgf -kt +obzq 26 +n +idz -bo -nfcg +bvf +xiir -rgtadudiqf -ipuexauff -jwbdsr -bakabjw -ul +fm -obzq -l -q +nabwxzdwkjip +hasndlpv -iknye +...
output:
nmn nabwxzdwkjip ipuexauff u h d idz nfcg cry cnm hm wxgi p bvf obzq jwbdsr hasndlpv gc olsbwuxu uuo suyqpurq jx ly rsvuyas xjom yy
result:
ok
Test #12:
score: 0
Accepted
time: 6ms
memory: 5300kb
input:
3580 8 +o +ks -wxm -kt +qpqimp -s -zkzqn +ms 8 +dll +d +ska -toq +osl -kgz +ea -bly 6 +ctgw +gpk -fmuaxm -ctbkshjzr +j +toq 8 +wok -hbn -jmhwvp +kziz +toq +n +r -kgz 8 -ahtu -poye +wxm +gpk +zoh +qpqimp +dll -ek 8 +qg +a +ut +w -bly -vu -kt +kz 6 +s -poye +o +zcu +uuz +yph 8 +ldfx +vu -xix -kgz +gg ...
output:
ks qpqimp dll ska toq osl ea gpk ctbkshjzr j wok n ek qg a w zcu uuz yph ldfx gg pdj t mt b hz azhqryg iv m cycscn gbhu llokw bpchytw cnfc mclk ivpcis xss jr od l jlj x ugvl lsb q h p
result:
ok
Test #13:
score: 0
Accepted
time: 7ms
memory: 5296kb
input:
1886 16 +jj -lb +oll +xrmuh +t +yieub +pk -pw -fm -wgxy -bmj -hdtip +iyc +qewee -my +hy 11 +fpxf +wgxy +nm +bjswp +xfvqiztisw +ewkry -sgvdmnsemngv +jlb -nwi +fm -zm 20 +lelpxsp -exk -wgxy +bsldgz -xxg +u -pk -ks +av +zj +pxfa +pphoeypz +zh +jj -rdtz +ir +mlbtopi +j +yw -ik 13 -slfe +optlh +xtsnssoyx...
output:
jj oll xrmuh t pk bmj hdtip fpxf nm bjswp xfvqiztisw ewkry zm lelpxsp bsldgz u zj pxfa zh rdtz mlbtopi ik optlh xtsnssoyxyizuhm hgnh mag osqt qcqqqu zi cu om wc qp llfatyx qmuqhocm hu wgr cb apa nemud vn skao krvbhu rxjmsxq a ua exj zgf vnmpse frn ppbh b ui qtku smdrth ibctey qtyc zv enc ime emziuzu...
result:
ok
Test #14:
score: 0
Accepted
time: 15ms
memory: 6048kb
input:
6192 13 -arta -lip -ggy -cgs +bjafk +kcii -ew +kx +ke +hlnk -gp +jasve +hi 16 -zxhqvcwu -hlnk +fgqr -bnx -bcfmwtd +gys -tabf +rp +bkit +kagixxc +lwd -cjnkrdtt +qh -qc -aw +yf 13 -k -ul +xg -udn -lpxg -xgz -kcii +fj -hoelxgx +qnohfxp -lip -hlnk -nxfvrxw 15 -sdan -uuq +hlnk +hpq -x +uyjicjc -sxg -vprv...
output:
ggy cgs bjafk kcii kx jasve hi fgqr gys rp bkit kagixxc qh qc yf ul xg fj qnohfxp nxfvrxw uuq uyjicjc sxg vprvfqaxjpkuwbe oyp eigf shb epn uwco jfwhp cnjd thd eka hudz lue gwof g rn bda ydisiwb dnt gpy ia jxrp sjoaq dcmo lcm gy vwn nt qqsipt whd phgj xvhe nj akyf orzxnco bpuic vqiic as tyxrr wj oiao...
result:
ok
Test #15:
score: 0
Accepted
time: 28ms
memory: 6844kb
input:
5972 23 +adl +nm -yr -peacw -chsvitx -ua -op +t +pnbdo -n -jt +pjhj +zz +h +fkcuc -xywwocm -k +obp -xom -xvxjfz +ymaz -rlabrmne -fil 23 -gep -u -gf -bv -rgdz -b -areiqquk +pro -lo +ai +ua +zk +adl +xl +gxdwl -oeci -rgn +zz -haxpa -ccz -q +fqtjji -ign 23 +iruv +pwf -yye -uxtq +zyjdg -bndlkp -jze -pea...
output:
adl nm yr chsvitx ua op pnbdo pjhj zz xom ymaz fil gep u gf rgdz b pro ai zk xl oeci fqtjji ign iruv pwf zyjdg jze gw ho r dkf ivg viqz myfaw jnncc ahp gper d wv jnw mlv kezrt gzsnvdm yla pxh i ern gj huuxnnqb v nkt hv vvobcf yfumij uoqhogmz qhqna ddaotla xb lu iem w egi cvppbabx fv o m en kc dj z c...
result:
ok
Test #16:
score: 0
Accepted
time: 13ms
memory: 6084kb
input:
8987 10 +sqhjcvx -ok -e -bclm -zpwn +f +ksui +wo +dhjzwyztoc +wogv 11 +d -kwb +vov +ujt -lxrxrvug +j -tc -aa -m +sqhjcvx -ok 7 +nx +jzr +jpwqfwfr -y +ttor -hbshn +ydvp 8 -kqrs -k +q -bjkz -jh +wo +b +l 9 +wo +x -jsbhxe +vmnv -qexo -bqz +yxh +bclm +ttor 11 -simikskrrlb +wlo +wlnrc -glzlyuxi -rx -rw +...
output:
bclm f ksui wo dhjzwyztoc wogv d vov ujt lxrxrvug nx jzr jpwqfwfr y ttor q bjkz b l x jsbhxe vmnv glzlyuxi rx a ulzun ky kc cc ioy fpy lka oo mmjctek itz pf sps sw bj jluguge zrqc i ud hjp tblnhbnlpy zgk ddbppc p ubbylzal na uojamhp jj u r ta
result:
ok
Test #17:
score: 0
Accepted
time: 29ms
memory: 7316kb
input:
9705 20 -a +lzz -k +os -g -hsh +pm -me -i -ecte +f -z -cr +x +nfm +ezhtojd +xjxbwyl -ub -gelfsarqnsg -ybb 21 +ub -k +f -g +gelfsarqnsg -z +km +l +ybb +wp -ecte -xjxbwyl -lzz +s -me -i +nfm -hsh +x +hm -a 23 +ecte +nfm +km -wp -mt -f +cr -z -a +ub -s -gm +x -i +ybb +me -g -bp +l -jric +q +pm +xjxbwyl...
output:
pm ecte f nfm xjxbwyl gelfsarqnsg km l wp bp jric q
result:
ok
Test #18:
score: 0
Accepted
time: 11ms
memory: 6244kb
input:
5224 14 +eq -sf -uzonmyey -erfke -d +bwzwlfgq -dq -mrcq +lyox +eoz -myyykog -wo -afl +tlks 16 -gw +bg +rno +jyw +cwhl -srjdcgvmu +qko -paw +xgwh -tlks +p -lyox -cavx -hgni -wqgatip -skwjsq 17 +puqhibpn +paw +vmyt +wo -xgwh +rsbn -b +o +abfg -uzonmyey +zbq +hgni -k -d -ql -us -ls 17 +tlks +dppsyge -m...
output:
eq d eoz myyykog wo afl tlks bg rno jyw cwhl paw xgwh p hgni puqhibpn rsbn abfg zbq us ls z fml se hv ey krjbs bzzeio ww bosjjdpec hs l kkm lsqr pkpcx onkeeb gjn qnijn sqwyh hrcu n skhhv f if u hyqdi e hynt idm iw r ybd hrnxytptnpl et pr c
result:
ok
Test #19:
score: 0
Accepted
time: 57ms
memory: 8364kb
input:
10000 30 -pd +upq -ac +bk -eq +hz -ats -px -qp +dp -bi +wcsq +chonikogqxcayuv +rku -lciy +fp +wnsbq -kwea -d -hys -cd +eimk +qad +hsbllellf +nyfqzyte +nwtyqx +c -gndmp -ixi -zfu 30 +kpjfgb +ybamq +w +px +dz -chonikogqxcayuv -hzqenih -sgzuuuzn -qo +rku -nl -gw +ll +nwtyqx +pb +jrh +nk -jvl -wyai -a +...
output:
upq eq hz qp dp wcsq rku lciy wnsbq d cd eimk hsbllellf nyfqzyte nwtyqx c gndmp kpjfgb qo nl gw jrh nk jvl wyai wucmlg s qe ol ay lqwx vhh djphb bu lq uimsi pv qeo iso qelgb tsofbqhuw vwyap xju p za lw ie dww oxuf vbeim ly y lk uaqma is lg eatf tsr sd cns ilyw tlt x izkba xo he ffvw zynixb nf dv ifw...
result:
ok