QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18761#1653. CodenamesxiaojifangAC ✓3929ms929048kbC++203.6kb2022-01-26 14:53:142022-05-06 02:26:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 02:26:14]
  • 评测
  • 测评结果:AC
  • 用时:3929ms
  • 内存:929048kb
  • [2022-01-26 14:53:14]
  • 提交

answer

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
//#include <atcoder/all>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1e18;
//const ll mod = 1000000007;
int L;
int Q;
int N; 
ll dpA[1<<25];
ll dpB[1<<25];
ll val[1<<25];
string S[100000];
int query[1<<25];
 
namespace REC1 {
ll calc(string X) {
    ll ret = 0;
    int sup = 0, fix = 0;
    REP (i, X.size()) {
	if (X[i] == '1') sup |= 1<<i;
	else if (X[i] == '?') fix |= 1<<i;
    }
    for (int sub=sup; ; sub=sup&(sub-1)) {
	if (__builtin_popcount(sup ^ sub) & 1) {
	    ret -= dpA[fix | sub];
	} else {
	    ret += dpA[fix | sub];
	}
	if (sub == 0) break;
    }
    return ret;
}
};
 
namespace REC0 {
ll calc(string X) {
    ll ret = 0;
    int sup = 0, fix = 0;
    REP (i, X.size()) {
	if (X[i] == '0') sup |= 1<<i;
	else if (X[i] == '1') fix |= 1<<i;
    }
    for (int sub=sup; ; sub=sup&(sub-1)) {
	if (__builtin_popcount(sub) & 1) {
	    ret -= dpB[fix | sub];
	} else {
	    ret += dpB[fix | sub];
	}
	if (sub == 0) break;
    }
    return ret;
}
};
 
namespace RECQ {
ll calc(string X) {
    ll ret = 0;
    int sup = 0, fix = 0;
    REP (i, X.size()) {
	if (X[i] == '?') sup |= 1<<i;
	else if (X[i] == '1') fix |= 1<<i;
    }
    for (int sub=sup; ; sub=sup&(sub-1)) {
	ret += val[fix | sub];
	if (sub == 0) break;
    }
    return ret;
}
};

ll calc(string X) {
	int zero = count(X.begin(), X.end(), '0');
	int one = count(X.begin(), X.end(), '1');
	ll ans;
	if (zero <= 8) {
	    ans = REC0::calc(X);
	} else if (one <= 8) {
	    ans = REC1::calc(X);
	} else {
	    ans = RECQ::calc(X);
	}
    return ans;
}

string T;

void solve() {
    T.clear();
    for(int i = 0; i < 5; i++) {
        string A;
        cin >> A;
        T += A;
    }
    string X = string(L, '?');
    int onenum = 0;
    for(int i = 0; i < L; i++) {
        if(T[i] == 'r') {
            onenum++;
            X[i] = '1';
        }
        if(T[i] == 'b' or T[i] == 'n' or T[i] == 'x') {
            X[i] = '0';
        }
    }
    if(calc(X) == 0) {
        cout << "IMPOSSIBLE" << endl;
        return;
    }
    for(int i = 0; i < L; i++) {
        if(X[i] != '?') continue;
        X[i] = '0';
        if(calc(X) == 0) {
            X[i] = '1';
        }
    }
    int bits = 0;
    for(int i = 0; i < L; i++) {
        if(X[i] == '1') bits |= (1 << i);
    }
    cout << S[query[bits]] << " " << onenum << endl;
}
 
