QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214098#3449. Pizza Problemsucup-team1209TL 16ms5072kbC++201.3kb2023-10-14 17:12:572023-10-14 17:12:57

Judging History

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

  • [2023-10-14 17:12:57]
  • 评测
  • 测评结果:TL
  • 用时:16ms
  • 内存:5072kb
  • [2023-10-14 17:12:57]
  • 提交

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;
}
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 i = 1;i <= cc;++i) {
		s[i] = gen() % 2;
	}
	for(;;) {
		int bad = 0;
		for(int i = 0;i < n;++i) {
			int c = 0;
			for(int x : a[i]) c += s[x];
			for(int x : b[i]) c += !s[x];
			if(c * 3 > a[i].size() + b[i].size()) {
				continue;
			}
			static std::vector<int> p; p.clear();
			for(int x : a[i]) if(!s[x]) p.push_back(x);
			for(int x : b[i]) if(s[x]) p.push_back(x);
			shuffle(p.begin(), p.end(), gen);
			for(int i = 0;(i + c) * 3 <= (int) a[i].size() + b[i].size();++i) {
				s[p[i]] ^= 1;
			}
			bad = 1;
		}
		if(!bad) break;
	}
	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: 4240kb

input:

1
4 +zucchini +mozzarella +mushrooms -artichoke

output:

zucchini
mozzarella
artichoke

result:

ok 

Test #2:

score: 0
Accepted
time: 1ms
memory: 4228kb

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: 9ms
memory: 4860kb

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: 9ms
memory: 4812kb

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: 16ms
memory: 4924kb

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
d
jc
zva
u
iybxturtnr
npk
ti
lu
exby
fsuwyg
q
zu
exfklxyic
hfpz
xty
...

result:

ok 

Test #6:

score: 0
Accepted
time: 15ms
memory: 4908kb

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
ubpvqfxyxwt
zlr
vocms
nbofz
hjnogqzspusqr
lt
wawoe
kim
yqm
uos
apmdptk
akbxb
jjve
dhaw
tby
yyzl
wi
op
gtyhwlrmvitgh
d
k
evr
jlcrvp
gecs
jets
uv
vcbc
yp
zffnrxu
twe
phs
sfuipbs
ynhzw...

result:

ok 

Test #7:

score: 0
Accepted
time: 13ms
memory: 5024kb

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:

jfy
ngm
nsdza
qa
khlmq
c
yh
h
yxqo
itcx
ku
ydl
u
o

result:

ok 

Test #8:

score: 0
Accepted
time: 11ms
memory: 5072kb

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:

hl
exsgs
j
lhkfbskgeg
zsryqneohbu
m
h
d
pdse
ofnis
ixbno
k
dr
kqtmsd
f
vaqcf
zgxs

result:

ok 

Test #9:

score: -100
Time Limit Exceeded

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:


result: