oj.uz

Submission #782030

# Submission time Handle Problem Language Result Execution time Memory
782030 2023-07-13T14:52:44 Z Andrey Binary Subsequences (info1cup17_binary) C++14
100 / 100
 590 ms 364 KB 
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int k,ans = 0,a = 0,b = 0,br = 0,sm = INT_MAX,c;
    cin >> k;
    for(int i = 0; i <= k; i++) {
        a = i;
        b = k-i;
        br = 0;
        while(a != b) {
            if(a < b) {
                swap(a,b);
            }
            br+=a/(b+1);
            a%=b+1;
        }
        if(a == 0 && b == 0) {
            ans++;
            if(br < sm) {
                sm = br;
                c = i;
            }
        }
    }
    vector<int> wut(0);
    a = c;
    b = k-c;
    while(a != b) {
        if(a > b) {
            wut.push_back(0);
            a-=b+1;
        }
        else {
            wut.push_back(1);
            b-=a+1;
        }
    }
    cout << ans << "\n";
    for(int i = 0; i < wut.size(); i++) {
        cout << wut[i] << " ";
    }
    cout << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

Compilation message

binary.cpp: In function 'void solve()':
binary.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0; i < wut.size(); i++) {
      |                    ~~^~~~~~~~~~~~
binary.cpp:28:10: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |     b = k-c;
      |         ~^~

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 364 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 320 KB Output is correct
2 Correct 51 ms 296 KB Output is correct
3 Correct 48 ms 296 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 292 KB Output is correct
2 Correct 590 ms 304 KB Output is correct
3 Correct 575 ms 300 KB Output is correct