Submission #46052

#	Time	Username	Problem	Language	Result	Execution time	Memory
46052		aome	Binary Subsequences (info1cup17_binary)	C++17	100 / 100	665 ms	608 KiB

binary

#include <bits/stdc++.h>

using namespace std;

int n;

void solve() {
	cin >> n;
	int cnt = 2;
	int minLen = n;
	pair<int, int> state = {0, n};
	for (int i = 1; i < (n + 1) / 2; ++i) {
		pair<int, int> cur = {i, n - i};
		int curLen = 0; 
		while (cur.first != cur.second) {
			if (cur.first > cur.second) {
				curLen += cur.first / (cur.second + 1);
				cur.first %= cur.second + 1; 
			}
			else {
				curLen += cur.second / (cur.first + 1);
				cur.second %= cur.first + 1;
			}
		}
		// cout << cur.first << ' ' << cur.second << ' ' << curLen << '\n';
		if (!cur.first) cnt += 2;
		if (curLen < minLen && !cur.first) {
			minLen = curLen, state = {i, n - i};
		}
	}
	vector<int> vec;
	pair<int, int> cur = state;
	while (cur.first != cur.second) {
		if (cur.first > cur.second) {
			cur.first -= cur.second + 1;
			vec.push_back(0);
		}
		else {
			cur.second -= cur.first + 1;
			vec.push_back(1);
		}
	}
	reverse(vec.begin(), vec.end());
	cout << cnt << '\n';
	for (auto i : vec) cout << i << ' '; cout << '\n'; 
}

int main() {
	ios::sync_with_stdio(false);
	int t; cin >> t; while (t--) solve();
}

Compilation message (stderr)

binary.cpp: In function 'void solve()':
binary.cpp:45:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (auto i : vec) cout << i << ' '; cout << '\n'; 
  ^~~
binary.cpp:45:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (auto i : vec) cout << i << ' '; cout << '\n'; 
                                       ^~~~

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