Submission #1140856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140856		tkm_algorithms	Binary Subsequences (info1cup17_binary)	C++20	100 / 100	698 ms	436 KiB

binary

/**
*    In the name of Allah
*    We are nothing and you're everything
*    author: najmuddin
**/
 
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("trapv")
//#pragma GCC optimize("inline")
using namespace std;
 
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
 
const char nl = '\n';
const int N = 1e8+5;
//const int inf = 1e18;
const int mod = 1e9+7;

int calc(int a, int b) {
	if (a == b) {
		if (a > 0)return -mod;
		return 0;
	}
	
	int div = (a > b?a/(b+1):b/(a+1));
	if (a > b)a -= div*(b+1);
	else b -= div*(a+1);
	return div+calc(a, b);
}

void printres(int a, int b) {
	if (a == b)return;
	if (a > b)cout << 0 << ' ';
	if (b > a)cout << 1 << ' ';
	if (a > b)printres(a-b-1, b);
	else printres(a, b-a-1);
}

void solve() {
	int k; cin >> k;
	
	int cnt = 0;
	pair<int, int> ans = {mod, 0};
	for (int a = 0; a <= k; ++a) {
		int tmp = calc(a, k-a);
		if (tmp >= 0)ans = min(ans, {tmp, a}), cnt += 1;
	}
	
	cout << cnt << nl;
	printres(ans.second, k-ans.second);
	cout << nl;
}
 
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	
	int t = 1;
	cin >> t;
	
	while (t--) {
		solve();
	}
    return 0;
}

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