oj.uz

Submission #98431

# Submission time Handle Problem Language Result Execution time Memory
98431 2019-02-23T15:28:43 Z keko37 Binary Subsequences (info1cup17_binary) C++14
82 / 100
 900 ms 384 KB 
#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; i++) {
        int val = f(i+1, n+1 - i);
        if (val < INF) cnt++;
        if (val < mn) {
            mn = val;
            ind = i;
        }
    }
    cout << cnt << '\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

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.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 384 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 384 KB Output is correct
2 Correct 99 ms 376 KB Output is correct
3 Correct 97 ms 376 KB Output is correct

Subtask #3
0 / 18.0

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