QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61181#4828. Four Plus FourJohnAlfnov0 489ms63532kbC++142.2kb2022-11-11 10:32:362022-11-11 10:32:37

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:32:37]
  • 评测
  • 测评结果:0
  • 用时:489ms
  • 内存:63532kb
  • [2022-11-11 10:32:36]
  • 提交

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][c]=f[c][a]=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];
			int w=max(f[A][B],f[B][A]);
			printf("%s\n",t1[w]+1);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 476ms
memory: 63532kb

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 thou

input:

keys
4
wrap pows
thou 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: 485ms
memory: 63416kb

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: 0
Wrong Answer
time: 489ms
memory: 63480kb

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 flow
kava kava kava

input:

keys
18
kava kava
kava kava
flow flaw
kava kava
kava kava
kava kava
fowl flow
flaw fowl
kava kava
flow fowl
kava kava
flaw flow
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
seafowls
aardvark
aardvark
aardvark
moorfowl
aardwolf
aardvark
moorfowl
aardvark
seafowls
aardvark
aardvark
aardvark
aardwolf
aardvark
aardvark

result:

wrong answer query 3: read seafowls but expected aardwolf