oj.uz

Submission #199654

# Submission time Handle Problem Language Result Execution time Memory
199654 2020-02-02T12:41:20 Z Pankin Binary Subsequences (info1cup17_binary) C++14
100 / 100
 746 ms 504 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define pii pair<int, int>

const int INF = 1000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;

using namespace std;
using namespace __gnu_pbds;

bool valid(int x, int y, int n, int m) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

mt19937 rng(1999999973);

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

inline int good(int z, int o) {
    if (z + o == 0)
        return 0;
    if (o == z)
        return INF;
    if (o > z) {
        return o / (z + 1) + good(z, o % (z + 1));
    }
    else {
        return z / (o + 1) + good(z % (o + 1), o);
    }
}

signed main() {
    fast_io;

    int t;
    cin >> t;
    while(t--) {
        int col = 0, k, mn = INF, z;
        cin >> k;
        for (int i = 0; i <= k; i++) {
            int val = good(i, k - i);
            if (val < INF) {
                col++;
                if (val < mn) {
                    mn = val;
                    z = i;
                }
            }
        }
        cout << col << endl;
        string s;
        int o = k - z;
        while(o + z != 0) {
            if (o > z) {
                cout << '1' << " ";
                o -= z + 1;
            }
            else {
                cout << '0' << " ";
                z -= o + 1;
            }
        }
        cout << endl;
    }

    return 0;
}

Compilation message

binary.cpp: In function 'int main()':
binary.cpp:74:13: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int o = k - z;
             ^

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 376 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 376 KB Output is correct
2 Correct 69 ms 248 KB Output is correct
3 Correct 63 ms 376 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 504 KB Output is correct
2 Correct 746 ms 392 KB Output is correct
3 Correct 731 ms 504 KB Output is correct