QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710060 | #8234. Period of a String | nowed | TL | 498ms | 18520kb | C++23 | 2.6kb | 2024-11-04 18:19:55 | 2024-11-04 18:19:57 |
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, M = 5e6 + 5;
struct node {
int len;
int c[26];
} a[N], re[N];
map<int, node> f;
char ans[M];
void solve() {
bool flag = 1;
int n;
f.clear();
memset(a, 0, sizeof(a));
cin >> n;
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 {
int cnt = 0;
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[++cnt] = now;
if (it == f.begin()) {
f.erase(it);
break;
} else f.erase(it);
}
if (!flag) break;
re[++cnt] = a[i];
rep(i, 1, cnt) if (f.find(re[i].len) == f.end()) f[re[i].len] = re[i];
else check(f[re[i].len], re[i]); }
last = a[i].len;
}
node now;
now.len = 0;
rep(i, 0, 25) now.c[i] = 0;
int k = 0;
for (auto it = f.begin(); it != f.end(); it++) {
check(it->second, now);
if (!flag) break;
rep(j, 0, 25) rep(s, now.c[j] + 1, it->second.c[j]) ans[++k] = j + 'a';
now = it->second;
}
if (!flag) {
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
{
rep(i, 1, k) cout << ans[i];
cout << endl;
rep(i, 2, n) {
int len = k;
rep(j, len + 1, a[i].len) ans[j] = ans[(j - 1) % len + 1];
rep(j, 1, a[i].len) cout << ans[j];
cout << endl;
k = a[i].len;
}
}
}
int main() {
// ios::sync_with_stdio(0); cin.tie(0);
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: 0ms
memory: 16208kb
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: 2ms
memory: 18152kb
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: 148ms
memory: 17272kb
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: 0
Accepted
time: 145ms
memory: 16776kb
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:
ok ok (100 test cases)
Test #5:
score: 0
Accepted
time: 144ms
memory: 17868kb
input:
100 1114 mmiceajjcjdemdhf c ccccccc cccccc cccccccccccccccccccccccccccccccccccccccc ccccccccc ccccccccc ccccccccccccccc ccccccccccccccccccccccccc cccccccccc ccc ccccccccccc ccccccccccccccccccccccccccccccc ccccccccc cccccc ccccccccccccccccccccccc ccccccccccccc ccc ccccccccccc ccccccccc cccccccccccccc...
output:
NO NO YES acgbacmikmfaaddehiibfjkacaaaaaabbbbbbcccccccccdddddeeeeeeeeeeeeefffffffgggggggghhhhhhiiiiiiiiijjjjjjjjkkkkkkklllllllmmmmm acgbacmikmfaaddehiibfjkac acgbacmikmfaaddehiibfjkacacgbacmikmfaaddehiibfjkacacgbacmikmfaaddehiibfjkacacgbacm acgbacmikmfaaddehiibfjkacacgbacmikmfaaddehiibfjkacacgbacmik...
result:
ok ok (100 test cases)
Test #6:
score: 0
Accepted
time: 143ms
memory: 17400kb
input:
100 512 tecvaycvrbprboqldxlzjmlbfxaseuomtjxenfyoxkmjqkifjpacqytpxmbxleryljfxeoghwfhcnhvimgkvdwjcwatlppmwbbygdbiyzvlrfqjmdnuioulrgmwfkutwgavesanvdzbypveznnvrddujscaekxauxwi nqmlelkfqrvjbwdlvtbzxkd kbdqfbqxqqvmkllqltebqmlrnxvxflkzedrmbwknzltfbllqllbwllwqrvkzmrdqlldvnfbkqxbdkewxrzbbndvfqrnfklllxxkvqkjf...
output:
YES vzxjrblkeqmvnftqbdkdllwaaaaaaaabbbbbbccccccdddddeeeeeeeffffffggggghhhiiiiijjjjjjjkkklllllmmmmmmmnnnnnoooooppppppqqrrrrrsssttttuuuuuuvvvvvvvwwwwwwxxxxxxxxyyyyyyyzzz vzxjrblkeqmvnftqbdkdllw vzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftq...
result:
ok ok (100 test cases)
Test #7:
score: 0
Accepted
time: 498ms
memory: 18520kb
input:
1000 379 hdiyyp ihy hyhyiih hiyh iyhhihihhyhy yhihhyyihhih h hhh h h hhhhh hhhh hhhhhhhhh hhhhhhhhhhhhh hhhhhhhhhhhhhhhhh hh hhh hhhhh hhhhhhhh hhhhhhhhhhhhhhhh hhh hhhhhhhh hhhhhhhhh h hhh hhhhhh hhhh hh hhhhhhhhhh hhhhhhh hh hhhhh hhhhhh hhhh h hh hh hh hh hhhhhhhhhhhhh hhhhh hhhh hhhhhh hhhh h hh...
output:
YES hiydpy hiy hiyhiyh hiyh hiyhhiyhhiyh hiyhhiyhhiyh h hhh h h hhhhh hhhh hhhhhhhhh hhhhhhhhhhhhh hhhhhhhhhhhhhhhhh hh hhh hhhhh hhhhhhhh hhhhhhhhhhhhhhhh hhh hhhhhhhh hhhhhhhhh h hhh hhhhhh hhhh hh hhhhhhhhhh hhhhhhh hh hhhhh hhhhhh hhhh h hh hh hh hh hhhhhhhhhhhhh hhhhh hhhh hhhhhh hhhh h hhhhhh ...
result:
ok ok (1000 test cases)
Test #8:
score: -100
Time Limit Exceeded
input:
10000 21 uiutbnjregblkwbpztgdbmahtlhe dtulrltbnbtlbggtwmteiwzbejzdlzbtbutiapwhnurumbnutkekbjehanphbhrn unt tnnntktntttttnttutnuuuuuunntuuuntununutnntuttunuutttntnuntnuuntuttunnuututuntuttntnunntuntnnuuttutunuunnunuutnuuutnutnutnnntntntunnttntuuttnnuunnnnuuutntn uttnnnntuuuutututtnttuutuuttnnnnntunnu...
output:
NO YES y y y y y YES kabhlmmszgklamrcgo kabhlmmszgklamrcgokabhlmmszgkl kabhlmmszgklamrcgokabhlmmszgklkabhlmmszgklamrcgokabhlmmszgklkabhlmmsz kabhlmmszgklamrcgokabhlmmszgklkabhlmmszgklamrcgokabhlmmszgklkabhlmmszkabhlmmszgklamrcgokabhlmmszgklkabhlmmszgklamrcgokabhlmmszgklkabhlmmszkabhlmmszgklamrcgokab...