Submission #1148246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148246		stdfloat	Binary Subsequences (info1cup17_binary)	C++20	100 / 100	757 ms	3340 KiB

binary

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

using ll = long long;

void solve() {
	int k;
	cin >> k;

	string ans;
	int cnt = 0;
	for (int i = 0; i <= k; i++) {
		int x = i, y = k - i, sz = 0;
		while (x || y) {
			if (x > y) {
				sz += x / (y + 1);
				x %= (y + 1);
			}
			else if (x < y) {
				sz += y / (x + 1);
				y %= (x + 1);
			}
			else {
				sz = -1;
				break;
			}
		}

		if (~sz) {
			cnt++;
			if (ans.empty() || sz < (int)ans.size()) {
				ans.clear();
				x = i; y = k - i;
				while (x || y) {
					if (x > y) {
						for (int i = 0; i < x / (y + 1); i++)
							ans += '1';

						x %= (y + 1);
					}
					else if (x < y) {
						for (int i = 0; i < y / (x + 1); i++)
							ans += '0';

						y %= (x + 1);
					}
				}
			}
		}
	}

	cout << cnt << '\n';
	for (auto i : ans)
		cout << i << ' ';
	cout << '\n';
}

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

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

• Subtask 1: 43 / 43
• Subtask 2: 39 / 39
• Subtask 3: 18 / 18