Submission #98433

#	Time	Username	Problem	Language	Result	Execution time	Memory
98433		keko37	Binary Subsequences (info1cup17_binary)	C++14	100 / 100	602 ms	460 KiB

binary

#include<bits/stdc++.h>

using namespace std;

const int INF = 1000000007;

int t, n;

int f (int x, int y) {
    int sol = 0;
    while (y != 0) {
        sol += x/y;
        x = x % y;
        swap(x, y);
    }
    if (x != 1) return INF; return sol;
}

void ispis (int x, int y) {
    string s = "";
    while (x != y) {
        if (x > y) {
            s += '0';
            x -= y+1;
        } else {
            s += '1';
            y -= x+1;
        }
    }
    int len = s.size();
    for (int i=len-1; i>=0; i--) {
        cout << s[i] << " ";
    }
    cout << '\n';
}

void calc () {
    int cnt = 0, mn = INF, ind;
    for (int i=0; i<=n/2; i++) {
        int val = f(i+1, n+1 - i);
        if (val < INF) cnt++;
        if (val < mn) {
            mn = val;
            ind = i;
        }
    }
    cout << cnt*2 << '\n';
    ispis(ind, n - ind);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    for (int i=0; i<t; i++) {
        cin >> n;
        calc();
    }
    return 0;
}

Compilation message (stderr)

binary.cpp: In function 'int f(int, int)':
binary.cpp:16:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (x != 1) return INF; return sol;
     ^~
binary.cpp:16:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     if (x != 1) return INF; return sol;
                             ^~~~~~
binary.cpp: In function 'void calc()':
binary.cpp:48:10: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ispis(ind, n - ind);
     ~~~~~^~~~~~~~~~~~~~

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