QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#654318#8234. Period of a StringTomorrowWA 71ms5272kbC++172.2kb2024-10-18 21:24:342024-10-18 21:24:35

Judging History

你现在查看的是最新测评结果

  • [2024-10-18 21:24:35]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:5272kb
  • [2024-10-18 21:24:34]
  • 提交

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));
	set<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); I m = 0;
	FORX(lim)
	{
		V<I> c(26);
		for (auto& y : x.s)c[y]++;
		FOR(i, 0, 26)
		{
			while (cur[i] < c[i])
			{
				++cur[i], ++m; ans[0].pb(i + 'a');
				if (cur[i] > cnt[0][i])
				{
					cout << "NO\n";
					return;
				}
			}
		}
	}
	assert(m == ss[0].size());


	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: 3704kb

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: 3576kb

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: 71ms
memory: 5272kb

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)