QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#621050 | #8234. Period of a String | Yzm007 | WA | 76ms | 250944kb | C++14 | 3.9kb | 2024-10-08 01:24:17 | 2024-10-08 01:24:17 |
Judging History
answer
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10,M=5e6+10,K=26;
char s[M],ans[M];
int t,n,c,mx,par[M],sz[N],a[N][K],lim[N],b[N][K];
vector<int>del[M],del2[M];
set<int>p,q;
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
void mer(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
if(x>y)swap(x,y);
par[y]=x;
}
int getch(int i){
int fa=find(i),lb,rb;
if(fa==i)lb=0,rb=25;
else lb=rb=ans[fa]-'a';
//printf("i:%d fa:%d lb:%d rb:%d\n",i,fa,lb,rb);
rep(j,lb,rb){
bool ok=1;
for(auto &v:p){
if(!b[v][j]){
ok=0;
break;
}
}
if(!ok)continue;
for(auto &v:q){
if(!a[v][j]){
ok=0;
break;
}
}
if(ok){
for(auto &v:p){
b[v][j]--;
}
for(auto &v:q){
a[v][j]--;
}
return j;
}
}
return -1;
}
bool sol(){
rep(i,2,n){
int x=i-1,y=i;
if(sz[x]==sz[y]){//前后相等,完全相同
rep(j,0,25){
if(a[x][j]!=a[y][j])return 0;
}
}
else if(sz[x]<sz[y]){//前短后长,前串是后串的循环节
int w=sz[y]/sz[x];
rep(j,sz[x]+1,sz[y]){
mer(j,j-sz[x]);
}
rep(j,0,25){
if(a[y][j]<1ll*a[x][j]*w)return 0;
}
int r=sz[y]%sz[x];
if(r){
lim[++c]=r;
p.insert(c);
rep(j,0,25){
b[c][j]=a[y][j]-a[x][j]*w;
}
del[lim[c]].pb(c);
}
}
else{//前长后短,前缀相等
rep(j,0,25){
if(a[x][j]<a[y][j])return 0;
}
lim[++c]=sz[y];
p.insert(c);
rep(j,0,25){
b[c][j]=a[y][j];
}
del[lim[c]].pb(c);
}
}
rep(i,1,mx){
int ch=getch(i);
if(ch==-1)return 0;
ans[i]=ch+'a';
//printf("i:%d ans:%c\n",i,ans[i]);
for(auto &v:del[i]){
p.erase(v);
}
for(auto &v:del2[i]){
q.erase(v);
}
}
return 1;
}
int main(){
sci(t);
while(t--){
mx=c=0;
p.clear();q.clear();
sci(n);
rep(i,1,n){
memset(a[i],0,sizeof(a[i]));
scanf("%s",s+1);
int m=strlen(s+1);
rep(j,1,m){
a[i][s[j]-'a']++;
}
sz[i]=m;
mx=max(mx,sz[i]);
q.insert(i);
del2[sz[i]].pb(i);
}
rep(i,1,mx)par[i]=i;
if(!sol()){
puts("NO");
}
else{
puts("YES");
rep(i,1,n){
int p=sz[i]+1;
char x=ans[p];
ans[p]='\0';
printf("%s\n",ans+1);
ans[p]=x;
}
}
rep(i,1,c){
del[lim[i]].clear();
}
rep(i,1,n){
del2[sz[i]].clear();
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 36ms
memory: 248120kb
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: 41ms
memory: 248704kb
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: 76ms
memory: 250944kb
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 YES a a aa aaaa aaa a aaaaaaaa aaaa aaaaaaaaaa a aaaaa aa a aaaaaaaaaaaaaaaaa aaaa aa aa aaaa aaaaaaaaaaaaa aaaaa aaaaaaaaaaaa aaaaaa aaaaaaaaa aaa a aaaaaa aaaaaaa a aa aa a aaaaa aaa aaaaaaa aaaaaa aaaaa aaa aa ...
result:
wrong answer Jury has the answer but participant has not (test case 2)