제출 #1140857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140857		tkm_algorithms	Binary Subsequences (info1cup17_binary)	C++20	100 / 100	698 ms	452 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;
	
	int div = (a > b?a/(b+1):b/(a+1));
	for (int i = 0; i < div; ++i)
		cout << (a > b?0:1) << ' ';
	
	if (a > b)a -= div*(b+1);
	else b -= div*(a+1);
	
	printres(a, b);
}

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