QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#693482 | #8234. Period of a String | doyo | WA | 81ms | 10284kb | C++20 | 2.6kb | 2024-10-31 16:15:15 | 2024-10-31 16:15:18 |
Judging History
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 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);
}
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;
FOR(j,0,l[i]-1){
++xz[h][l[i]-1].alpha[s[i][j]-'a'];
xz[h][l[i]-1].exi = 1;
++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+1)/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();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
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: 3544kb
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: 81ms
memory: 10284kb
input:
100 147 ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO
result:
wrong answer Jury has the answer but participant has not (test case 2)