QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#259615#5603. Three DicequsolAC ✓1ms3500kbC++141.6kb2023-11-21 06:58:522023-11-21 06:58:52

Judging History

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

  • [2023-11-21 06:58:52]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3500kb
  • [2023-11-21 06:58:52]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vl>;
using pll = pair<ll,ll>;
using vpll = vector<pll>;
using vs = vector<string>;
const ll oo = 0x3f3f3f3f3f3f3f3fLL;
const ld eps = 1e-9;

#define sz(c) ll((c).size())
#define pb(c) push_back(c)
#define all(c) begin(c),end(c)
#define mp make_pair
#define xx first
#define yy second
#define FOR(i,a,b) for (ll i=(a); i<(b); i++)
#define FORD(i,a,b) for (ll i=ll(b)-1; i>=(a); i--)
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

ll adj[18][18] = {0};
map<char,ll> inds;

ll getInd(char a){
	if(inds.find(a) == inds.end()) inds[a] = sz(inds);
	return inds[a];
}

ll solve(ll curr, vl &cols, vl &rem){
	if(curr == 18) return 1;
	
	FOR(i,0,3){
		if(rem[i] == 0) continue;
		ll pos=1;
		FOR(j,0,curr) if(adj[curr][j] && cols[j] == i) pos = 0;
		if(!pos) continue;
		
		cols[curr] = i; rem[i]--;
		if(solve(curr+1, cols, rem)) return 1;
		rem[i]++;
	}
	
	return 0;
}

int main() { cin.sync_with_stdio(0); cin.tie(0);
	ll n; cin >> n;
	
	FOR(i,0,n){
		string a; cin >> a;
		
		FOR(j,1,3) FOR(k,0,j){
			if(a[j] == a[k] || getInd(a[j]) > 17 || getInd(a[k]) > 17){
				cout << "0\n";
				return 0;
			}
			adj[getInd(a[k])][getInd(a[j])] = 1;
			adj[getInd(a[j])][getInd(a[k])] = 1;
		}
	}
	
	if(sz(inds) != 18) FOR(i,'a','z'+1) if(getInd(i) == 17) break;
	
	vl cols(18);
	vl rem(3,6);
	
	if(!solve(0, cols, rem)) cout << "0\n";
	else{
		vvl die(3);
		for(auto [k,v] : inds){
			die[cols[v]].pb(k);
		}
		
		FOR(i,0,3){
			FOR(j,0,6) cout << (char) die[i][j];
			cout << " ";
		}
		cout << endl;
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3456kb

input:

3
lad
fin
sly

output:

abceis fghjkl dmnopy 

result:

ok correct

Test #2:

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

input:

1
dad

output:

0

result:

ok impossible

Test #3:

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

input:

11
aft
cog
far
irk
kit
yes
tau
rag
own
uke
via

output:

fgiuwy abdkos cenrtv 

result:

ok correct

Test #4:

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

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: 3432kb

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: 3432kb

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: 1ms
memory: 3436kb

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:

aeiouy flmrtw gjknxz 

result:

ok correct

Test #8:

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

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:

aeiouy bdgptz clsvwx 

result:

ok correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 3432kb

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:

aeiouy fgkntx bjqsvz 

result:

ok correct

Test #10:

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

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:

aeiouy djnpqz ghlmtw 

result:

ok correct

Test #11:

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

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:

aeiouy bfhmnp dglrst 

result:

ok correct

Test #12:

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

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: 3376kb

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:

cgmouv bdhlnz ekprwx 

result:

ok correct

Test #14:

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

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:

fjmquv agknos bcdptw 

result:

ok correct

Test #15:

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

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:

bejltv dfkoyz chiqwx 

result:

ok correct

Test #16:

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

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: 0ms
memory: 3380kb

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: 3396kb

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