oj.uz

Submission #410690

# Submission time Handle Problem Language Result Execution time Memory
410690 2021-05-23T11:44:10 Z nichke Binary Subsequences (info1cup17_binary) C++14
100 / 100
 756 ms 324 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e9 + 7;

int n;

int f(int x, int y) {
	int res = 0;
	while (y != 0) {
		res += x / y;
		x = x % y;
		swap(x, y);
	}
	if (x != 1) return INF;
	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 << endl;
}

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

signed main() {
	int t; cin >> t;
	while (t--) {
		cin >> n;
		solve();
	}
	return 0;
}

Compilation message

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

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 324 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 204 KB Output is correct
2 Correct 65 ms 204 KB Output is correct
3 Correct 62 ms 304 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 204 KB Output is correct
2 Correct 756 ms 204 KB Output is correct
3 Correct 743 ms 324 KB Output is correct