QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#18761 | #1653. Codenames | xiaojifang | AC ✓ | 3929ms | 929048kb | C++20 | 3.6kb | 2022-01-26 14:53:14 | 2022-05-06 02:26:14 |
Judging History
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