oj.uz

Submission #98556

# Submission time Handle Problem Language Result Execution time Memory
98556 2019-02-24T04:52:21 Z TAMREF Binary Subsequences (info1cup17_binary) C++11
100 / 100
 551 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
int t, k;

void pro(int k){
    int cnt = 0;
    int len = INT_MAX, lenx = 0;
    for(int i = 0; i + i < k; i++){
        int x = i, y = k - x;
        int nlen = 0;
        while(x){
            if(x == y){
                nlen = INT_MAX;
                break;
            }
            nlen += y / (x+1);
            y %= (x+1);
            swap(x,y);
        }
        if(nlen < INT_MAX) cnt += 2, nlen += y;
        if(nlen < len){
            len = nlen;
            lenx = i;
        }
    }
    cout << cnt << '\n';
    int X = lenx, Y = k - X;
    while(X || Y){
        cout << (X < Y) << ' ';
        if(X < Y) Y -= (X+1);
        else X -= (Y+1);
    }
    cout << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    for(cin >> t; t--;){
        cin >> k;
        pro(k);
    }
}

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 512 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 384 KB Output is correct
2 Correct 46 ms 384 KB Output is correct
3 Correct 43 ms 376 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 504 KB Output is correct
2 Correct 520 ms 476 KB Output is correct
3 Correct 515 ms 372 KB Output is correct