제출 #1133159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133159		stdfloat	Nice sequence (IZhO18_sequence)	C++20	76 / 100	2058 ms	45808 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, int z) {
	if (~p[x]) return p[x];

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

	return p[x];
}

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

	int l = 0, r = n + m - __gcd(n, m);
	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);
	}

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

	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: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 0 / 24