Submission #1143049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143049		Muhammet	Binary Subsequences (info1cup17_binary)	C++20	100 / 100	706 ms	436 KiB

binary

#include "bits/stdc++.h"

using namespace std;

#define SZ(s) (int)s.size()
#define ff first
#define ss second
#define ll long long

const int N = 1e3 + 5;
const ll M = 1000000007;

ll T, n, k, cnt;

bool tr;

int f(ll a, ll b){
	if(a == b){
		if(a) return 0;
		return 1;
	}
	if(a < b) swap(a, b);
	cnt += a/(b+1);
	return f(a%(b+1), b);
}

void f1(int a, int b, int x, int y){
	if(a == b) return;
	if(a < b) swap(a, b), swap(x, y);
	cout << x << ' ';
	f1(a-(b+1), b, x, y);
}

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

	cin >> T;
	while(T--){
		cin >> n;
		int ans = 0, k = 1e9, a1, b1;
		for(int i = 0; i <= n; i++){
			int a = i, b = (n-i);
			cnt = 0;
			int tr = f(a, b);
			ans += tr;
			if(tr == 1 and cnt < k){
				k = cnt;
				a1 = a, b1 = b;
			}
		}
		cout << ans << '\n';
		f1(a1, b1, 0, 1);
		cout << '\n';
	}

	return 0;
}

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