QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#709723#8234. Period of a StringcarottWA 104ms18296kbC++206.8kb2024-11-04 16:27:502024-11-04 16:27:51

Judging History

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

  • [2024-11-04 16:27:51]
  • 评测
  • 测评结果:WA
  • 用时:104ms
  • 内存:18296kb
  • [2024-11-04 16:27:50]
  • 提交

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)