QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#709723 | #8234. Period of a String | carott | WA | 104ms | 18296kb | C++20 | 6.8kb | 2024-11-04 16:27:50 | 2024-11-04 16:27:51 |
Judging History
answer
//Created by carottx on 2024-11-04.
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
namespace IO {
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc() \
(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
? EOF \
: *p1++)
int rd() {
int x = 0, f = 1;
char c = gc();
while (!isdigit(c)) {
if (c == '-') f = -1;
c = gc();
}
while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
return x * f;
}
char pbuf[1 << 20], *pp = pbuf;
void push(const char &c) {
if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
*pp++ = c;
}
void clear(){
fwrite(pbuf, 1, strlen(pbuf), stdout);
pp = pbuf;
}
void write(int x) {
static int sta[35];
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
}
} // namespace IO
const int maxn=100005;
const int INF=1e9+7;
// using namespace MYDEBUG;
int n;
string s[maxn];
string ans[maxn];
int len[maxn];
struct Restriction{
int len;
int cnt[26];
void clear(){len=0;memset(cnt, 0, sizeof(cnt));}
Restriction operator+(char c){
Restriction nr;
memcpy(nr.cnt, cnt, sizeof(cnt));
nr.cnt[c-'a']++;
nr.len = len+1;
return nr;
}
Restriction operator-(Restriction other){
Restriction nr;
for(int i=0; i<26; ++i) nr.cnt[i] = cnt[i] - other.cnt[i];
nr.len = len - other.len;
return nr;
}
Restriction operator*(int x){
Restriction nr;
nr.len = len*x;
for(int i=0; i<26; ++i) nr.cnt[i] = x*cnt[i];
return nr;
}
bool operator<(const Restriction& other)const{
return len < other.len;
}
bool check(){
for(int i=0;i<26;++i){
if(cnt[i] < 0) return false;
}
return true;
}
};
struct Segment{
int val;
int max;
}seg[20000000];
void build(int id, int l, int r){
if(l>r)return;
if(l==r){
seg[id].val = 0;
seg[id].max = 0;
return;
}
int mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
seg[id].max = max<int>(seg[id*2+1].max, seg[id*2].max);
}
void update(int id, int l, int r, int pos,int val){
if(r<pos) return;
if(l>pos) return;
if(l==pos){
seg[id].val = val;
seg[id].max = val;
return;
}
int mid = (l+r)/2;
update(id*2, l, mid, pos,val);
update(id*2+1, mid+1, r, pos, val);
seg[id].max = max<int>(seg[id*2].max, seg[id*2+1].max);
}
int query(int id, int l, int r, int L, int R){
if(r < L || l > R) return 0;
if(L<=l && r<=R) return seg[id].max;
int mid = (l+r)/2;
return max<int>(query(id*2, l, mid, L, R),query(id*2+1, mid+1, r, L, R));
}
Restriction r[maxn];
int T;
void solve(){
// cerr<<"!!!!!!!!!!!!!!!!!!!!!!!"<<endl;
cin>>n;
// n=147;
int MaxLen = 0;
for(int i=0; i<n; ++i) r[i].clear();
for(int i=0; i<n; ++i) {
cin>>s[i];
// s[i] = "";
// for(int j=0; j<5000; ++j) s[i] += 'a';
}
for(int i=0; i<n; ++i) {
len[i] = s[i].length();
MaxLen = max(len[i],MaxLen);
Restriction& tmp = r[i];
tmp = tmp + s[i][0];
for(int j=1; j<len[i]; ++j){
tmp = tmp + s[i][j];
}
}
build(1,1,MaxLen);
vector<Restriction> r0;
int LenOfFirst = len[0];
for(int i=1; i<n; ++i){
int NowLen = len[i];
auto tmp = r[i];
while(NowLen != 0){
int id = query(1,1,MaxLen,1,NowLen)-1;
if(id!=-1) {
int ModLen = len[id];
tmp = tmp - r[id] * (NowLen/ModLen);
if(!tmp.check()) {
// if(T==100){cout<<"FUCK0"<<endl;}
// cout<<"NO"<<endl;
IO::push('N');
IO::push('O');
IO::push('\n');
return;
}
NowLen %= ModLen;
}
else {
id = 0 ;
tmp = tmp - r[id] * (NowLen/LenOfFirst);
NowLen %= LenOfFirst ;
break;
}
}
if(NowLen){
int mul = (len[i]-NowLen)/LenOfFirst;
r0.push_back(tmp);
}
update(1,1,MaxLen,len[i],i+1);
}
sort(r0.begin(),r0.end());
r0.push_back(r[0]);
Restriction now;
now.clear();
bool flag = false;
string& new0 = ans[0];
new0 = "";
for(auto& rr: r0){
Restriction tmp = rr-now;
for(int i=0; i<26; ++i)
{
if(tmp.cnt[i] < 0){
flag = true;
// if(T==100) cout<<"FUCK1"<<endl;
break;
}
else if(tmp.cnt[i] > 0){
for(int k=0; k<tmp.cnt[i]; ++k) new0 += i+'a';
}
}
now = rr;
}
for(int i=1; i<n && !flag; ++i){
int mul = len[i]/len[i-1];
auto delta = r[i] - r[i-1] * mul;
if(!delta.check()) {flag=true;break;}
ans[i] = "";
for(int j=0; j<mul; ++j) ans[i] += ans[i-1];
for(int j=0; j<delta.len; ++j){
if(delta.cnt[ans[i-1][j]-'a']<=0) {flag=true;break;}
delta.cnt[ans[i-1][j]-'a'] --;
ans[i] += ans[i-1][j];
}
}
if(flag) {
IO::push('N');
IO::push('O');
IO::push('\n');
// cout<<"NO"<<endl;
return;
}
IO::push('Y');
IO::push('E');
IO::push('S');
IO::push('\n');
// cout<<"YES"<<endl;
for(int i=0;i<n;++i){
for(int j=0; j<ans[i].length(); ++j) IO::push(ans[i][j]);
IO::push('\n');
// cout<<ans[i]<<endl;
}
}
int main(){
// freopen("output.txt","w",stderr);
// freopen("test.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>T;
for(int _=0;_<T;++_)solve();
IO::clear();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 13800kb
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: 15916kb
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: 104ms
memory: 18296kb
input:
100 147 ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...
output:
NO NO NO NO NO NO YES bbaaaaabbbbbbbbbbb bb bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb bb bbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbbbbbbbbbbbbb bbbb bbbbbbbbbbbb bbbbbb bbbbb bbbbbbbbbb bbb bbb b bbbbbbbbbbbbbbbbb bbbb bbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbb b bbb bbbbbbbbbbbbbbbbb bbbbbb bbbbb bbbbbbbbbbbbbbb...
result:
wrong answer Jury has the answer but participant has not (test case 2)