QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#127470 | #5603. Three Dice | batrr# | AC ✓ | 32ms | 3600kb | C++17 | 3.1kb | 2023-07-19 18:30:56 | 2023-07-19 18:30:58 |
Judging History
answer
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N = 300500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;
int sum(int a, int b) {
a += b;
if (a >= mod)
a -= mod;
return a;
}
int sub(int a, int b) {
a -= b;
if (a < 0)
a += mod;
return a;
}
int mult(int a, int b) {
return 1ll * a * b % mod;
}
int bp(int a, int b) {
int res = 1;
while (b) {
if (b & 1)
res = mult(res, a);
a = mult(a, a);
b >>= 1;
}
return res;
}
int inv(int x) {
return bp(x, mod - 2);
}
int n;
const int maxN = 1005;
string X[maxN];
bool bad[18][18];
char bck[18];
bool used[18];
int id[18];
int ans[18];
int cnt[3];
bool fnd = false;
void rec(int v) {
if (v == 18) {
fnd = true;
for (int z = 0; z < 18; z++) ans[z] = id[z];
return;
}
for (int r = 0; r < 3; r++) {
if (cnt[r] == 6) continue;
bool can = true;
for (int z = 0; z < v; z++) {
if (id[z] == r && bad[v][z]) {
can = false;
break;
}
}
if (can) {
cnt[r]++;
id[v] = r;
rec(v + 1);
cnt[r]--;
}
}
}
void solve() {
cin >> n;
map<char,int> s;
int sz = 0;
for (int i = 0; i < n; i++) {
cin >> X[i];
for (auto& it : X[i]) {
if (!s.count(it)) {
s[it] = sz;
sz++;
}
}
}
if (s.size() > 18) {
cout << 0;
return ;
}
for (char x = 'a'; x <= 'z'; x++) {
if (sz < 18 && !s.count(x)) {
s[x] = sz;
sz++;
}
}
for (int i = 0; i < n; i++) {
for (int a = 0; a < 3; a++) {
for (int b = a + 1; b < 3; b++) {
bad[s[X[i][a]]][s[X[i][b]]] = true;
bad[s[X[i][b]]][s[X[i][a]]] = true;
// cout << " HI " << s[X[i][a]] << " " << s[X[i][b]] << endl;
}
}
}
for (int i = 0; i < 18; i++) {
if (bad[i][i]) {
cout << 0;
return ;
}
}
for (auto& it : s) {
bck[it.second] = it.first;
}
rec(0);
if (!fnd) {
cout << 0 << '\n';
}
else {
vector<vector<char>> ANS(3);
for (int t = 0; t < 18; t++) {
ANS[ans[t]].emplace_back(bck[t]);
}
for (int p = 0; p < 3; p++) {
assert(ANS[p].size() == 6);
for (char& t : ANS[p]) cout << t;
if (p != 2) {
cout << " ";
}
}
}
}
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) {
// cout << "Case #" << i << endl;
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 32ms
memory: 3588kb
input:
3 lad fin sly
output:
dnymop aishjk lfbceg
result:
ok correct
Test #2:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
1 dad
output:
0
result:
ok impossible
Test #3:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
11 aft cog far irk kit yes tau rag own uke via
output:
torevd fgisun ackywb
result:
ok correct
Test #4:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
20 aah aal aas aba abo abs aby ace act add ado ads adz aff aft aga age ago aha aid
output:
0
result:
ok impossible
Test #5:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
23 abc acb bac bca cab cba abd adb bad bda dab dba acd adc cad cda dac dca fgh ijk lmn opq rst
output:
0
result:
ok impossible
Test #6:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
24 abc bcd cde def efg fgh ghi hij ijk jkl klm lmn mno nop opq pqr qrs rst stu tuv uvw vwx wxy xyz
output:
0
result:
ok impossible
Test #7:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
121 lax tog taj fun get jar fez own now gut gul ark fax new meg fen fog log lez gum kor leg not rug fug lag kit urn gal nam gar jew rex rin ant gam mun jam nil gem kir ilk jut ern man mon awn mig mix wag erg gor fig run nim raj fix elk nom wig gat nor jow fag jaw kaf rig fin kat rag mag won wog wan ...
output:
xgjnzk aoueiy ltfrwm
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
149 pic twa cub wag spa til two pyx pis tew vug cig pul vig pol tow tis sub pew sty eld gas pes guv bal dol lob sot sap cob ply tic taw wit bow lad gal cup cep pax lab bys sup psi pox ops tel dex veg lop vat uts ods ups wiz lit gox wud cad sod cud dev paw pac dow wig gul zax sob set lag lip doc bos ...
output:
cwslxv iauoye ptbgdz
result:
ok correct
Test #9:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
97 fub tav seg box tas ski bin six syn fas sag neb sot jog gab van vug zax ban fob ons ask zit jot zin jin fiz nob jut fez beg vet sox kos gib sit sat bun bot son ifs ens but fib ins bug big sen vig tab sex zig ben sin efs kas kob nos zek nab qat xis gob guv set its bag sun veg zag uns tis sty ska n...
output:
bvsjzq uaeoiy ftgxkn
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
150 jug nit hen ant imp men ply pam pah awn jig god pal pet gan put jet dol zag tap ted lip dah lez tad pom dom dig pul hup mod edh poh dow lop old wan hap wed gin tup paw tod wiz nil ton nom tan hun hin apt mop daw pol ump noh pew pot wap hid nut map lap gun tun nam gip won nag eng wad own zit mon ...
output:
gthmlw uieayo jnpdzq
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
259 bog ant gan urn eng pit pig dam bid nod dap rib pul ens bot dim fur ops fad ugh fag bod hes lib she spy rep rum ash mug lin mig tan het rif sop pur gap bet pal mud big dah bit gun fro arm rub dib rap fed oms bas alb aft lip mol ins fas gum sob mod end ref sib dip arf mos ems hut nor ifs bra bud ...
output:
gtrdls oaueiy bnpmfh
result:
ok correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
260 bog ant gan urn eng pit pig dam bid nod dap rib pul ens bot dim fur ops fad ugh fag bod hes lib she spy rep rum ash mug lin mig tan het rif sop pur gap bet pal mud big dah bit gun fro arm rub dib rap fed oms bas alb aft lip mol ins fas gum sob mod end ref sib dip arf mos ems hut nor ifs bra bud ...
output:
0
result:
ok impossible
Test #13:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
1000 lgk nur wnm czr zuk une kob elg whc evn vlx woz mne gnp odp vkz xgz wdc npu hgk ged mwd hvx crn zcr vnp uze xbv brv bve okl bwg kno xgl oeh dec kvh nvp mpz hwc pbc ngk egz zpv zme ubx hgr xbo bgw brc rmd ubp xdc mxh hxc ebu vpz bgk dwg dve deu obp ohw ubx cxl edo zkv mbr mhe kbo zwu zwv gnk rhv...
output:
krwexp gumcov lnzbhd
result:
ok correct
Test #14:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
1000 sfp fbk nfw pfk qdk odm wgv kvt nwu mgw ucs gcq gvw kjd mda fod psu jto aqb pmg jba tja kdj usd fbs gqd ckq uod vco mkc djs sbj psj boj mws obu bau bgf qbn atu ntv ncf tof jts cmg tku fac dkf pfs pkf pqa nuw ojc svp otm sbf jwk mac vsp jbs jab dam omt udo jdo dsu joc auw tqs stf vgt cgu psu nup...
output:
pbwdtc fqmvuj sknoga
result:
ok correct
Test #15:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
1000 zjh lxd ftq xkb xkb oqt clf yce fjq ylc vqy ckv cke ovh fvx xdb qft dwl wjo kqv yei vfi tcf wjd tck ibz lck jcf qvz lzq ezx yvw jif tfq fxe vxz ekc tfi tiz ilz fjw yxj yvx hze dhe ibf ehk qzl kbc yvc oxb oil ijf vfw bkh lhd bhz dhe ybc ybh eyq dbw vxf xlz jwk zjx xkt ivd bio feh yjx ywb wkl xjd...
output:
hxqcwi jltbev zdfkoy
result:
ok correct
Test #16:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
1000 epn vpq xud gjq pxr hgt ezo gfs okk ukb rne iof eko flg yzz sck qwa zks bep uzh onw nfs ram tfp ctr ahw hrz fxx jgb izx gvs afn cii vbk wzx lkb sbl dga jpi nlv eon svd ioo zas bgh zdj elm aip kmf fta pmh vwr dsj gib yjv hgx ffx tyn crf yao vqm zbm bzu cay rkt jie pgn jms cpd jhd moz ymc ogc bve...
output:
0
result:
ok impossible
Test #17:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
1000 dzq bjt xwu pwy mba ekg pyo mqc nqo xrh ptt ayg ogv uga qop olo ohw rrm ekg vwq ilv emx lld ibf hpd ffn kei wop mxx quw zgn otm fcu ehs mnl evl lsk ocr bkg bpc zzx dcm jpx yak yuc qzz ktl ifb blo ktn qpm gtb nhp pao ugp qow hgt wqi axf rjz tnl rtm nyw bmx nfe rfu wru mpw wmm wzy jgm icz szd elb...
output:
0
result:
ok impossible
Test #18:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
1000 xzy hta jca xfn hjh ige fch cdl tzj gyg qsg ebt irn lys jgs bpe zog mkv ggb wos faa arr sqy cjc bbz wld rkx hdk gob ars frk ltj dzw ilg gxs ubm edf uur yfr fkv pma tek qqe tgn wwh low fit tzz txv yhq xix mnb ner jup nrl bim iwu rgh ohv mmn utv zil wqd vee ajh jwq eau rrh bdc zzm zfk ago bwi cwi...
output:
0
result:
ok impossible