QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#684204 | #8234. Period of a String | Grand_Elf | WA | 34ms | 15704kb | C++17 | 3.1kb | 2024-10-28 11:16:51 | 2024-10-28 11:16:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 5e6 + 5;
int T, n, bn, tot, m[N], b[N], c[N], id[N], pre[N], vis[M];
string sans, nans, s[N];
struct A {
int v[26];
} cnt[N], ans[N];
A operator + (const A &a, const A &b) {
A c;
for (int j = 0; j < 26; j++) {
c.v[j] = a.v[j] + b.v[j];
}
return c;
}
A operator - (const A &a, const A &b) {
A c;
for (int j = 0; j < 26; j++) {
c.v[j] = a.v[j] - b.v[j];
}
return c;
}
A operator * (const A &a, const int &b) {
A c;
for (int j = 0; j < 26; j++) {
c.v[j] = a.v[j] * b;
}
return c;
}
bool operator == (const A &a, const A &b) {
for (int j = 0; j < 26; j++) {
if (a.v[j] != b.v[j]) {
return 0;
}
}
return 1;
}
void add(int x, int v) {
for (; x <= bn; x += x & -x) {
id[x] = max(id[x], v);
}
}
int query(int x) {
int res = 0;
for (; x; x -= x & -x) {
res = max(res, id[x]);
}
return res;
}
void work() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
m[i] = s[i].size();
for (int j = 0; j < 26; j++) {
cnt[i].v[j] = 0;
}
for (char c : s[i]) {
int j = c - 'a';
cnt[i].v[j]++;
}
b[i] = m[i];
}
sort(b + 1, b + n + 1);
bn = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++) {
c[i] = lower_bound(b + 1, b + bn + 1, m[i]) - b;
}
for (int i = 1; i <= bn; i++) {
id[i] = 0;
}
for (int i = 1; i <= n; i++) {
add(c[i], i);
pre[i] = query(c[i] - 1);
}
tot = 0;
for (int i = 1; i <= m[1]; i++) {
vis[i] = 0;
}
for (int i = 2; i <= n; i++) {
int l = m[i], j = pre[i];
while (j > 0 && l > 0) {
l %= m[j];
j = pre[j];
}
if (j == 0) {
l = m[i], j = pre[i];
A now = cnt[i];
while (j > 0 && l > 0) {
now = now - cnt[j] * (l / m[j]);
l %= m[j];
j = pre[j];
}
if (l == 0) {
for (int x = 0; x < 26; x++) {
if (now.v[x] != 0) {
cout << "NO\n";
return;
}
}
continue;
}
if (!vis[l]) {
vis[l] = ++tot;
ans[tot] = now;
} else {
int k = vis[l];
if (!(ans[k] == now)) {
cout << "NO\n";
return;
}
}
}
}
sans = "";
for (int i = 1, j = 0; i <= m[1]; i++) {
if (vis[i]) {
int k = vis[i];
A now = j > 0 ? ans[k] - ans[vis[j]] : ans[k];
for (int x = 0; x < 26; x++) {
int t = now.v[x];
if (t < 0) {
cout << "NO\n";
return;
}
while (t--) {
sans += x + 'a';
}
}
j = i;
} else if (i == m[1]) {
A now = j > 0 ? cnt[1] - ans[vis[j]] : cnt[1];
for (int x = 0; x < 26; x++) {
int t = now.v[x];
if (t < 0) {
cout << "NO\n";
return;
}
while (t--) {
sans += x + 'a';
}
}
}
}
cout << "YES\n";
for (int i = 1; i < n; i++) {
cout << sans << '\n';
string nans = "";
for (int j = 0; j < m[i + 1]; j++) {
nans += sans[j % m[i]];
}
sans = nans;
}
cout << sans << '\n';
}
int main() {
int st = clock();
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while (T--) {
work();
}
cerr << (double)(clock() - st) / CLOCKS_PER_SEC << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12280kb
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: 12120kb
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: 34ms
memory: 15704kb
input:
100 147 ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...
output:
NO YES baaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb ba bababababababababababababababababababababab bababababababababababababababab babababab bababababbababababb bababababbabab baba bababababababab b bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb b bbbbbbbbbbbbbb bbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbbbbbbb bbbbbbbb...
result:
wrong answer Number of letters do not same (test case 16)