oj.uz

Submission #389418

# Submission time Handle Problem Language Result Execution time Memory
389418 2021-04-14T04:06:14 Z 8e7 Binary Subsequences (info1cup17_binary) C++14
100 / 100
 687 ms 332 KB 
//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.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 332 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 308 KB Output is correct
2 Correct 53 ms 292 KB Output is correct
3 Correct 50 ms 204 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 296 KB Output is correct
2 Correct 687 ms 292 KB Output is correct
3 Correct 622 ms 292 KB Output is correct