QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#709578 | #8234. Period of a String | nowed | WA | 149ms | 14380kb | C++23 | 2.9kb | 2024-11-04 15:35:21 | 2024-11-04 15:35:25 |
Judging History
answer
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#define endl '\n'
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;
const int N = 1e5 + 5;
struct node {
int len;
int c[26];
} a[N];
map<int, node> f;
vector<node> re;
void solve() {
bool flag = 1;
int n;
cin >> n;
auto init = [&]() {
f.clear();
memset(a, 0, sizeof(a));
};
init();
rep(i, 1, n) {
string s;
cin >> s;
int len = s.size();
a[i].len = len;
rep(j, 0, len - 1) a[i].c[s[j] - 'a']++;
}
int last = 0;
auto check = [&](node A, node B) {
rep(i, 0, 25) if (A.c[i] < B.c[i]) {
flag = 0;
return;
}
return;
};
for (int i = n; i >= 1; i--) {
if (a[i].len > last) f[a[i].len] = a[i];
else {
re.clear();
for (auto it = --f.end();; it = --f.end()) {
if (it->second.len <= a[i].len) break;
node now;
now.len = it->second.len % a[i].len;
int x = it->second.len / a[i].len;
rep(j, 0, 25) {
now.c[j] = it->second.c[j] - a[i].c[j] * x;
if (now.c[j] < 0) flag = 0;
}
if (!flag) break;
re.push_back(now);
if (it == f.begin()) {
f.erase(it);
break;
} else f.erase(it);
}
if (!flag) break;
re.push_back(a[i]);
for (auto it = re.begin(); it != re.end(); it++)
if (f.find(it->len) == f.end()) f[it->len] = *it;
else check(f[it->len], *it);
}
last = a[i].len;
}
for (auto it = f.begin(); it != f.end(); it++)
if (it != f.begin()) check(it->second, f.begin()->second);
if (!flag) {
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
vector<char> ans;
int Ans[26];
ans.clear();
memset(Ans, 0, sizeof(Ans));
{
for (auto it = f.begin(); it != f.end(); it++) rep(j, 0, 25) {
while (Ans[j] < it->second.c[j]) {
ans.push_back(j + 'a');
Ans[j]++;
}
}
}
{
for (auto it = ans.begin(); it != ans.end(); it++) cout << *it;
cout << endl;
vector<char> Last = ans;
rep(i, 2, n) {
ans.clear();
int len = Last.size();
rep(j, 1, a[i].len) ans.push_back(Last[(j - 1) % len]);
for (auto it = ans.begin(); it != ans.end(); it++) cout << *it;
cout << endl;
Last = ans;
}
}
}
int main() {
int T;
cin >> T;
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 14092kb
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: 4ms
memory: 14380kb
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: 0
Accepted
time: 149ms
memory: 14252kb
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:
ok ok (100 test cases)
Test #4:
score: -100
Wrong Answer
time: 149ms
memory: 14208kb
input:
100 326 decadadcaaacaaeecaddaeadeadc aaadedcaaeaaeddddaeaceaddaaaaecccaaeadeaaedaccdddcdddaaaadddacceaaadcadaeeeadeeadccdaacadaaecaedadcaaaecdaddaeaaaeccdedaceaaaacdddcecdcdacddccecaaaeaeedacaeaadaaacdadedae acaecaaaedcdaceaaddddaaeaddccdaeaadaeedaecdacaadeeaadeceadacdadaccdaaedaddccaceea ddccacdcea...
output:
NO YES ebccdeabb ebccde ebccd ebccdebccdebccdebccd ebccde e eeeeeeeeeeeeeeeee eeeeeeeeeeee eeeeeee eeeeeeeeeeeee eee eeeeeeeeeeeeeeee eeeeeeeeeeeeee eeeeeeeeeeeeeeeeeeee eeeeeeeeeee eeeeeeeeeeeeeeeeeeeee eeeeeeeeeeeeeeeeeee eeeeeeeeeeee eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee eeeeeeeeee eee...
result:
wrong answer Number of letters do not same (test case 71)