oj.uz

Submission #67996

# Submission time Handle Problem Language Result Execution time Memory
67996 2018-08-15T17:20:53 Z cdemirer Binary Subsequences (info1cup17_binary) C++17
100 / 100
 673 ms 600 KB 
#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.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 376 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 376 KB Output is correct
2 Correct 58 ms 432 KB Output is correct
3 Correct 59 ms 568 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 568 KB Output is correct
2 Correct 673 ms 600 KB Output is correct
3 Correct 653 ms 600 KB Output is correct