oj.uz

Submission #67995

# Submission time Handle Problem Language Result Execution time Memory
67995 2018-08-15T17:07:10 Z MrTEK Binary Subsequences (info1cup17_binary) C++14
100 / 100
 654 ms 664 KB 
#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

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.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 376 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 376 KB Output is correct
2 Correct 56 ms 584 KB Output is correct
3 Correct 56 ms 584 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 584 KB Output is correct
2 Correct 654 ms 664 KB Output is correct
3 Correct 641 ms 664 KB Output is correct