QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#61178#4828. Four Plus FourJohnAlfnov0 457ms46716kbC++142.2kb2022-11-11 10:28:092022-11-11 10:28:12

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:28:12]
  • 评测
  • 测评结果:0
  • 用时:457ms
  • 内存:46716kb
  • [2022-11-11 10:28:09]
  • 提交

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 i=1;i<=n0;++i){
		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;
}

详细

Test #1:

score: 100
Accepted
time: 438ms
memory: 46632kb

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:

ados orad orad
cero etch etui

input:

keys
4
ados orad
etui etch
orad ados
orad orad
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: 457ms
memory: 46716kb

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:

kier kier kier

input:

keys
1
kier kier
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: 437ms
memory: 46540kb

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:

arak arak arak
afar afar afar
arak arak arak

input:

keys
18
arak arak
arak arak
afar afar
arak arak
arak arak
arak arak
afar afar
afar afar
arak arak
afar afar
arak arak
afar afar
arak arak
arak arak
arak arak
afar afar
arak arak
arak arak
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: 0
Wrong Answer on the first run

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:

arak arak arak
afar afar afar
aals aals aals
abas abas abas
aals abas able
aper aper aper
abas abos abos
alba alba alba
aals abed abed
aahs aahs aahs
abba abba abba
abas abet abet
abri abri abri
abas abba abbe
abba alba alit
abbe abbe abbe
abed abet aced
abed abos ados
ambo ambo ambo
abed aced aced
...

input:


output:


result:

wrong answer anal didn't appear in diacidic