제출 #389418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
389418		8e7	Binary Subsequences (info1cup17_binary)	C++14	100 / 100	687 ms	332 KiB

binary

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define ll long long
#define maxn 100005
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define pii pair<int, int>
using namespace std;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//template<lcass T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//find by order, order of key
int gcd(int x, int y) {
	return (x == 0 ? y : gcd(y % x, x));
}
int getnum(int x, int y) {
	return (x == 0 ? -1 : getnum(y % x, x) + y / x);
}
string getans(int x, int y) {
	string ret;
	while (max(x, y) != 1) {
		if (x > y) x -= y, ret += '0';
		else y -= x, ret += '1';
	}
	return ret;
}
int main() {
	io
	int t;
	cin >> t;
	while (t--) {
		int k;
		cin >> k;

		int cnt = 0, mv = 1<<30, mx = 0;
		for (int i = 1;i < (k + 2 - i);i++) {
			if (gcd(i, k + 2 - i) == 1) {
				cnt+=2;
				int val = getnum(i, k + 2 - i);
				if (val < mv) {
					mv = val;
					mx = i;
				}
			}

		}
		cout << cnt << "\n";
		string ret = getans(mx, k + 2 - mx);
		for (char i:ret) cout << i << " ";
		cout << "\n";
	}
}

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