QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61173#4828. Four Plus FourJohnAlfnov0 459ms47328kbC++142.2kb2022-11-11 10:18:202022-11-11 10:18: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:18:22]
  • 评测
  • 测评结果:0
  • 用时:459ms
  • 内存:47328kb
  • [2022-11-11 10:18: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 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+1;B<sz&&!flag;++B){
			int a=g[i][A],b=g[i][B];
			if(f[a][b])continue;
			for(int C=B+1;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=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: 0
Wrong Answer
time: 459ms
memory: 47328kb

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 osar
cero etch etui

input:

keys
4
ados orad
etui etch
osar ados
orad osar
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:


couthier

password

result:

wrong answer query 1: read couthier but expected password