QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#684204#8234. Period of a StringGrand_ElfWA 34ms15704kbC++173.1kb2024-10-28 11:16:512024-10-28 11:16:53

Judging History

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

  • [2024-10-28 11:16:53]
  • 评测
  • 测评结果:WA
  • 用时:34ms
  • 内存:15704kb
  • [2024-10-28 11:16:51]
  • 提交

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)