oj.uz

Submission #199653

# Submission time Handle Problem Language Result Execution time Memory
199653 2020-02-02T12:40:04 Z Pankin Binary Subsequences (info1cup17_binary) C++14
30.1 / 100
 725 ms 452 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 = 2000000005;
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;
                }
            }
        }
        col = -1;
        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:75:13: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int o = k - z;
             ^

Subtask #1
30.1 / 43.0

# Verdict Execution time Memory Grader output
1 Partially correct 85 ms 452 KB Output is partially correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 725 ms 412 KB Output isn't correct
2 Halted 0 ms 0 KB -