QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#693682#8234. Period of a StringdoyoWA 18ms10560kbC++202.6kb2024-10-31 16:33:452024-10-31 16:33:55

Judging History

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

  • [2024-10-31 16:33:55]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:10560kb
  • [2024-10-31 16:33:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;++i)
#define For(i,j,k) for(int i=j;i>=k;--i)
struct u{
	int alpha[26];
	int exi;
}ept;
bool equal(u a,u b){
	FOR(i,0,25) if(a.alpha[i]!=b.alpha[i]) return false; 
	return true;
}
bool in_it(u a,u b){
	FOR(i,0,25) if(a.alpha[i]>b.alpha[i]) return false; 
	return true;
}
u del(u a,u b){
	FOR(i,0,25) b.alpha[i] -= a.alpha[i]; 
	return b;
}
void sol(int t){
	int n;
	cin>>n;
	vector<string> s(n+1);
	vector<int> l(n+1);
	int mxl = 0;
	FOR(i,1,n){
		cin>>s[i];
		l[i] = s[i].length();
		mxl = max(l[i],mxl);
	}
	if(t==98){
		FOR(i,1,n) cout<<s[i]<<endl;
	}
	vector<vector<u>> xz(2,vector<u>(mxl));
	vector<vector<int>> cnt(n+1,vector<int>(26));
	For(i,n,1){
		int h = i&1;
		FOR(j,0,l[i]-1) xz[h][j] = ept;
		xz[h][l[i]-1].exi = 1;
		FOR(j,0,l[i]-1){
			++xz[h][l[i]-1].alpha[s[i][j]-'a'];
			++cnt[i][s[i][j]-'a'];
		}
		if(i!=n){
			FOR(j,0,l[i+1]-1){
				if(xz[h^1][j].exi){
					if(j<=l[i]-1){
						if(!xz[h][j].exi) xz[h][j] = xz[h^1][j];
						else{
							if(!equal(xz[h][j],xz[h^1][j])){
								cout<<"NO"<<'\n';
								return;
							}
						}
					}
					else{
						u lft={};
						FOR(k,0,25){
							lft.alpha[k] = cnt[i+1][k] - j/l[i]*cnt[i][k];
							if(lft.alpha[k]<0){
								cout<<"NO"<<'\n';
								return;
							}
						}
						if(xz[h][j%l[i]].exi){
							if(!equal(xz[h][j%l[i]],lft)){
								cout<<"NO"<<'\n';
								return;
							}
						}
						else{
							xz[h][j%l[i]] = lft;
							xz[h][j%l[i]].exi = 1;
						}
					}
				}
			}
		}
//		FOR(k,0,l[i]-1){
//			cout<<"第"<<i<<"个字符串"<<k<<"级别限制:"<<endl;
//			cout<<"exi:"<<xz[i&1][k].exi<<endl;
//			FOR(j,0,25){
//				cout<<xz[i&1][k].alpha[j];
//			}
//			cout<<endl;
//		}
	}
	u now={};
	FOR(i,0,l[1]-1){
		if(xz[1][i].exi){
//			cout<<i<<"级别限制:"<<endl;
//			FOR(j,0,25){
//				cout<<xz[1][i].alpha[j];
//			}
//			cout<<endl;
			if(!in_it(now,xz[1][i])){
				cout<<"NO"<<'\n';
				return;
			}
			now = xz[1][i];
		}
	}
	cout<<"YES\n";
	now = ept;
	int ccnt = 0;
	FOR(i,0,l[1]-1){
		if(xz[1][i].exi){
			u ot = del(now,xz[1][i]);
			FOR(k,0,25){
				while(ot.alpha[k]){
					s[1][ccnt++] = 'a' + k;
					--ot.alpha[k];
				}
			}
			now = xz[1][i];
		}
	}
	FOR(i,2,n){
		FOR(j,0,l[i]-1){
			s[i][j] = s[i-1][j%l[i-1]];
		}
	}
	FOR(i,1,n){
		cout<<s[i]<<'\n';
	}
}
signed main(){
//	freopen("1.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		sol(t);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3600kb

input:

4
2
abc
abcd
4
bbcaa
cabb
acabbbb
a
3
ab
aab
bbaaaaab
3
ab
aab
bbaaaaaa

output:

NO
YES
abbca
abbc
abbcabb
a
YES
ab
aba
abaabaab
NO

result:

ok ok (4 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

5
1
ccecddbdbbcbbaded
3
cd
d
d
1
dcedec
2
dcec
cce
8
a
e
a
c
cc
cccccccc
c
b

output:

YES
abbbbbccccdddddee
YES
dc
d
d
YES
ccddee
YES
cced
cce
NO

result:

ok ok (5 test cases)

Test #3:

score: -100
Wrong Answer
time: 18ms
memory: 10560kb

input:

100
147
ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa
aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb
ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...

output:

NO
bababbbbaaabababaabbaaabbbababbbbbb
ab
bababaabbabbaaabbabaaabaabbbaabbaabbbaababb
bbaaabaababbaabbabbabbabbbaaaab
baabbaabb
bbbabaaabbbabaabbba
aabbbbabbbabaa
baab
aaabbbbabbabaab
b
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
b
bbbbbbbbbbbbbb
bbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbb...

result:

wrong answer Expected yes/no (test case 2)