QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#708259#8234. Period of a StringlmcgWA 1ms5588kbC++203.9kb2024-11-03 20:50:302024-11-03 20:50:30

Judging History

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

  • [2024-11-03 20:50:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5588kb
  • [2024-11-03 20:50:30]
  • 提交

answer

#include <bits/stdc++.h>

class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        #define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
        char Fin[S],Fout[S],*A,*B,*Ftop,*Fend;
    public:
        inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
        inline void read(int& x)
        {
            x=0; char ch; while (!isdigit(ch=tc()));
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
        }
        inline void read_string(std::string& s)
        {
            char ch; while (isalpha(ch=tc())) s+=ch;
        }
        inline void write_string(const std::string& s)
        {
            for (auto ch:s) pc(ch);
        }
        inline void flush(void)
        {
            fwrite(Fout,1,Ftop-Fout,stdout);
        }
}F;

struct vivi {
    int a[26];
    inline int& operator[](const size_t i) { return a[i]; }
    vivi () { memset(a, 0, sizeof(a)); }
    // inline vivi& operator += (const vivi& b) const { for(int i = 0; i < 26; ++i) a[i] += b[i]; }
    // inline vivi& operator -= (const vivi& b) const { for(int i = 0; i < 26; ++i) a[i] -= b[i]; }
    // inline vivi& operator %= (const vivi& b) const { for(int i = 0; i < 26; ++i) a[i] %= b[i]; }
    
    // inline bool less(const vivi& b) const { 
    //     for(int i = 0; i < 26; ++i) if(a[i] < b[i]) return true;
    //     return true;
    // }
};

std::vector<vivi> hkr;
std::vector<int> len;
std::vector<std::vector<std::pair<int, int>>> trim;

struct pqnode_t {
    int inner_value;
    inline bool operator <(const pqnode_t &b) const {
        return len[inner_value] < len[b.inner_value];
    }
};

std::priority_queue<pqnode_t> pq;
std::vector<pqnode_t> pqv;
std::vector<int> ending;

void work() {
#define NO() ({ F.write_string("NO\n"); return; })
    int n; F.read(n);

    hkr.assign(n, vivi());
    len.assign(n, 0);
    trim.assign(n, {});
    std::vector<std::string> ans(n);
    
    for(int i = 0; i < n; ++i) {
        F.read_string(ans[i]); len[i] = ans[i].size();
        for(auto c: ans[i]) hkr[i][c - 'a'] += 1;
    }

    while(pq.size()) pq.pop();
    pq.push({ n - 1 });

    for(int i = n - 2; i >= 0; --i) {
        while(pq.size()) {
            auto [top] = pq.top();    
            if(len[top] < len[i]) break;
            pq.pop();
            const int uu = len[top] / len[i];
            if(ans[i].size() >= 26) {
                for(int j = 0; j < 26; ++j) hkr[top][j] -= hkr[i][j] * uu;
                for(int j = 0; j < 26; ++j) if(hkr[top][j] < 0) NO();
            } else {
                for(auto c: ans[i]) if((hkr[top][c - 'a'] -= uu) < 0) NO();
            }
            len[top] -= uu * len[i];
            trim[top].push_back({i, uu});
            if(len[top]) pq.push({ top });
        }
        pq.push({ i });
    }

    pqv.clear();
    pqv.reserve(pq.size());
    while(pq.size()) pqv.push_back(pq.top()), pq.pop();

    std::string curAns = "";
    vivi curVivi;
    ending.assign(n, 0);

    std::reverse(pqv.begin(), pqv.end());
    for(auto [v]: pqv) {
        for(int i = 0; i < 26; ++i) {
            if(hkr[v][i] < curVivi[i]) NO();
            while(hkr[v][i] > curVivi[i]) {
                curAns += char('a' + i);
                curVivi[i] += 1;
            }
        }
        ending[v] = curAns.size();
    }

    F.write_string("YES\n");

    for(int i = 0; i < n; ++i) {
        ans[i].clear();
        for(auto [a, b]: trim[i]) while(b--) ans[i] += ans[a];
        for(int j = 0; j < ending[i]; ++j) ans[i] += curAns[j];
        F.write_string(ans[i]);
        F.write_string("\n");
    }

#undef NO
}

int main(void) {
    // std::ios::sync_with_stdio(false);
    int t; F.read(t);
    while(t--) work();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5588kb

input:

4
2
abc
abcd
4
bbcaa
cabb
acabbbb
a
3
ab
aab
bbaaaaab
3
ab
aab
bbaaaaaa

output:


result:

wrong output format Unexpected end of file - token expected (test case 1)