oj.uz

Submission #45372

# Submission time Handle Problem Language Result Execution time Memory
45372 2018-04-13T03:41:05 Z model_code Binary Subsequences (info1cup17_binary) C++17
100 / 100
 896 ms 692 KB 
#include<bits/stdc++.h>

using namespace std;

int Tests, ans[1000009];

void solve (int K)
{
    int cnt = 0, minL = K + 2, how = -1;
    for (int T = 0; T <= K - T; T++)
    {
        int i = T, j = K - T, currL = 0;
        bool fail = 0;
        while (i > 0 || j > 0)
        {
            if (i < 0 || j < 0)
            {
                fail = 1;
                break;
            }
            if (i < j) swap (i, j);
            int curr = (i - j - 1) / (j + 1) + 1;
            i -= curr * (j + 1), currL += curr;
        }
        if (!fail)
        {
            cnt ++;
            if (T != K - T) cnt ++;
            if (currL < minL)
                minL = currL, how = T;
        }
    }
    printf ("%d\n", cnt), ans[0] = 0;
    int i = how, j = K - how;
    while (i > 0 || j > 0)
    {
        if (i > j) i = i - j - 1, ans[++ans[0]] = 1;
        else j = j - i - 1, ans[++ans[0]] = 0;
    }
    for (int i=ans[0]; i>=1; i--)
        printf ("%d ", ans[i]);
    printf ("\n");
}
int main ()
{

scanf ("%d", &Tests);
for (int i=1; i<=Tests; i++)
{
    int x;
    scanf ("%d", &x);
    solve (x);
}

return 0;
}

Compilation message

binary.cpp: In function 'int main()':
binary.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &Tests);
 ~~~~~~^~~~~~~~~~~~~~
binary.cpp:51:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &x);
     ~~~~~~^~~~~~~~~~

Subtask #1
43.0 / 43.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 376 KB Output is correct
2 Correct 74 ms 484 KB Output is correct
3 Correct 69 ms 488 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 880 ms 556 KB Output is correct
2 Correct 896 ms 692 KB Output is correct
3 Correct 869 ms 692 KB Output is correct