QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#634359#8234. Period of a StringLateRegistration#WA 26ms14224kbC++173.9kb2024-10-12 17:09:162024-10-12 17:09:16

Judging History

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

  • [2024-10-12 17:09:16]
  • 评测
  • 测评结果:WA
  • 用时:26ms
  • 内存:14224kb
  • [2024-10-12 17:09:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define per(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename T>void chkmax(T&x,const T&y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,const T&y){if(y<x)x=y;}

#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define mem(x) memset((x),0,sizeof(x))

typedef double db;
typedef long long ll;
typedef vector<int>vi;
typedef pair<int,int>pii;

typedef unsigned u32;
typedef unsigned uint;
typedef unsigned long long u64;

namespace orzjk{
  const int SZ=1e6;
  char buf[SZ],*p1=buf,*p2=buf;
  char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SZ,stdin),p1==p2)?EOF:*p1++;
  }
  char fub[SZ],*p3=fub,*p4=fub+SZ;
  void pc(char c){
    p3==p4&&(fwrite(fub,1,SZ,stdout),p3=fub);
    *p3++=c;
  }
  void flush(){
    fwrite(fub,1,p3-fub,stdout),p3=fub;
  }
}
using orzjk::nc;
using orzjk::pc;

//#define nc getchar
//#define pc putchar

int read(){
  int x=0,f=1;char c=nc();
  while(c<48)c=='-'&&(f=-1),c=nc();
  while(c>47)x=x*10+(c^48),c=nc();
  return x*f;
}
template<class T>void write(T x){
  static char st[41];
  if(!x)return pc(48),void();
  char*p=st;
  if(x<0)x=-x,pc('-');
  for(;x;x/=10)*p++=x%10|48;
  do{
    pc(*--p);
  }while(p!=st);
}

//const int P=1e9+7;
const int P=998244353;
int qp(int a,int k){
  int res=1;for(;k;k>>=1,a=1ll*a*a%P)if(k&1)res=1ll*res*a%P;return res;
}

const int maxn=1e5+10;
int n;
int len[maxn];
int cnt[maxn][26],lim[maxn][26];
char buf[maxn*50],ans[maxn*50];

int N,mnv[maxn*4];
void build(){
  N=1;
  for(;N<n;N<<=1);
  rep(i,1,n)mnv[N+i-1]=len[i];
  per(i,N-1,1)mnv[i]=min(mnv[i<<1],mnv[i<<1|1]);
}
int ask(int pos,int v){ // idx<pos,val<=v
  int k=N+pos-1;
  while(k>1){
    if(k&1){
      if(mnv[k^1]<=v){
        k^=1;
        while(k<N){
          k=k<<1|(mnv[k<<1|1]<=v);
        }
        return k-N+1;
      }
    }
    k>>=1;
  }
  return 0;
}

typedef array<int,26>arr;

void solve(){
  cin>>n;
  rep(i,1,n){
    cin>>(buf+1);
    len[i]=strlen(buf+1);
    mem(cnt[i]);
    rep(j,1,len[i]){
      cnt[i][buf[j]-'a']++;
    }
  }
  memset(ans,0,len[1]+3);
  build();
  vector<pii>vec;
  rep(i,1,n){
    int pos=i,sz=len[i];
    static int c[26];
    memcpy(c,cnt[i],sizeof c);
    while(1){
      int nxt=ask(pos,sz);
      if(!nxt)break;
      assert(len[nxt]<=sz);
      int tmp=sz/len[nxt];
//      printf("(%d %d) %d\n",pos,sz,nxt);
      rep(j,0,25){
        c[j]-=cnt[nxt][j]*tmp;
        if(c[j]<0){
          puts("NO");
          return;
        }
      }
      pos=nxt;
      sz%=len[nxt];
    }
    memcpy(lim[i],c,sizeof c);
    // (sz, c)
    if(sz){
//      printf("%d : [%d] ",i,sz);
//      rep(j,0,25)if(c[j])printf("(%c %d) ",'a'+j,c[j]);
//      puts("");
      vec.pb({sz,i});
    }
  }
//  puts("GG");
  sort(ALL(vec),[&](pii A,pii B){
    return A.first<B.first;
  });
  int cur[26]={0},lst=0;
  for(auto[sz,idx]:vec){
    static int ths[26];
    memcpy(ths,lim[idx],sizeof ths);
    int sum=0;
    rep(i,0,25){
      sum+=ths[i]-cur[i];
      if(cur[i]>ths[i]){
        puts("NO");
        return;
      }
    }
    if(sum!=sz-lst){
      puts("NO");
      return;
    }
    rep(i,0,25){
      rep(j,1,ths[i]-cur[i]){
        ans[++lst]='a'+i;
      }
    }
    memcpy(cur,ths,sizeof cur);
  }
  puts("YES");
  puts(ans+1);
  rep(i,2,n){
    if(len[i]<len[i-1]){
      rep(j,len[i]+1,len[i-1])ans[j]=0;
    }else{
      rep(j,len[i-1]+1,len[i])ans[j]=ans[(j-1)%len[i-1]+1];
    }
    puts(ans+1);
  }
}

signed main(){
  ios::sync_with_stdio(0),cin.tie(0);
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
  int T;cin>>T;while(T--)solve();
//  solve();
  orzjk::flush();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 2ms
memory: 13824kb

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: 26ms
memory: 14224kb

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 Wrong length of string (test case 7)