QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#708259 | #8234. Period of a String | lmcg | WA | 1ms | 5588kb | C++20 | 3.9kb | 2024-11-03 20:50:30 | 2024-11-03 20:50:30 |
Judging History
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)