QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#308122#7340. Spoonerismsucup-team1303AC ✓121ms279880kbC++143.6kb2024-01-19 16:17:242024-01-19 16:17:25

Judging History

你现在查看的是最新测评结果

  • [2024-01-19 16:17:25]
  • 评测
  • 测评结果:AC
  • 用时:121ms
  • 内存:279880kb
  • [2024-01-19 16:17:24]
  • 提交

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.