QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214126#3449. Pizza Problemsucup-team1209AC ✓57ms8364kbC++201.9kb2023-10-14 17:20:032023-10-14 17:20:03

Judging History

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

  • [2023-10-14 17:20:03]
  • 评测
  • 测评结果:AC
  • 用时:57ms
  • 内存:8364kb
  • [2023-10-14 17:20:03]
  • 提交

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';
	}
}

詳細信息

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