QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#665480 | #8234. Period of a String | OIer_kzc# | WA | 49ms | 12280kb | C++17 | 3.6kb | 2024-10-22 13:20:23 | 2024-10-22 13:20:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define p 1000000007
#define ll long long
int read(){
int u=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9'){
u=u*10+c-48;
c=getchar();
}
return u;
}
int n;
int s[100011][26],len[100011];
struct Sub{
int A[26];
int l,r;
friend bool operator <(Sub x,Sub y){
return (x.l<y.l);
}
void build(int x){
l=0,r=len[x]-1;
fo(j,0,25)A[j]=s[x][j];
}
bool Cut(Sub y){
fo(j,0,25){
if(y.A[j]>A[j])return 0;
A[j]-=y.A[j];
}
l=y.r+1;
return 1;
}
};
Sub fir;
char s2[5000011];
set<Sub>F;
string ans[100011];
bool Add(Sub X){
auto it=F.begin();
while(it!=F.end()){
if((*it).r<=X.r){
int v=X.Cut(*it);
if(!v){
puts("NO");
return 0;
}
}
else{
if(X.l<=X.r){
Sub v=(*it);
int u=v.Cut(X);
if(!u){
puts("NO");
return 0;
}
F.erase(it);
F.insert(X);
F.insert(v);
}
return 1;
}
++it;
}
return 1;
}
void qin(Sub x){
int u=0;
fo(i,x.l,x.r){
while(x.A[u]==0)++u;
if(ans[1][i]=='#'){
ans[1][i]='a'+u;
}
--x.A[u];
}
}
void solve(){
n=read();
fo(i,1,n){
scanf("%s",s2);
len[i]=strlen(s2);
memset(s[i],0,sizeof(s[i]));
fo(j,0,len[i]-1){
++s[i][s2[j]-'a'];
}
ans[i].clear();
fo(j,1,len[i])ans[i].push_back('#');
}
F.clear();
Sub Init;
Init.build(1);
F.insert(Init);
fo(i,2,n){
if(len[i]<=len[i-1]){
Sub X;
X.build(i);
int v=Add(X);
if(!v)return ;
auto it=F.end();
--it;
while((*it).l>=len[i]){
qin((*it));
--it;
}
++it;
while(it!=F.end()){
auto it2=it;
++it2;
F.erase(it);
it=it2;
}
}
else{
int h=len[i]%len[i-1];
Sub X;
X.l=0,X.r=h-1;
int w=len[i]/len[i-1];
if(h){
fo(j,0,25){
X.A[j]=s[i][j]-s[i-1][j]*w;
if(X.A[j]<0){
puts("NO");
return ;
}
}
int v=Add(X);
if(!v)return ;
}
}
}
while(F.size()){
qin(*F.begin());
F.erase(F.begin());
}
fo(i,2,n){
fo(j,0,len[i-1]-1){
int u=j;
while(u<len[i]){
ans[i][u]=ans[i-1][j];
u+=len[i-1];
}
}
}
fo(i,1,n){
int h[26]={0};
fo(j,0,len[i]-1)h[ans[i][j]-'a']++;
fo(j,0,25){
if(s[i][j]!=h[j]){
puts("NO");
return ;
}
}
}
puts("YES");
fo(i,1,n){
cout<<ans[i]<<"\n";
}
}
int main(){
int T=read();
while(T){
--T;
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 10220kb
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: 9108kb
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: 49ms
memory: 12280kb
input:
100 147 ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...
output:
NO YES baaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb ba bababababababababababababababababababababab bababababababababababababababab babababab bababababbababababb bababababbabab baba bababababababab b bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb b bbbbbbbbbbbbbb bbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbbbbbbb bbbbbbbb...
result:
wrong answer Jury has the answer but participant has not (test case 4)