oj.uz

Submission #389556

# Submission time Handle Problem Language Result Execution time Memory
389556 2021-04-14T07:21:26 Z cheissmart Binary Subsequences (info1cup17_binary) C++14
100 / 100
 673 ms 332 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << "): " << #x << " is " << (x) << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e3 + 7, M = 1e9 + 7;

void add(int& a, int b) {
    a += b;
    if(a >= M) a -= M;
}

int go(int a, int b) {
    if(a == 0 && b == 0) return 1;
    if(a == b) return 0;
    if(a < b) swap(a, b);
    return go(a % (b + 1), b);
}

int go_len(int a, int b) {
    if(a == 0 && b == 0) return 0;
    if(a == b) return INF;
    if(a < b) swap(a, b);
    return go_len(a % (b + 1), b) + a / (b + 1);
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);


    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int k;
        cin >> k;
        int ans = 0, mn_len = INF, j = -1;
        for(int i = 0; i <= k / 2; i++) {
            add(ans, go(i, k - i) * 2 % M);
            int len = go_len(i, k - i);
            if(len < mn_len) {
                mn_len = len;
                j = i;
            }
        }
        cout << ans << '\n';
        int x = j, y = k - j;
        while(true) {
            if(x > y) cout << 0, x -= y + 1;
            else cout << 1, y -= x + 1;
            if(x || y) cout << ' ';
            else break;
        }
        cout << '\n';
    }

}

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 332 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 292 KB Output is correct
2 Correct 58 ms 204 KB Output is correct
3 Correct 56 ms 204 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 292 KB Output is correct
2 Correct 673 ms 296 KB Output is correct
3 Correct 673 ms 300 KB Output is correct