QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#308122 | #7340. Spoonerisms | ucup-team1303 | AC ✓ | 121ms | 279880kb | C++14 | 3.6kb | 2024-01-19 16:17:24 | 2024-01-19 16:17:25 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define mk make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
// mt19937 rnd(20070819);
// int randint(int l,int r){return rnd()%(r-l+1)+l;}
void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}
const int N=2e6+5;
int d[N][26],n,tot,root;
string str[N];
bool isp[N];
vector<int>pf[N],sf[N];
pair<int,int>pos[N];
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>str[i];
root=tot=1;
for(int i=1;i<=n;i++){
int p=root;pf[i].resize(str[i].size());
for(int j=0;j<(int)str[i].size();j++){
int c=str[i][j]-'a';
if(!d[p][c]){
d[p][c]=++tot;
pos[d[p][c]]=mk(i,j),isp[d[p][c]]=1;
}
p=d[p][c],pf[i][j]=p;
}
}
root=++tot;
for(int i=1;i<=n;i++){
int p=root;sf[i].resize(str[i].size());
for(int j=(int)(str[i].size())-1;j>=0;j--){
int c=str[i][j]-'a';
if(!d[p][c])pos[d[p][c]=++tot]=mk(i,j);
p=d[p][c],sf[i][j]=p;
}
}
// cout<<"tot = "<<tot<<endl;
vector<pair<int,int> >edges;
vector<int>deg(tot+1);
auto print=[&](int x){
// cout<<"print "<<x<<endl;
auto [p,l]=pos[x];
if(isp[x])for(int j=0;j<=l;j++)cout<<str[p][j];
else for(int j=l;j<(int)str[p].size();j++)cout<<str[p][j];
};
auto adde=[&](int u,int v){
// cout<<"adde ";print(u);cout<<" - ";print(v);puts("");
deg[u]++,deg[v]++,edges.emplace_back(mk(u,v));
};
for(int i=1;i<=n;i++){
for(int j=0;j+1<(int)str[i].size();j++)adde(pf[i][j],sf[i][j+1]);
}
for(auto &[u,v]:edges)if(mk(deg[u],u)>mk(deg[v],v))swap(u,v);
sort(edges.begin(),edges.end());edges.erase(unique(edges.begin(),edges.end()),edges.end());
// for(int i=0;i<edges.size();i++)for(int j=i+1;j<edges.size();j++)if(edges[i]==edges[j]){
// cout<<"multi edges : ("<<edges[i].fi<<","<<edges[i].se<<")"<<endl;
// }
vector<vector<int> >G(tot+1),ind(tot+1);
for(auto [u,v]:edges)G[u].emplace_back(v),ind[v].emplace_back(u);
auto clr=[&](){
for(int i=1;i<=tot;i++)memset(d[i],0,sizeof(d[i])),pos[i]=mk(0,0),isp[i]=0;
for(int i=1;i<=n;i++)pf[i].clear(),sf[i].clear();
tot=0;
};
// cout<<"tot = "<<tot<<endl;
auto output=[&](int x,int y,int z,int t,int p=0){
// cout<<"Case = "<<p<<endl;
// cout<<"(id) x,y,z,t = "<<x<<" "<<y<<" "<<z<<" "<<y<<endl;
// cout<<"x,y,z,t = ";print(x),cout<<" ",print(y),cout<<" ",print(z),cout<<" ",print(t),puts("");
if(!isp[x])swap(x,y);
if(!isp[z])swap(z,t);
puts("YES");
print(x),print(y),cout<<" ",print(z),print(t);puts("");
print(z),print(y),cout<<" ",print(x),print(t);puts("");
clr();
};
vector<int>vis(tot+1,0);
for(int i=1;i<=tot;i++){
// case 1
for(int j:G[i])for(int k:G[j]){
// cout<<i<<" -> "<<j<<" -> "<<k<<" vis = "<<vis[k]<<endl;
if(!vis[k])vis[k]=j;
else return output(i,j,k,vis[k],1);
}
for(int j:G[i])for(int k:G[j])vis[k]=0;
// case 2
for(int j:ind[i])for(int k:G[j])if(k!=i)vis[k]=j;
for(int j:G[i])for(int k:G[j])if(k!=i)if(vis[k])return output(i,j,k,vis[k],2);
for(int j:ind[i])for(int k:G[j])vis[k]=0;
// case 3
for(int j:ind[i])for(int k:G[j])if(k!=i){
// cout<<j<<" -> "<<i<<" , "<<j<<" -> "<<k<<" vis = "<<vis[k]<<endl;
if(!vis[k])vis[k]=j;
else return output(i,j,k,vis[k],3);
}
for(int j:ind[i])for(int k:G[j])vis[k]=0;
}
puts("NO"),clr();
}
signed main(void){
#ifndef ONLINE_JUDGE
freopen("2.in","r",stdin);
freopen("2.out","w",stdout);
#endif
int tt=read();while(tt--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 19ms
memory: 163324kb
input:
1 9 blunder blushing crow cry crushing blow black back clap
output:
YES blow crushing crow blushing
result:
ok OK.
Test #2:
score: 0
Accepted
time: 93ms
memory: 187796kb
input:
423 30 aaaaabbbba ababbaaa abaaab bababb aabaa bbaaba bbbaaa abaabba aaabba aabbab bbbaa aaababbbb baaaabaaab aabaaaabab abababbaa aaaaabab abaaaa aabbb baaababa babbaa aabbbb baababb abaabaa aabbbbbb babaabbb baabbaaabb bbbabb baababa bbabb aabbababab 30 abbababbba aabbbaa aaaba bbaba aabbb bbbbbba...
output:
YES bababb bababb baababb bbabb YES abbbaaa aaaba aabaaa abbaba YES aaaaabb baaabaa baaabbb aaaaaaa YES abbaa bbbaba bbbaa abbaba YES baaaa bbbbbaab bbbaaa babbaab YES bbababb abaabba abababb bbaabba YES bbbaababb abbaaa abababb bbbabaaa YES baaab ababbb aaaab bbabbb YES aabbba bbbaab bbabbba abaab ...
result:
ok OK.
Test #3:
score: 0
Accepted
time: 98ms
memory: 241172kb
input:
2 4 vgxgpuamkxkszhkbpphykinkezplvfjaqmopodotkrjzrimlvumuarenexcfycebeurgvjyospdhvuyfvtvnrdyluacvrayggwnpnzijdifyervjaoalcgxovldqfzaorahdigyojknviaztpcmxlvovafhjphvshyfiqqtqbxjjmqngqjhwkcexecmdkmzakbzrkjwqdyuxdvoossjoatryxmbwxbwexnagmaygzyfnzpqftobtaotuayxmwvzllkujidhukzwzcltgqngguftuahalwvjwqncksizg...
output:
YES ivnokuladzhmaajkfuacmfukcnbnfnjbwlgoxvnjyeucjnpncvfgaiwbkryamuegkglbyrutpnunnqzayunkyisacxwinqyhpsyushfmofdpqrvkygtpwlhpdliubxrcrdagwgwxbigcxgsqzbirsykfnkfxuvadgecswqwluhzzrslmzbkwyaslguyahbempkuxmvmwapyryjcoeptvifwxjlfnnffnjhekfupytmvcvwtbzaqvsdbbhwuoyiqaqkrxaumhqqyjwxtlnmzqhfcgqiseezekrscopbsu...
result:
ok OK.
Test #4:
score: 0
Accepted
time: 99ms
memory: 279880kb
input:
1 45000 zaaaaaaaaz zaaabaaabz zaaacaaacz zaaadaaadz zaaaeaaaez zaaafaaafz zaaagaaagz zaaahaaahz zaaaiaaaiz zaaajaaajz zaaakaaakz zaaalaaalz zaaamaaamz zaaanaaanz zaaaoaaaoz zaaapaaapz zaaaqaaaqz zaaaraaarz zaaasaaasz zaaataaatz zaaauaaauz zaaavaaavz zaaawaaawz zaaaxaaaxz zaabaaabaz zaabbaabbz zaabca...
output:
NO
result:
ok OK.
Test #5:
score: 0
Accepted
time: 99ms
memory: 271364kb
input:
1 45000 aaaaaaay aaaaaaaaabaaab zaabaaab aaacaaay aaacaaaaadaaad zaadaaad aaaeaaay aaaeaaaaafaaaf zaafaaaf aaagaaay aaagaaaaahaaah zaahaaah aaaiaaay aaaiaaaaajaaaj zaajaaaj aaakaaay aaakaaaaalaaal zaalaaal aaamaaay aaamaaaaanaaan zaanaaan aaaoaaay aaaoaaaaapaaap zaapaaap aaaqaaay aaaqaaaaaraaar zaar...
output:
NO
result:
ok OK.
Test #6:
score: 0
Accepted
time: 87ms
memory: 249368kb
input:
1 24076 mwbmwbcmdbcmdb tugbtugbcmdbcmdb gvygvysizsiz uivuivglbglb patpatifrifr gjjbgjjbhhkbhhkb zwhzwhadcbadcb sbhbsbhbucjucj gcibgcibnqnnqn mrmrouloul patpatgjlgjl cwqcwqhmthmt swesweemxemx lqkblqkbvagvag patpatgjmbgjmb lgxlgxfiffif cjycjyaygayg mszmszriirii numnumzhmzhm ublbublbasuasu htnhtncmdbcm...
output:
YES gcibgcibcmdbcmdb patpatucjucj patpatcmdbcmdb gcibgcibucjucj
result:
ok OK.
Test #7:
score: 0
Accepted
time: 72ms
memory: 239988kb
input:
1 21712 idnbidnbscrscr idnbidnbbzubzu cavcavukrbukrb eudeudtthtth bljbbljbeveeve ngnbngnbqkcbqkcb ikyikynaobnaob iunbiunbeveeve oeooeoqzpqzp ssqbssqbthvthv xjjxjjeveeve hvkbhvkbndkbndkb saibsaibvvivvi dwqdwqlojloj ywbbywbbeveeve whabwhablhnblhnb niuniuixwixw mnpmnpclibclib smcsmcevnevn ffrbffrbwyqbw...
output:
YES vubbvubbnwjbnwjb xhbxhbecsecs xhbxhbnwjbnwjb vubbvubbecsecs
result:
ok OK.
Test #8:
score: 0
Accepted
time: 105ms
memory: 259392kb
input:
1 30360 alcbalcbqflbqflb uysuysaihbaihb aqzaqzxgdbxgdb wvabwvablwklwk rvjbrvjbqujbqujb fezfezfvfbfvfb hmbbhmbbijij nkinkiilqilq aenbaenbcskbcskb lfiblfibngbngb tgntgnwbswbs wuibwuibqwsqws bpxbpxekcekc mksmksaghagh fiqfiqbakbbakb labblabbigcbigcb bxkbxkdoodoo hzlhzlxhmxhm kobkobugbugb xfibxfibmxwmxw ...
output:
NO
result:
ok OK.
Test #9:
score: 0
Accepted
time: 100ms
memory: 267180kb
input:
1 33936 sembsembqypqyp bvxbvxlumblumb tbabtbabxdbbxdbb etketktwjbtwjb pdopdozsbbzsbb pnpbpnpbkltklt nckbnckbjykjyk qjdbqjdbznszns oymoymgifbgifb owkbowkbddebddeb mcpbmcpbvlqvlq mpompogpebgpeb ljqljqtrdbtrdb jmjbjmjbbnnbnn bgxbgxbxpbbxpb benbencbebcbeb jnpbjnpbqevqev wbbwbbwhxwhx yckyckwnabwnab rjirj...
output:
NO
result:
ok OK.
Test #10:
score: 0
Accepted
time: 99ms
memory: 267964kb
input:
1 33936 qxxqxxfrhbfrhb arabarabxvwxvw lmclmcqcsqcs rdurdugszgsz byrbyryhkbyhkb sevsevvfibvfib tpxtpxwevwev xxhxxhllhbllhb kqcbkqcbbwjbwj irobirobbwobbwob xtnxtnlncblncb manbmanbztfztf tdltdlrlzrlz kkzkkzfhobfhob ekrbekrbobgbobgb tjttjtcmibcmib ohnbohnbtvtv fzcbfzcbmqbbmqbb dagdagcwicwi bmebbmebgjygj...
output:
NO
result:
ok OK.
Test #11:
score: 0
Accepted
time: 121ms
memory: 262332kb
input:
1 33048 dlbbdlbbpzdpzd zkmbzkmbgtkgtk dwhdwhssebsseb gzfbgzfbsbssbs prqbprqbgcwgcw ruhbruhbpcbpcb oqyoqytixtix uvnuvnbodbbodb ijkbijkbyclbyclb jphbjphbyxwyxw vlhbvlhbqkoqko jiljiletcetc ujgbujgbkzdkzd hsphsppzpbpzpb cufcufnqnq kdskdspspbpspb mmabmmabzljbzljb qsgbqsgbjepbjepb stjstjwrhbwrhb ogzogzcwp...
output:
NO
result:
ok OK.
Test #12:
score: 0
Accepted
time: 110ms
memory: 268188kb
input:
1 36192 gelgelxafxaf nkwnkwigjbigjb halhalbbdbbd tlutluuebbuebb ilvilvhoho isziszacvacv amxamxhugbhugb rlsrlsblbblb porbporblsls ytgytgvhnbvhnb qtgqtgpwlpwl bogbbogbqgmbqgmb ecwecwoioboiob gvgbgvgbuacbuacb iemiemnrlnrl xolxolwhabwhab qsobqsobdabdab frebfrebhwshws efrbefrbpljbpljb vcjvcjtwvtwv cklbck...
output:
NO
result:
ok OK.
Test #13:
score: 0
Accepted
time: 111ms
memory: 262696kb
input:
1 34884 eyeymulbmulb exyexyidhbidhb ptrbptrbdtrbdtrb dlsdlsxumxum odgodgtejtej doebdoebqqyqqy bgobgofofbfofb bidbidcwabcwab rtmbrtmbxtlbxtlb pgfpgfbygbbygb qzjbqzjbbopbbopb yxhbyxhbzkcbzkcb ornbornbxirbxirb jxgjxgvdjvdj puibpuiboaeoae frpbfrpbdarbdarb citcititlitl ijvijvnchbnchb awgawgnlfbnlfb jkjbj...
output:
NO
result:
ok OK.
Test #14:
score: 0
Accepted
time: 111ms
memory: 266464kb
input:
1 36504 zshzshwkibwkib wcpbwcpbrvfbrvfb blmbblmbollbollb vdpvdpxlhxlh bubuuwcbuwcb hwbbhwbbhegbhegb poopoopajbpajb rnzrnzfrabfrab otzotztjbtjb xdcbxdcbggibggib gexgexgvlgvl wsfwsfgkegke vxivxivelbvelb vsmvsmmyrbmyrb hxpbhxpbfoqbfoqb ypibypibnounou epnbepnbzsibzsib xdkbxdkbatwatw ovyovybmmbmm fkofkor...
output:
NO
result:
ok OK.