Submission #1143101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143101		Agageldi	Binary Subsequences (info1cup17_binary)	C++17	100 / 100	578 ms	328 KiB

binary

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 600005
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sz(s) (int)s.size()

ll T, n, a[N], t, b[25];
map <string,int> vis;

int main () {
	cin >> n;
	while(n--) {
		cin >> t;
		int ans = t + 1, ans1 = t + 1, bb = 0;
		for(int i = 0; i <= t;i++) {
			int x1 = t - i, x2 = i, new_sz = 0;
			while(x1 != x2) {
				if(x1 > x2) {
					new_sz += (x1/(x2 + 1));
					x1 = (x1 % (x2+1));
				}
				else {
					new_sz += (x2/(x1 + 1));
					x2 = x2%(x1+1);
				}
			}
			if(x1 == 0 && x2 == 0 && new_sz < ans) {
				ans = new_sz;
				bb = i;
			}
			if(x1 > 0 || x2 > 0) ans1--;
		}
		int x1 = t - bb, x2 = bb, new_sz = 0;
		cout << ans1 << '\n';
		while(x1 != x2) {
			if(x1 > x2) {
				for(int i= 1;i<=x1 / (x2 + 1); i++) {
					cout << '1' << " ";
				}
				x1 = x1%(x2 + 1);
				continue;
			}
			for(int i = 1; i <= x2 / (x1+1); i++) {
				cout << '0' << " ";
			}
			x2 = (x2 % (x1 + 1));
		}
		cout << '\n';
	}
}

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