QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214098 | #3449. Pizza Problems | ucup-team1209 | TL | 16ms | 5072kb | C++20 | 1.3kb | 2023-10-14 17:12:57 | 2023-10-14 17:12:57 |
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;
}
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 +...