QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#654430 | #8234. Period of a String | Tomorrow | WA | 97ms | 5460kb | C++17 | 2.1kb | 2024-10-18 21:33:42 | 2024-10-18 21:33:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define C const
#define OP operator
#define pb push_back
#define ft first
#define sd second
#define TTT template<typename T = I>
#define BE(v) v.begin(), v.end()
#define VD void
#define I int
#define STR string
using PII = pair<I, I>;
TTT using V = vector<T>;
#define FORX(v) for(auto& x : v)
#define FOR(i, b, e) for(auto i = b, _e = (decltype(i))e;i != _e; ++i)
#define FORR(i, b, e) for(auto i = b, _e = (decltype(i))e;i != _e; --i)
#define FUNC(T, f, ...) function<T(__VA_ARGS__)> f = [&](__VA_ARGS__)->T
TTT VD setmin(T& a, C T& b) { if (b < a)a = b; }
TTT VD setmax(T& a, C T& b) { if (a < b)a = b; }
struct Lim
{
V<I> s;
bool OP < (C Lim& _)C { return s.size() < _.s.size(); }
};
VD test()
{
I n;cin >> n;
V<V<I>> ss(n);
V<V<I>> cnt(n, V<I>(26));
multiset<Lim> lim;
V<STR> ans(n);
FOR(i, 0, n)
{
STR str;cin >> str;ss[i].resize(str.size());
FOR(j, 0, str.size())cnt[i][ss[i][j] = str[j] - 'a']++;
}
FORR(i, n - 1, 0)
{
lim.insert({ ss[i] });
for (auto it = --lim.end();it->s.size() >= ss[i - 1].size();it = --lim.end())
{
V<I> s = it->s; Lim nl;
lim.erase(it);
if (s.size() == 0)continue;
I tm = s.size() / ss[i - 1].size();
V<I> c(26);
FORX(s)c[x]++;
FORX(ss[i - 1])c[x] -= tm;
FOR(j, 0, 26)
{
if (c[j] < 0 || c[j] > cnt[i - 1][j])
{
cout << "NO\n";
return;
}
while (c[j]--)nl.s.pb(j);
}
lim.insert(nl);
}
}
lim.insert({ ss[0] });
V<I> cur(26);
FORX(lim)
{
V<I> c(26);
for (auto& y : x.s)c[y]++;
FOR(i, 0, 26)
{
while (cur[i] < c[i])
{
++cur[i]; ans[0].pb(i + 'a');
if (cur[i] > cnt[0][i])
{
cout << "NO\n";
return;
}
}
}
}
FOR(i, 1, n)
{
FOR(j, 0, ss[i].size())ans[i].pb(ans[i - 1][j % ss[i - 1].size()]);
}
cout << "YES\n";
FORX(ans)cout << x << '\n';
}
I main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
if (fopen("test.in", "r"))
{
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
}
I t = 1;
cin >> t;
while (t--)test();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3776kb
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: 3556kb
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: 97ms
memory: 5460kb
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 47)