Submission #1318688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318688		TraianDanciu	Binary Subsequences (info1cup17_binary)	C++20	100 / 100	577 ms	448 KiB

binary

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

vector<int> answer;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin >> t;
  while(t--) {
    int k;
    cin >> k;

    int best = -1, bestcnt = k + 1, total = 0;
    for(int i = 0; i <= k; i++) {
      int a = i, b = k - i, cnt = 0;
      while(a != b) {
        if(a > b) {
          cnt += a / (b + 1);
          a %= b + 1;
        } else {
          cnt += b / (a + 1);
          b %= a + 1;
        }
      }
      if(a == 0) {
        total++;
        if(cnt <= bestcnt) {
          bestcnt = cnt;
          best = i;
        }
      }
    }

    cout << total << "\n";
    if(total == 0) {
      cout << "-1\n";
    } else {
      int a = best, b = k - best;
      while(a != b) {
        if(a > b) {
          answer.push_back(0);
          a -= b + 1;
        } else {
          answer.push_back(1);
          b -= a + 1;
        }
      }
      reverse(answer.begin(), answer.end());
      for(auto it : answer) {
        cout << it << " ";
      }
      cout << "\n";
      answer.clear();
    }
  }

  return 0;
}

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