Submission #1308708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308708		mxhrvs	Binary Subsequences (info1cup17_binary)	C++20	100 / 100	414 ms	568 KiB

binary

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

long long get_phi(int n) {
    long long result = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

int get_length(int a, int b) {
    int length = 0;
    while (a > 1 && b > 1) {
        if (a > b) {
            int count = (a - 1) / b; 
            length += count;
            a -= count * b;
        } else {
            int count = (b - 1) / a; 
            length += count;
            b -= count * a;
        }
    }
    if (a > 1) length += (a - 1);
    if (b > 1) length += (b - 1);
    
    return length;
}

void print_shortest_string(int a, int b) {
    vector<int> result;
    
    while (a > 1 && b > 1) {
        if (a > b) {
            int count = (a - 1) / b;
            for(int i=0; i<count; i++) result.push_back(0); // '0' ekle
            a -= count * b;
        } else {
            int count = (b - 1) / a;
            for(int i=0; i<count; i++) result.push_back(1); // '1' ekle
            b -= count * a;
        }
    }
    if (a > 1) {
        for(int i=0; i < a - 1; i++) result.push_back(0);
    }
    if (b > 1) {
        for(int i=0; i < b - 1; i++) result.push_back(1);
    }

    reverse(result.begin(), result.end());

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << (i == result.size() - 1 ? "" : " ");
    }
    cout << endl;
}

void solve() {
    int K;
    cin >> K;

    long long count = get_phi(K + 2);
    cout << count << endl;

    int best_a = -1, best_b = -1;
    int min_len = 2000000000; 

    for (int a = 1; a * 2 <= (K + 2); a++) {
        int b = (K + 2) - a;
        
        if (__gcd(a, b) == 1) {
            int current_len = get_length(a, b);
            
            if (current_len < min_len) {
                min_len = current_len;
                best_a = a;
                best_b = b;
            }
        }
    }

    if (best_a != -1) {
        print_shortest_string(best_a, best_b);
    }
}

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

    int T;
    if (cin >> T) {
        while (T--) {
            solve();
        }
    }
    return 0;
}

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