Submission #67995

#	Time	Username	Problem	Language	Result	Execution time	Memory
67995		MrTEK	Binary Subsequences (info1cup17_binary)	C++14	100 / 100	654 ms	664 KiB

binary

#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left ind+ind
#define right ind+ind+1
#define mid (l+r)/2
#define FAST_IO ios_base::sync_with_stdio(false);
#define endl '\n'

typedef long long int ll;

const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 2e3 + 5;
const int M = 25;
const int SQ = 350;
const int MOD = 998244353;

typedef pair <int,int> pii;

int t;

int main() {

	scanf("%d",&t);

	while(t--) {
		int k,ans = 0,ans2 = 0,mn = INF;
		scanf("%d",&k);
		k += 2;
		for (int i = 1 ; i <= k / 2 ; i++) {
			int x = i, y = k - i,cnt =0;
			while(x && y) {
				if (x > y) {
					cnt += x/y ;
					x %= y;
				}
				else {
					cnt += y/x ;
					y %= x; 
				}
			}
			if (max(x,y) == 1) {
				ans++;
				if (mn > cnt) {
					mn = cnt;
					ans2 = i;
				}
			}
		}
		printf("%d\n",ans + ans);
		int x = ans2 , y = k - ans2;
		vector <int> write;
		while ( x != y) {
			if (x > y) x -= y,write.pb(1);
			else y -= x,write.pb(0);
		}
		for (int i = len(write) - 1 ; i >= 0 ; i--) printf("%d ",write[i]);
		puts("");
	}

	return 0 ;
}

Compilation message (stderr)

binary.cpp: In function 'int main()':
binary.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&t);
  ~~~~~^~~~~~~~~
binary.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&k);
   ~~~~~^~~~~~~~~

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