oj.uz

Submission #649558

# Submission time Handle Problem Language Result Execution time Memory
649558 2022-10-10T13:19:03 Z dozer Binary Subsequences (info1cup17_binary) C++17
82 / 100
 900 ms 2688 KB 
#include <bits/stdc++.h>
//#include "c2.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 int long long
#define N 100005


const int INF = 1e9 + 7;
vector<int> opt[N];

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

inline void print2(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';
	print2(j, i % j, 1 - turn, s);
}

void solve(int k)
{
	pii tmp;
	int mini = INF, res = 0;
	k += 2;
	for (int j = 1; j < k; j++)
	{
		int l = k - j;
		if (gcd(j, l) != 1) continue;
		res++;
		int gh = newgcd(l, j);
		if (mini > gh)
		{
			mini = gh;
			tmp = {j, l};
		}
	}
	//cout<<k<<sp<<tmp.st<<sp<<tmp.nd<<endl;
	//opt[tmp.st].pb(tmp.nd);
	//opt[tmp.nd].pb(tmp.st);
	
	cout<<res<<endl;
	string s;
	print2(tmp.st, tmp.nd, 0, s);
	for (auto i : s) cout<<i<<sp;
	cout<<endl;
	
}

int32_t main()
{
	//fileio();
	fastio();

	int t;
	cin>>t;

	while(t--)
	{
		int k;
		cin>>k;
		solve(k);
	}
	
	
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 2644 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2688 KB Output is correct
2 Correct 90 ms 2652 KB Output is correct
3 Correct 87 ms 2648 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 934 ms 2648 KB Time limit exceeded
2 Halted 0 ms 0 KB -