QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#634359 | #8234. Period of a String | LateRegistration# | WA | 26ms | 14224kb | C++17 | 3.9kb | 2024-10-12 17:09:16 | 2024-10-12 17:09:16 |
Judging History
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)