Submission #67992

#	Time	Username	Problem	Language	Result	Execution time	Memory
67992		hamzqq9	Binary Subsequences (info1cup17_binary)	C++14	100 / 100	676 ms	652 KiB

binary

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000000
#define MOD 1000000007
#define N 100003
#define MAX 10000006
#define LOG 30
using namespace std;

int n,t,sz;
bool res[N];

int exg(int x,int y) {

	int step=0;

	while(x>0) {

		step+=y/x;

		y%=x;

		swap(x,y);

	}

	return step-1+(y!=1)*inf;

}

void solve(int n) {

	int k=n+2;
	int ans=0;
	int best=inf;
	int x,y;

	for(int i=1;i<=k/2;i++) {

		int step=exg(i,k-i);

		if(step<inf) {

			++ans;

			if(step<best) {

				best=step;

				x=i,y=k-i;

			}


		}
	
	}

	printf("%d\n",ans*2);

	int tur=0;

	while(x>0) {

		for(int i=1;i<=y/x;i++) res[sz++]=tur;

		y%=x;

		swap(x,y);

		tur^=1;

	}

	sz--;

	while(sz) {--sz;putchar('0'+res[sz]);putchar(' ');}

	puts("");

}

int main() {

	//freopen("input.txt","r",stdin);

	scanf("%d",&t);

	while(t--) {

		scanf("%d",&n);

		solve(n);

	}

}

Compilation message (stderr)

binary.cpp: In function 'int main()':
binary.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&t);
  ~~~~~^~~~~~~~~
binary.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
binary.cpp: In function 'void solve(int)':
binary.cpp:50:8: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int x,y;
        ^
binary.cpp:50:6: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int x,y;
      ^

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