oj.uz

Submission #67986

# Submission time Handle Problem Language Result Execution time Memory
67986 2018-08-15T16:40:47 Z hamzqq9 Binary Subsequences (info1cup17_binary) C++14
82 / 100
 900 ms 612 KB 
#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 1000006
#define MAX 10000006
#define LOG 30
using namespace std;

int n,t;
stack<bool> s;

int exg(int x,int y,bool pr) {

	if(x==0 || y==0) return -1;

	if(x<y) {

		int totd=y/x;
		int rem=y%x;

		if(pr) for(int i=1;i<=totd;i++) s.push(0);

		return exg(x,rem,pr)+totd;

	}
	else {

		int totd=x/y;
		int rem=x%y;

		if(pr) for(int i=1;i<=totd;i++) s.push(1);

		return exg(rem,y,pr)+totd;

	}

}

void solve(int n) {

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

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

		if(__gcd(i,k-i)==1) {

			++ans;

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

			if(step<best) {

				best=step;

				x=i,y=k-i;

			}


		}
	
	}

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

	exg(x,y,1);

	s.pop();

	while(sz(s)) {printf("%d ",s.top());s.pop();}

	puts("");

}

int main() {

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

	scanf("%d",&t);

	while(t--) {

		scanf("%d",&n);

		solve(n);

	}

}

Compilation message

binary.cpp: In function 'int main()':
binary.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&t);
  ~~~~~^~~~~~~~~
binary.cpp:102: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:84:5: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  exg(x,y,1);
  ~~~^~~~~~~
binary.cpp:84:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 508 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 516 KB Output is correct
2 Correct 232 ms 536 KB Output is correct
3 Correct 220 ms 536 KB Output is correct

Subtask #3
0 / 18.0

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