QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#605522 | #8234. Period of a String | DBsoleil# | WA | 2ms | 7640kb | C++20 | 3.4kb | 2024-10-02 17:40:36 | 2024-10-02 17:40:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=1e5+5,K=26;
int T,n,len[N];
string t[N];
struct req
{
int x[26];
req() {for(int i=0;i<K;i++) x[i]=0;}
int&operator [](int i) {return x[i];}
int sum()
{
int res=0;
for(int i=0;i<K;i++) res+=x[i];
return res;
}
req friend operator + (req a,req b)
{
req res;
for(int i=0;i<K;i++) res[i]=max(a[i],b[i]);
return res;
}
req friend operator * (req a,int b)
{
req res;
for(int i=0;i<K;i++) res[i]=a[i]*b;
return res;
}
req friend operator -(req a,req b)
{
req res;
for(int i=0;i<K;i++) res[i]=max(a[i]-b[i],0);
return res;
}
bool friend operator > (req a,req b)
{
for(int i=0;i<K;i++) if(a[i]>b[i]) return 1;
return 0;
}
};
void prin(req x)
{
for(int i=0;i<K;i++) cerr<<' '<<x[i];
cerr<<endl;
}
vector<req> ve[N];
void input()
{
string s;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s,len[i]=s.size();
ve[i].clear(),ve[i].resize(len[i]);
for(int j=0;j<len[i];j++) ve[i][len[i]-1][s[j]-'a']++;
}
}
bool work(vector<req>&u,vector<req>&v,int lu,int lv)
{
if(lu<=lv)
{
for(int i=0;i<lu;i++) v[i]=v[i]+u[i];
for(int i=0;i<lv;i++)
{
if(i>0) v[i]=v[i]+v[i-1];
//cerr<<i<<endl;
//prin(v[i]);
if(v[i].sum()>i+1) return 0;
}
return 1;
}
req rq=v[lv-1];
int p=(lu+lv-1)/lv;
if(u[lu-1]>(rq*p)) return 0;
//prin(rq),prin(rq*1);
for(int l=0,p=0;l<lu;l+=lv,p++)
{
int r=min(l+lv,lu);
if(r%lv==0&&(u[r-1]+(rq*(p+1))).sum()>r) return 0;
for(int i=l;i<r;i++) v[i%lv]=v[i%lv]+(u[i]-(rq*p));
//cerr<<l<<' '<<r<<endl;
//prin(u[r-1]);
//prin((u[r-1]+(rq*(p+1))));
}
//for(int i=0;i<lv;i++) prin(v[i]);
for(int i=0;i<lv;i++) if(v[i].sum()>i+1) return 0;
return 1;
}
bool check()
{
for(int i=n-1;i>=1;i--)
{
//cerr<<i<<endl;
if(!work(ve[i+1],ve[i],len[i+1],len[i])) return 0;
//cerr<<endl;
}
return 1;
}
bool getans(vector<req>&u,vector<req>&v,int lu,int lv,string&su,string&sv)
{
sv="";
req nw;
if(lu==-1)
{
for(int i=0;i<lv;i++)
{
for(int j=0;j<K;j++) if(nw[j]<v[i][j])
{
sv+=char('a'+j);
nw[j]++;
}
}
return 1;
}
int p=lv/lu,q=lv%lu;
for(int i=1;i<=p;i++) sv+=su;
sv+=su.substr(0,q);
//cerr<<sv<<endl;
for(int i=0;i<lv;i++)
{
nw[sv[i]-'a']++;
//prin(nw); prin(v[i]);
if((nw+v[i]).sum()>i+1) return 0;
}
return 1;
}
bool output()
{
len[0]=-1;
for(int i=1;i<=n;i++)
{
//cerr<<i<<endl;
if(!getans(ve[i-1],ve[i],len[i-1],len[i],t[i-1],t[i])) return 0;
//cerr<<t[i]<<endl;
}
return 1;
}
void solve()
{
input();
if(!check()||!output()) cout<<"NO"<<endl;
else
{
cout<<"YES"<<endl;
for(int i=1;i<=n;i++) cout<<t[i]<<endl;
}
}
int main()
{
cin.sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7640kb
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: -100
Wrong Answer
time: 0ms
memory: 6968kb
input:
5 1 ccecddbdbbcbbaded 3 cd d d 1 dcedec 2 dcec cce 8 a e a c cc cccccccc c b
output:
YES abcde YES dc d d YES cde YES cecd cec NO
result:
wrong answer Wrong length of string (test case 1)