void MAIN() {
    L = 25;
    for(int i = 0; i < (1 << L); i++) {
        val[i] = 0;
        query[i] = -1;
    }
    cin >> N;
    for(int i = 0; i < N; i++) {
        int bits = 0;
        cin >> S[i];
        for(auto c : S[i]) {
            if(c == 'z') continue;
            int j = (int)(c - 'a');
            bits |= (1 << j);
            if(query[bits] != -1) continue;
            val[bits] = 1;
            query[bits] = i;
        }
    }
 
    REP (s, 1<<L) {
	dpA[s] = dpB[s] = val[s];
    }
 
    REP (t, L) REP (s, 1<<L) if (~s>>t&1) {
	dpA[s|(1<<t)] += dpA[s];
	dpB[s] += dpB[s|(1<<t)];
    }
    int Q;
    cin >> Q;
    for(int q = 0; q < Q; q++) solve();
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    MAIN();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1710ms
memory: 924144kb

input:

3
actor
cheat
zeta
1
rBBnR
NRnbB
nRRnR
NRxBr
nBRbB

output:

zeta 2

result:

ok OK

Test #2:

score: 0
Accepted
time: 3632ms
memory: 928976kb

input:

100000
elqhnetajrxtexqelrfc
mkvfckyvpdcyjvojoidq
cwvgawpgvrjcjpcepmgq
chmwujlinjcintvlkvkr
pnyhiaxrkuyhuahepxng
wcrrkrwymclhhjeacypg
txcxpaqkirtcxqyydiro
hxnpoyeycpqxdgempgctp
angigamneabnhgjdbeely
eaacjfumbqnngejwqqgp
ufffbsppvgbjjgvhbdvi
srkdpatxsanakxtrhprg
jbwyapjyspjrqfupoasc
evleiposkxmnpxdymo...

output:

bqewjwokxexykquvnqjr 7
xsxwnassbnoqudylrbqt 7
xskpccfqcfwpiuplpbgn 6
jwqyroxkxxikwtgigeif 7
hvmfonqfxsmxsraejgni 6
toiloopiloxgrcxlixck 7
easjvymeluoaswalvimd 7
iihfdlfvrudawdqofliy 6
eeuvpuqddiuefkypxihj 7
gpgtpubjsmtfpatgaatv 6
mwhdrnceawhlcbynwsrt 5
ldvuoxddqoyedhtyatyz 7
ohswwwtoxvvwyntwnbcuxk 7...

result:

ok OK

Test #3:

score: 0
Accepted
time: 3929ms
memory: 928836kb

input:

100000
ktglptogbrjtkojqbo
pnrwcppddjkxiumbw
itkfkaaskgbbwigj
cisexgqsmohonvdl
ltxuruvqhmyfstwam
rmyqktnfiqigpyrb
iqcjwycfyaewlqas
ygvpyuxgxnxylqod
llrppayuqlncfblt
kjqfemveotvbsjkd
kiehemetflndmikb
atjxiumicxkktygf
ftxprhominotnqmmg
uqbdtupbxocmcbkv
eesymnhkoltcmlod
aueucienoipohneoo
modcffaedqqlafn...

output:

qajvjukoyfxmujjp 7
ldhkkvdckdjxjrcn 7
vmqtptfvkkwbtasy 4
pmyjskksmaoqrlvi 7
yxeptnnptpvuuwdk 7
uxglsxlvwktoqueh 7
vsfirgdguvvndhyw 7
mjeuscvojyfhmxyr 7
gbdtwwdojjsfcxbmy 7
lxvidkbvmymetqgft 7
fmyuethwumwinhev 7
bvjnfeqejatbfmhy 2
qlrrvlpihstnjqqxp 7
ntwjhtqvldwiirxf 7
cqytrftyvocwncfx 7
sxcaadgwyixw...

result:

ok OK

Test #4:

score: 0
Accepted
time: 3116ms
memory: 929048kb

input:

100000
srdfpsajcabsdyypblnmkydkblxjcq
yyvwesfhwjjpfrbfsbkqnqanrornkm
wcaolxfulvvduvxxamfqoqogwofvwi
ayjkyafapxaljgrllagfybpapofoxq
ytqmjsfiqmhevvjixbhygmjnemxljr
msiegrgwicnexrunhibybgrwghuemq
dstffbynonlnlpdtltffwgbfttxlfz
kbbeahfbcfqqbbeuxojtroiutkcftg
kqofpvmecbjitvvuxbskfpaoojxjqy
tyccmmehficqth...

output:

ptlxsbtydkqavrtycquchoadrltroo 6
nqrsenmgkphwmkwampnlkwpghlmghu 3
cxjdrqamrndyrcwjayjopkkwjllcwb 6
qaaxwvjlqwjgeoashawfkmmmjktnir 5
cpyxkypmcvnygpoxsmqlcttdrkpnqu 6
uekexwurdukxergjfmpxcpmjaapexi 6
koeahkaooqyiufqfaexbfohihqwbxj 5
bxyjbdtvhwjisbivybpayuweflixyg 6
voggsddvrwlqujxnquqfqoysfuuryi 2
ial...

result:

ok OK

Test #5:

score: 0
Accepted
time: 2889ms
memory: 929044kb

input:

100000
dolfdepkwgaulpokkwwk
lfwefbbryleomriwuajt
klvbivnfojughhfkbgds
fnhrufroxfqutjqnggxs
yqhmjhmbxiklybjusmxc
lfpeefrjxrpldnfscvxt
ftdlobogvvfgaiynnysm
ehevewoqaeyuymtbjdqk
fccssxdhicmvsrxygwxd
yqckkixyyukgkxnwxcwb
hcvqrtdvrcjxobovnbwy
paxuatcocovsupobfbir
eswjnywsnevrjyefngno
wpcmcwjvbwoppkaehfbq...

output:

cdnwhisxvskopikxcgeu 2
rnststnyjcdvoqoniclm 6
pcujupjystvpnjgdnhme 5
ooeicfeixbexhqflbjyu 4
ywbdtoqxfqyxfxglnhyi 5
ffqsaxqnurbdrpmwhmmo 6
rdxfbxfcklfrtpoumtvy 4
hlldcoulbwmaapvvhwlf 6
vsyqssqbwskgljswesuh 5
iprhkiedefhyupoallgb 3
shrmwncbbusmavlpnvjt 6
xuwuvrmaygtxfoftrjtqx 5
obqhqubxtumeybyfnitp 4
...

result:

ok OK

Test #6:

score: 0
Accepted
time: 3896ms
memory: 924216kb

input:

100000
sycrxchoiqpbn
hbgwwtcmtmsoln
gfkoekgbudwin
opsvawubfctvl
nkbpbldtpeudj
gawbjoptpqdan
dcvkyxifsvfal
vfjnctrfkrqyi
ejotlcalhjsuq
ebyigyulkepoc
gbjrgshldchbn
mdmgcixhajqsw
vssbkddvsevvm
lejlihhuajsdq
wxbrpfwkgwmrq
cxjonbjxvshql
vjxpyvjwktlhft
pqkuqhagjboke
eowkmghpwjjgnd
aywvehjkhedxr
iwtqxiwvko...

output:

bjlgeijtydgbwt 7
xoryobintvytk 7
sgyotkbffjjxc 7
wnkbtyvkflamxn 7
srnwccoitdusvkofl 7
pnklhhtqyskmc 7
ejttvqyebqhew 4
vwymaxpwpnhgn 7
nvfwutyvhplpx 7
uokrduduawfpn 7
rnneqfeelrsqx 7
xsisfqxewsphu 7
jninuyysoftajw 6
vxhiymfabonaku 7
iwawhsgfusape 7
vncyvkkouwlsx 7
jrmxccoulvhyb 7
goxtncueugcgw 7
rimc...

result:

ok OK

Test #7:

score: 0
Accepted
time: 2683ms
memory: 928980kb

input:

100000
drjfnddxclqyxbchqyrtqaew
vyciggoxoytxcakybpgusmke
qenyjdjxcvuvrxwyficpjxvbc
lluukkdjprgoyleryldiphrs
aitvhsjjvvixxdaxuwxghtxl
kxyfnecpxlevsuyjhivjuncrl
bfipfspsththixxmbtuwlckrk
ywojxvofvpgguonqaarlpwjdo
uwpteeknbgnhgettvmvtcuds
ixbquqfibdsxigxkxyeditvrn
ytkwirsuvmfexywccjmhtotg
adxhsaqglerfr...

output:

mbsmbecqoypanatwyiqcbmax 4
uujupnogfriesgveelpcenvm 4
sonuxdeholmudewwjhlocmvu 4
rnuixdflnomlawtylfixvakj 5
poaoubjfsdelbfxcgmaxmjrv 5
hxrhvhsxhgqenylecvgpceewf 4
tpsmlhxgadvtyjpoxnqgrvgu 5
leaammgwgvdhxbaptwdddofy 5
xyvjhqiqgekqgwqcuvcixtgo 5
eclvgbacvjlmhxmljvlrrbgw 4
tislcksedmocwqcqixyxwxsr 5
am...

result:

ok OK

Test #8:

score: 0
Accepted
time: 2290ms
memory: 924356kb

input:

100000
fqcjarqfl
cljuaphxe
liimhwhvr
mxqmsnilp
mndapkfxid
maokbecdr
knoeifvfc
rmkgkrdsi
hfrntlxuw
jagpdtrpex
qgvqwrohcb
dyudsjskt
xfyrtwffv
nlhmhehay
peknoaacba
ooqavcjkd
bpbncuqjs
drlyhwacu
ihkvwajrx
dhkhslhrj
xkrfcieij
nsvtvjlsg
gosydfthp
obpcogedn
yshibnteg
hoalyohne
gmjobrytf
sbhjedabt
puhahyvwv...

output:

irqraqpxl 3
guslayupn 2
knpvvicwo 3
axianumlj 3
gwcbekstji 3
fqkiulacj 3
mfhyhvnws 3
hncuitdsx 3
debcrxmag 3
vvfmwpngk 3
lpuujpwes 3
bplprvdef 3
exhhjgnvq 3
chtwrjsfk 3
iuxkufila 3
pkafltfaw 3
lpfrhmrmu 3
recwewafl 3
upxknyufq 3
cxsfndnxh 3
mxwsilcxy 3
cxgtvvbey 3
qsclttadw 3
ovdfxxgkm 3
cjrjnxrjd 3...

result:

ok OK

Test #9:

score: 0
Accepted
time: 2520ms
memory: 924256kb

input:

100000
qrbx
gmhv
yobm
xfgl
iwkd
ugiq
hvnibj
aswp
lbej
ygfxn
koyx
rtogf
xbfm
lguqc
xvrf
vyjr
pwyo
rbmtd
xuoe
gkfu
vyuh
wuic
nhur
labq
vgdxs
xuoj
hrjs
cgphs
lkdi
lqgb
unjha
canb
cmtr
cxat
vmhq
juod
pnxm
bxtjtf
brne
tjvo
ucxr
nqegx
ojwa
xsuq
sqab
eutb
cvpe
trsq
ayedi
wljd
oqfb
qlsw
yqcpt
ehwo
dpqe
sldn...

output:

fplb 4
jibw 4
jbki 4
dlhy 4
lvxh 4
mwlx 4
dtic 4
mhqy 3
lkdi 4
ohay 4
ehdy 3
fwmk 4
yhok 4
wlnj 4
cgfq 4
vbcd 4
aqlgz 4
sabu 4
yvmb 4
ptxv 4
ulkx 4
udly 4
gbmlz 4
mpijm 4
ptyg 4
bgltq 4
ypnb 4
iaen 4
xmcu 4
gbrm 4
agxr 4
hdle 4
fscu 4
mxus 4
ducv 4
usfw 4
daere 4
otju 4
nmwh 4
wicl 4
omjn 4
gfiy 4
s...

result:

ok OK

Test #10:

score: 0
Accepted
time: 3653ms
memory: 924208kb

input:

100000
fvkxyvoemo
faibbosqw
fixtifclg
fhkbghxvu
rvncsmygw
xvntvxgmi
fsvjflqga
eoihuvckss
onvdpmrwg
yllugptkd
mobejpeva
adfufyrkqg
atjdjtuick
efjvancqr
ypkktlggno
hwfkkfgqot
phcjyybya
lwpbtlxarw
wphyrbxet
gavkuuste
jkrwpdmnf
efymdftqi
hereuawto
muxngxpofa
kjljbhnhp
cpwydtxpr
lvqtqgxuf
yuibyttcx
xetua...

output:

lqejverya 7
jdebppahv 7
ppisdlfvn 7
bfaceuiyqk 7
rrifyowox 5
hramvfakq 7
fudkntfwc 7
ysxsncjvi 7
hnvfspkmc 7
salfonpquj 7
agyhxngic 7
dkapgimln 7
btsdnxyfow 7
nnedlwrocy 7
khhgmcnyi 7
dccjhexym 7
tcenggbfyv 7
pvssfnffhxw 7
xnfbtkonq 7
ypisxnemt 7
scqvuhjnw 7
exxdfevjy 7
oyhesmlkg 7
bbvdhgmbs 7
qkfhx...

result:

ok OK

Test #11:

score: 0
Accepted
time: 3837ms
memory: 928892kb

input:

100000
udeisirksumgpnkdptgx
obpbecioogooysbeomrh
fvacddwxyltvckkxaaro
aykrklkggaioudikoflx
mdlurjsqedylpktcteuh
yrtbckodycctknntbcsa
tmktmhkukpavwfdwbfcg
ifqyiftpqygxqxsfyptr
rhuxxhjktbppsxdrwkfn
yffeakwyejswpfpnkpbu
lbvtdorrnebdydniurbh
xgkokxjyquttihnkxkrwm
vhssnwppqayfhuqlnciky
jbbwsctbeeutbswvfr...

output:

saaasutqrxntisensprwi 7
aleexbawcvtroawbijcu 6
qhiwjssvxnvymwysyujw 7
msnncvilbupicdcpdolf 6
vuevspjfwpbuwqeancwka 7
ttdilslrjwmfomvvtdxnc 7
lrypjtrdaqyxhllpqxie 6
nirvwqehgntllawweray 7
uapsauvapqnoosdfqiuj 6
ivjpykbvyverisepjdmm 6
dvqjdyosrwhjdxmexceb 7
vncnblkirkcioegefqftu 7
rrdoqkdcfmtowdqtcftl...

result:

ok OK

Test #12:

score: 0
Accepted
time: 2262ms
memory: 924616kb

input:

10000
epoarwirgbseovyvm
inswqfprsjrsqxmv
duqyvuwrocjgnjf
mdltatwhdgyrren
hhjuejejlnhqvvscc
ahuqnjnuyjfqwgiop
fmirskawesoejmxsy
xoejtiaagjraxmlf
jpnpuejuasdpawrg
edhyfynkgamyeupw
edkltbnxyceteep
vfcuclfmglsaoiy
uylcbalcbwvndleguuu
hbhoixetoilismq
ykghcclpyjfjmmssjkl
jbmfxwkfhyliimq
xyggrngvkqsguipa
r...

output:

ivkrvuvvnvkhdipd 3
spqowxgyxkqcfhrb 3
xpcaxntjcbclawks 3
ikptobmtatfmfuhg 3
anubhyupxcnakmq 3
txkggpsthpqerevoo 3
mdeurmpkququxscy 3
vqcdcbovhjmvwirmgm 3
ujqamfjwrrvdrfnoykm 3
qhvuvwfqewtkycrc 3
txehggkdaraorop 3
fterrvmgekcvemq 3
mowanhhendkdgfip 3
averqrpjiwdncbt 3
tvpkxwsllqtjsrbro 2
fcsjyjbcbbur...

result:

ok OK

Test #13:

score: 0
Accepted
time: 2204ms
memory: 924212kb

input:

20000
nihhjixfk
balwnotjca
uhgeacgbn
vuljupyxuk
mqcxqqcgb
atohkruf
uwrvhscfx
vudywbla
xsbwkftg
wallmxeob
jbyebjmihhot
ihkrbpafi
xetnoqhd
tnytmpwlxgb
jnwnicrb
aiokxqjnry
jgkkhpvdxh
ptdpbbbjla
ufkeokip
vounpqjlsc
rblobimge
vyboqkbpry
wlicyqkm
phcerdjvy
roarpcpf
snowjsoxu
vjdtxgju
dygjunotkq
vebvekqy
l...

output:

ttgakfxu 3
egtekmiwljx 3
xgropahcb 3
ibitjxek 3
wtvhgkdec 3
sejisahmgsl 2
qdhpqjhuuw 3
nlfphbprxs 3
ngograqhr 3
imlssejg 3
yifoxhrcxii 3
ktqtuhfwd 3
jbyebjmihhot 1
udxinkar 3
poppojlboh 3
wallmxeob 3
jbyebjmihhot 2
njmeyuur 3
crkwqvidte 3
txkbhgxajx 3
emkrwbbacrc 3
pcwrttknu 3
rykofslhx 3
almahxxc 3...

result:

ok OK

Test #14:

score: 0
Accepted
time: 2026ms
memory: 924268kb

input:

10000
skskcjwksvswxwyclf
lcmmdhxrmgmwp
vgbyowxcjfxaa
riskdngidgtje
isillkwgmlhjz
pknbgepciagdueyewgr
torrbwhutmrjj
trnmcdyxnvkagz
ugamldvbxqgji
kdtodylsdhwa
cueclpecbccdsdon
tevofrrlfjvkdv
kmprlwjtyindoyq
fufeshokckktcqe
cvssdhocpqvw
uinepwahuajkrr
fpqtikyswrqd
mobsnsaqnjawux
ehllrajyqfldygnl
bjocky...

output:

riskdngidgtje 1
riskdngidgtje 1
jxobjvxmtfjrhw 1
riskdngidgtje 1
dhjbkisypsqwx 1
riskdngidgtje 1
skskcjwksvswxwyclf 1
wxcxhkbickinmig 1
dhjbkisypsqwx 1
riskdngidgtje 1
lcmmdhxrmgmwp 1
jxobjvxmtfjrhw 1
dhjbkisypsqwx 1
abwfbytqpecrqk 1
dhjbkisypsqwx 1
dhjbkisypsqwx 1
jxobjvxmtfjrhw 1
abwfbytqpecrqk 1
...

result:

ok OK