QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61180 | #4828. Four Plus Four | JohnAlfnov | 0 | 442ms | 44520kb | C++14 | 2.2kb | 2022-11-11 10:30:37 | 2022-11-11 10:30:40 |
Judging History
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: 0
Wrong Answer
time: 442ms
memory: 44520kb
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 dows draw cero huic hurt
input:
keys 4 ados dows hurt huic draw ados dows draw 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 swordman password
result:
wrong answer query 3: read swordman but expected password