QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61185#4828. Four Plus FourJohnAlfnov0 512ms71924kbC++142.2kb2022-11-11 10:57:202022-11-11 10:57:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-11 10:57:22]
  • 评测
  • 测评结果:0
  • 用时:512ms
  • 内存:71924kb
  • [2022-11-11 10:57:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
char s0[100005][15],s1[100005][15],s2[100005][15];
char t1[100005][15],t2[100005][15];
int cnt[11144],tnc[11144];
vector<int>g[30005];
int deg[300005];
int vv[30005];
int f[4005][4005];
int wz[30005][3];
int main(){
	string florr;
	cin>>florr;
	int n;
	cin>>n;
	for(int i=1;i<=n;++i){
		if(florr[0]=='p')scanf("%s",s0[i]+1);
		else scanf("%s%s",s1[i]+1,s2[i]+1);
	}
	int n0,n1;
	cin>>n0;
	for(int i=1;i<=n0;++i)scanf("%s",t1[i]+1);
	cin>>n1;
	for(int i=1;i<=n1;++i)scanf("%s",t2[i]+1);
	for(int i=1;i<=n0;++i){
		for(int j=1;j<=8;++j)++cnt[t1[i][j]];
		for(int j=1;j<=n1;++j){
			int flag=1;
			for(int l=1;l<=4;++l){
				++tnc[t2[j][l]];
				if(tnc[t2[j][l]]>cnt[t2[j][l]]){
					flag=0;
					break;
				}
			}
			if(flag){
				g[i].emplace_back(j);
				++deg[j];
			}
			for(int l=1;l<=4;++l)tnc[t2[j][l]]=0;
		}
		for(int j=1;j<=8;++j)--cnt[t1[i][j]];
	}
	for(int i=1;i<=n0;++i)vv[i]=i;
	sort(vv+1,vv+n0+1,[&](int a,int b){
		return g[a].size()<g[b].size();
	});
	for(int x=1;x<=n0;++x){
		int i=vv[x];
		if(g[i].size()<3)continue;
		sort(g[i].begin(),g[i].end(),[&](int a,int b){
			return deg[a]<deg[b];
		});
		int flag=0,sz=g[i].size();
		for(int A=0;A<sz&&!flag;++A)for(int B=A;B<sz&&!flag;++B){
			int a=g[i][A],b=g[i][B];
			if(f[a][b])continue;
			for(int C=B;C<sz;++C){
				int c=g[i][C];
				if(f[a][c]||f[b][c])continue;
				wz[i][0]=a,wz[i][1]=b,wz[i][2]=c;
				f[a][b]=f[b][a]=f[b][c]=f[c][b]=f[c][a]=f[a][c]=i;
				flag=1;
				break;
			}
		}
	//	assert(flag);
	}
	map<string,int>m1,m2;
	for(int i=1;i<=n0;++i){
		string st;
		for(int j=1;j<=8;++j){
			st+=t1[i][j];
		}
		m1[st]=i;
	}
	for(int i=1;i<=n1;++i){
		string st;
		for(int j=1;j<=4;++j){
			st+=t2[i][j];
		}
		m2[st]=i;
	}
	if(florr[0]=='p'){
		for(int i=1;i<=n;++i){
			string st;
			for(int j=1;j<=8;++j)st+=s0[i][j];
			int w=m1[st];
			printf("%s %s %s\n",t2[wz[w][0]]+1,t2[wz[w][1]]+1,t2[wz[w][2]]+1);
		}
	}else{
		for(int i=1;i<=n;++i){
			string st1,st2;
			for(int j=1;j<=4;++j)st1+=s1[i][j],st2+=s2[i][j];
			int A=m2[st1],B=m2[st2];
			printf("%s\n",t1[f[A][B]]+1);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 487ms
memory: 70284kb

input:

password
2
password
couthier
28558
aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatises abattoir abbacies abbatial abbesses abdicate abdomens abdomina abducens abducent abducing abducted abductee abductor abelmosk aberrant abetment abettals abet...

output:

wrap pows sows
huic hurt uric

input:

keys
4
wrap pows
uric hurt
sows wrap
pows sows
28558
aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatises abattoir abbacies abbatial abbesses abdicate abdomens abdomina abducens abducent abducing abducted abductee abductor abelmosk aberrant abet...

output:

password
couthier
password
password

result:

ok OK

Test #2:

score: 100
Accepted
time: 475ms
memory: 70404kb

input:

password
1
quirkier
28558
aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatises abattoir abbacies abbatial abbesses abdicate abdomens abdomina abducens abducent abducing abducted abductee abductor abelmosk aberrant abetment abettals abetters abet...

output:

keir keir keir

input:

keys
1
keir keir
28558
aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatises abattoir abbacies abbatial abbesses abdicate abdomens abdomina abducens abducent abducing abducted abductee abductor abelmosk aberrant abetment abettals abetters abettin...

output:

quirkier

result:

ok OK

Test #3:

score: 100
Accepted
time: 500ms
memory: 70084kb

input:

password
3
aardvark
aardwolf
aardvark
28558
aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatises abattoir abbacies abbatial abbesses abdicate abdomens abdomina abducens abducent abducing abducted abductee abductor abelmosk aberrant abetment abet...

output:

kava kava kava
flaw fowl fado
kava kava kava

input:

keys
18
kava kava
kava kava
fado flaw
kava kava
kava kava
kava kava
fowl fado
flaw fowl
kava kava
fado fowl
kava kava
flaw fado
kava kava
kava kava
kava kava
fowl flaw
kava kava
kava kava
28558
aardvark aardwolf aasvogel abacuses abalones abampere abandons abapical abasedly abashing abatable abatise...

output:

aardvark
aardvark
aardwolf
aardvark
aardvark
aardvark
aardwolf
aardwolf
aardvark
aardwolf
aardvark
aardwolf
aardvark
aardvark
aardvark
aardwolf
aardvark
aardvark

result:

ok OK

Test #4:

score: 100
Accepted
time: 512ms
memory: 71924kb

input:

password
10000
aardvark
aardwolf
aasvogel
abacuses
abalones
abampere
abandons
abapical
abasedly
abashing
abatable
abatises
abattoir
abbacies
abbatial
abbesses
abdicate
abdomens
abdomina
abducens
abducent
abducing
abducted
abductee
abductor
abelmosk
aberrant
abetment
abettals
abetters
abetting
abetto...

output:

kava kava kava
flaw fowl fado
vasa goal vole
cube sabs scab
anoa snob abas
beep barm ramp
naan bond bods
blip paca clip
abys dyes yald
agha bags gibs
baba abbe babe
sibs baas bait
bott batt obia
abba sibb bice
abba alba baal
ebbs ebbs ebbs
bice data bait
bond bema mods
bond bima anoa
daub cube cuds
...

input:

keys
60000
clag glen
feel fehs
flic lift
azon zags
nidi code
foin grog
turk kerb
kind desk
adze drib
kois kefs
grim germ
moos mods
offs fall
alif alif
birk tsks
duad deed
coda load
onus cone
hade shes
flap fays
obit both
cels lacs
next tend
grog cols
fado fico
fail fiar
errs diss
fork fork
viga viga...

output:

cleaning
fleeches
felsitic
agonizes
coincide
frogging
bruskest
dinkiest
arabized
forkiest
armigero
endosome
falloffs
fallible
briskest
denudate
canoodle
conquers
dashiest
flypasts
bioethic
carrells
dextrins
cloggers
fricando
filarees
dressier
formwork
aviating
dogeship
arousals
celestas
buttocks
epi...

result:

ok OK

Test #5:

score: 0
Wrong Answer on the first run

input:

password
10000
fucoidal
fuddling
fuehrers
fuellers
fuelling
fuelwood
fugacity
fuggiest
fugitive
fugleman
fuglemen
fuguists
fulcrums
fulfills
fullback
fullered
fullface
fullness
fulmined
fulmines
fulminic
fumarase
fumarate
fumarole
fumatory
fumblers
fumbling
fumeless
fumelike
fumettes
fumigant
fumiga...

output:

cuif fado coif
gulf gulf gulf
fehs furs rush
full furl feel
gulf fill fuel
woof foul wold
cagy yuga yuga
fugs gift gigs
five five five
fume flag geum
fume gulf glum
fugu fugs fuss
curf culm urus
lull luff full
fuck bulk flak
full dull feud
cuff luff calf
full fuss fuel
fume fund mild
fume slum fuel
...

input:


output:


result:

wrong answer hyla didn't appear in nuzzling