Submission #1133154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133154		stdfloat	Nice sequence (IZhO18_sequence)	C++20	0 / 100	0 ms	328 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<int> cl, p;

vector<vector<int>> E;

bool dfs(int x) {
	cl[x] = 1;
	for (auto i : E[x])
		if (cl[i] == 1 || (!cl[i] && dfs(i))) return true;

	cl[x] = 2;
	return false;
}

int dfs1(int x) {
	if (~p[x]) return p[x];

	p[x] = 1;
	for (auto i : E[x])
		p[x] = max(p[x], dfs1(i) + 1);

	return p[x];
}

void solve() {
	int n, m;
	cin >> n >> m;

	int l = 0, r = max(n, m) << 1;
	while (l <= r) {
		int md = (l + r) >> 1;

		E.assign(md + 1, {});
		for (int i = 1; i <= md; i++) {
			if (n <= i) E[i].push_back(i - n);
			if (m <= i) E[i - m].push_back(i);
		}

		bool tr = false;
		cl.assign(md + 1, 0);
		for (int i = 0; i <= md && !tr; i++)
			if (!cl[i]) tr = dfs(i);

		if (!tr) l = md + 1;
		else r = md - 1;
	}

	E.assign(l, {});
	for (int i = 1; i < l; i++) {
		if (n <= i) E[i - n].push_back(i);
		if (m <= i) E[i].push_back(i - m);
	}

	p.assign(l, -1);
	for (int i = 0; i < l; i++)
		if (!~p[i]) dfs1(i);

	cout << l - 1 << '\n';
	for (int i = 1; i < l; i++)
		cout << p[i] - (i ? p[i - 1] : 0) << " \n"[i + 1 == l];
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int T;
	cin >> T;
	while (T--) solve();
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24