제출 #1161527

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161527		xnqs	Nice sequence (IZhO18_sequence)	C++20	0 / 100	6 ms	5128 KiB

sequence

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

void solve() {
	int n, m;
	std::cin >> n >> m;
	
	int len = n + m - 1 - std::__gcd(n, m);
	if (!len) {
		std::cout << "0\n";
		return;
	}

	std::vector<std::vector<int>> adj_list;
	adj_list.resize(n+m+1);

	std::vector<int> deg(400005, 0);
	std::vector<int> node_val(400005, 0);
	for (int i = n; i <= len; i++) {
		adj_list[i].emplace_back(i-n);
		++deg[i-n];
	}
	for (int i = m; i <= len; i++) {
		adj_list[i-m].emplace_back(i);
		++deg[i];
	}

	std::queue<int> q;
	for (int i = 0; i < len; i++) {
		if (!deg[i]) {
			q.emplace(i);
		}
	}

	int cnt = 0;
	while (!q.empty()) {
		int k = q.front();
		q.pop();
		node_val[k] = ++cnt;
		
		for (const auto& i : adj_list[k]) {
			--deg[i];
			if (!deg[i]) {
				q.emplace(i);
			}
		}
	}

	std::cout << len << "\n";
	for (int i = 1; i <= len; i++) {
		std::cout << (node_val[i] - ((i-1>=0) ? node_val[i-1] : 0)) << " ";
	}
	std::cout << "\n";
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int t;
	std::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