oj.uz

Submission #46052

# Submission time Handle Problem Language Result Execution time Memory
46052 2018-04-17T04:21:07 Z aome Binary Subsequences (info1cup17_binary) C++17
100 / 100
 665 ms 608 KB 
#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

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.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 376 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 376 KB Output is correct
2 Correct 58 ms 412 KB Output is correct
3 Correct 56 ms 428 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 480 KB Output is correct
2 Correct 665 ms 480 KB Output is correct
3 Correct 650 ms 608 KB Output is correct