Submission #649464

#	Time	Username	Problem	Language	Result	Execution time	Memory
649464		dozer	Binary Subsequences (info1cup17_binary)	C++17	0 / 100	1002 ms	4628 KiB

binary

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define int long long

const int INF = 1e9 + 7;

int newgcd(int a, int b)
{
	if (a < b) swap(a, b);
	if (b == 1) return a - 1;
	return gcd(b, a % b) + a / b;
}

void print(int i, int j, int turn, string &s)
{
	if (i < j) swap(i, j);
	if (j == 1)
	{
		for (int k = 1; k < i; k++) s += (char)turn + '0';
		return;
	}
	for (int k = 0; k < i / j; k++)
		s += (char)turn + '0';
	print(j, i % j, 1 - turn, s);
}


int32_t main()
{
	fastio();

	int t;
	cin>>t;
	for (int i = 1; i <= t; i++)
	{
		int k;
		cin>>k;
		k += 2;
		int ans = 0;
		pii tmp;
		int mini = INF;
		for (int j = 1; j < k; j++)
		{
			int l = k - j;
			if (gcd(j, l) != 1) continue;
			ans++;
			int gh = newgcd(l, j);
			if (mini > gh)
			{
				mini = gh;
				tmp = {j, l};
			}
		}
		cout<<-1<<endl;
		string s;
		print(tmp.st, tmp.nd, 0, s);
		reverse(s.begin(), s.end());
		for (auto i : s) cout<<i<<sp;
		cout<<endl;
	}
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

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