Submission #67996

#	Time	Username	Problem	Language	Result	Execution time	Memory
67996		cdemirer	Binary Subsequences (info1cup17_binary)	C++17	100 / 100	673 ms	600 KiB

binary

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef pair<double, double> dodo;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define INF 1000000000

int N;
string out;

void func2(int a, int b) {
	if (a == 0 || b == 0) return;
	if (a < b) {
		int k = b/a;
		for (int i = 0; i < k; i++) out += "1 ";
		func2(a, b%a);
	} else {
		int k = a/b;
		for (int i = 0; i < k; i++) out += "0 ";
		func2(a%b, b);
	}
}

int func(int a, int b) {
	if (a == 0) {
		if (b == 1) return 0;
		else return INF;
	}
	if (b == 0) {
		if (a == 1) return 0;
		else return INF;
	}
	if (a < b) {
		return b/a + func(a, b%a);
	} else {
		return a/b + func(a%b, b);
	}
}

int main(int argc, char **argv) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		out = "";
		int x; cin >> x;
		int cnt = 0;
		int best = 1000000000;
		int bestj = 1;
		for (int j = 1; j <= (x+2)/2; j++) {
			int res = func(j, x+2-j);
			if (res < INF) {
				cnt++;
				if (res < best) {
					best = res;
					bestj = j;
				}
			}
		}
		cout << 2*cnt << '\n';
		out = "";
		func2(bestj, x+2-bestj);
		cout << out.substr(0, out.length()-2) << '\n';
	}
	

	return 0;
}

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