Submission #410687

#	Time	Username	Problem	Language	Result	Execution time	Memory
410687		nichke	Binary Subsequences (info1cup17_binary)	C++14	0 / 100	747 ms	352 KiB

binary

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

int n;

int f(int x, int y) {
	int res = 0;
	while (y) {
		res += x / y;
		x = x % y;
		swap(x, y);
	}
	if (x != 1) return 0x3f;
	return res;
}

void print(int x, int y) {
	string s = "";
	while (x != y) {
		if (x > y) {
			s += '0';
			x -= y + 1;
		} else {
			s += '1';
			y -= x + 1;
		}
	}
	int len = s.length();
	for (int i = len - 1; i >= 0; i--) {
		cout << s[i] << ' ';
	}
	cout << '\n';
}

void solve() {
	int cnt = 0, mn = 0x3f, ind;
	for (int i = 0; i <= n; i++) {
		int val = f(i + 1, n + 1 - i);
		if (val < 0x3f) cnt++;
		if (val < mn) {
			mn = val;
			ind = i;
		}
	}
	cout << cnt << endl;
	print(ind, n - ind);
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t; cin >> t;
	while (t--) {
		cin >> n;
		solve();
	}
	return 0;
}

Compilation message (stderr)

binary.cpp: In function 'void solve()':
binary.cpp:48:7: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |  print(ind, n - ind);
      |  ~~~~~^~~~~~~~~~~~~~

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