oj.uz

Submission #170552

# Submission time Handle Problem Language Result Execution time Memory
170552 2019-12-25T15:37:35 Z SamAnd Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 31540 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 400005;

int ka()
{
    int x = 0;
    while (1)
    {
        char y = getchar();
        if ('0' <= y && y <= '9')
            x = (x * 10) + (y - '0');
        else
            return x;
    }
}

char uu[12];
void tp(int x)
{
    if (x == 0)
    {
        putchar('0');
        return;
    }
    if (x < 0)
    {
        putchar('-');
        x *= (-1);
    }
    int i = 0;
    while (x)
    {
        uu[i++] = (x % 10) + '0';
        x /= 10;
    }
    for (i = i - 1; i >= 0; --i)
        putchar(uu[i]);
}

int n, m;

vector<int> a[N];

int c[N];
bool dfs(int x)
{
    c[x] = 1;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (c[h] == 1)
            return true;
        if (c[h] == 0)
            if (dfs(h))
                return true;
    }
    c[x] = 2;
    return false;
}

bool stg(int x)
{
    for (int i = 0; i <= x; ++i)
        a[i].clear();
    for (int i = 0; i <= x; ++i)
    {
        if (i + m <= x)
            a[i + m].push_back(i);
        if (i + n <= x)
            a[i].push_back(i + n);
    }
    for (int i = 0; i <= x; ++i)
        c[i] = 0;
    for (int i = 0; i <= x; ++i)
    {
        if (dfs(i))
            return false;
    }
    return true;
}

vector<int> v;
void dfs1(int x)
{
    c[x] = 1;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (c[h])
            continue;
        dfs1(h);
    }
    v.push_back(x);
}

int p[N];
void solv()
{
    //n = ka();
    //m = ka();
    scanf("%d%d", &n, &m);
    int l = min(n, m) - 1, r = N - 1;
    int ans;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (stg(m))
        {
            ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    //tp(ans);
    //putchar('\n');
    printf("%d\n", ans);
    //return;
    for (int i = 0; i <= ans; ++i)
        a[i].clear();
    for (int i = 0; i <= ans; ++i)
    {
        if (i + m <= ans)
            a[i + m].push_back(i);
        if (i + n <= ans)
            a[i].push_back(i + n);
    }
    v.clear();
    for (int i = 0; i <= ans; ++i)
        c[i] = 0;
    for (int i = 0; i <= ans; ++i)
    {
        if (!c[i])
            dfs1(i);
    }
    for (int i = 0; i < v.size(); ++i)
        p[v[i]] = i;
    for (int i = 1; i <= ans; ++i)
    {
        tp(p[i] - p[i - 1]);
        putchar(' ');
        //printf("%d ", p[i] - p[i - 1]);
    }
    putchar('\n');
    //printf("\n");
}

int main()
{
    int tt;
    //tt = ka();
    scanf("%d", &tt);
    while (tt--)
    {
        solv();
    }
    return 0;
}

Compilation message

sequence.cpp: In function 'bool dfs(int)':
sequence.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
sequence.cpp: In function 'void dfs1(int)':
sequence.cpp:87:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
sequence.cpp: In function 'void solv()':
sequence.cpp:137:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
sequence.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:153:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &tt);
     ~~~~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 16960 KB Ok
2 Correct 103 ms 16760 KB Ok
3 Correct 99 ms 16760 KB Ok
4 Correct 111 ms 16764 KB Ok
5 Correct 101 ms 16760 KB Ok
6 Correct 100 ms 16760 KB Ok
7 Correct 101 ms 16760 KB Ok
8 Correct 107 ms 16860 KB Ok
9 Correct 108 ms 16860 KB Ok
10 Correct 105 ms 16760 KB Ok
11 Correct 107 ms 16840 KB Ok
12 Correct 103 ms 16844 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 16760 KB Ok
2 Correct 100 ms 16860 KB Ok
3 Correct 100 ms 16888 KB Ok
4 Correct 109 ms 16764 KB Ok
5 Correct 99 ms 16760 KB Ok
6 Correct 113 ms 16896 KB Ok
7 Correct 144 ms 17660 KB Ok
8 Correct 122 ms 17272 KB Ok
9 Correct 142 ms 17628 KB Ok
10 Correct 130 ms 17272 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16760 KB Ok
2 Correct 100 ms 16808 KB Ok
3 Correct 100 ms 16760 KB Ok
4 Correct 102 ms 17016 KB Ok
5 Correct 99 ms 16760 KB Ok
6 Correct 100 ms 16760 KB Ok
7 Correct 101 ms 16812 KB Ok
8 Correct 100 ms 16860 KB Ok
9 Correct 102 ms 16760 KB Ok
10 Correct 101 ms 16764 KB Ok
11 Correct 104 ms 16760 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 16764 KB Ok
2 Correct 99 ms 16760 KB Ok
3 Correct 101 ms 16764 KB Ok
4 Correct 103 ms 16760 KB Ok
5 Correct 101 ms 16804 KB Ok
6 Correct 570 ms 28012 KB Ok
7 Correct 499 ms 28400 KB Ok
8 Correct 951 ms 31540 KB Ok
9 Correct 644 ms 29420 KB Ok
10 Correct 368 ms 23148 KB Ok
11 Correct 569 ms 29748 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 16960 KB Ok
2 Correct 103 ms 16760 KB Ok
3 Correct 99 ms 16760 KB Ok
4 Correct 111 ms 16764 KB Ok
5 Correct 101 ms 16760 KB Ok
6 Correct 100 ms 16760 KB Ok
7 Correct 101 ms 16760 KB Ok
8 Correct 107 ms 16860 KB Ok
9 Correct 108 ms 16860 KB Ok
10 Correct 105 ms 16760 KB Ok
11 Correct 107 ms 16840 KB Ok
12 Correct 103 ms 16844 KB Ok
13 Correct 52 ms 16760 KB Ok
14 Correct 100 ms 16808 KB Ok
15 Correct 100 ms 16760 KB Ok
16 Correct 102 ms 17016 KB Ok
17 Correct 99 ms 16760 KB Ok
18 Correct 100 ms 16760 KB Ok
19 Correct 101 ms 16812 KB Ok
20 Correct 100 ms 16860 KB Ok
21 Correct 102 ms 16760 KB Ok
22 Correct 101 ms 16764 KB Ok
23 Correct 104 ms 16760 KB Ok
24 Correct 104 ms 16872 KB Ok
25 Correct 106 ms 16840 KB Ok
26 Correct 112 ms 16928 KB Ok
27 Correct 110 ms 16860 KB Ok
28 Correct 104 ms 16888 KB Ok
29 Correct 105 ms 16888 KB Ok
30 Correct 105 ms 16888 KB Ok
31 Correct 105 ms 17016 KB Ok
32 Correct 105 ms 16892 KB Ok
33 Correct 105 ms 16888 KB Ok
34 Correct 119 ms 17016 KB Ok
35 Correct 126 ms 17016 KB Ok
36 Correct 125 ms 17144 KB Ok
37 Correct 129 ms 17220 KB Ok
38 Correct 137 ms 17144 KB Ok
39 Correct 121 ms 17016 KB Ok
40 Correct 133 ms 17144 KB Ok
41 Correct 129 ms 17148 KB Ok
42 Correct 159 ms 17144 KB Ok
43 Correct 142 ms 17172 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 16960 KB Ok
2 Correct 103 ms 16760 KB Ok
3 Correct 99 ms 16760 KB Ok
4 Correct 111 ms 16764 KB Ok
5 Correct 101 ms 16760 KB Ok
6 Correct 100 ms 16760 KB Ok
7 Correct 101 ms 16760 KB Ok
8 Correct 107 ms 16860 KB Ok
9 Correct 108 ms 16860 KB Ok
10 Correct 105 ms 16760 KB Ok
11 Correct 107 ms 16840 KB Ok
12 Correct 103 ms 16844 KB Ok
13 Correct 100 ms 16760 KB Ok
14 Correct 100 ms 16860 KB Ok
15 Correct 100 ms 16888 KB Ok
16 Correct 109 ms 16764 KB Ok
17 Correct 99 ms 16760 KB Ok
18 Correct 113 ms 16896 KB Ok
19 Correct 144 ms 17660 KB Ok
20 Correct 122 ms 17272 KB Ok
21 Correct 142 ms 17628 KB Ok
22 Correct 130 ms 17272 KB Ok
23 Correct 52 ms 16760 KB Ok
24 Correct 100 ms 16808 KB Ok
25 Correct 100 ms 16760 KB Ok
26 Correct 102 ms 17016 KB Ok
27 Correct 99 ms 16760 KB Ok
28 Correct 100 ms 16760 KB Ok
29 Correct 101 ms 16812 KB Ok
30 Correct 100 ms 16860 KB Ok
31 Correct 102 ms 16760 KB Ok
32 Correct 101 ms 16764 KB Ok
33 Correct 104 ms 16760 KB Ok
34 Correct 104 ms 16872 KB Ok
35 Correct 106 ms 16840 KB Ok
36 Correct 112 ms 16928 KB Ok
37 Correct 110 ms 16860 KB Ok
38 Correct 104 ms 16888 KB Ok
39 Correct 105 ms 16888 KB Ok
40 Correct 105 ms 16888 KB Ok
41 Correct 105 ms 17016 KB Ok
42 Correct 105 ms 16892 KB Ok
43 Correct 105 ms 16888 KB Ok
44 Correct 119 ms 17016 KB Ok
45 Correct 126 ms 17016 KB Ok
46 Correct 125 ms 17144 KB Ok
47 Correct 129 ms 17220 KB Ok
48 Correct 137 ms 17144 KB Ok
49 Correct 121 ms 17016 KB Ok
50 Correct 133 ms 17144 KB Ok
51 Correct 129 ms 17148 KB Ok
52 Correct 159 ms 17144 KB Ok
53 Correct 142 ms 17172 KB Ok
54 Correct 412 ms 19992 KB Ok
55 Correct 448 ms 20332 KB Ok
56 Correct 438 ms 20572 KB Ok
57 Correct 306 ms 19700 KB Ok
58 Correct 354 ms 20088 KB Ok
59 Correct 300 ms 19828 KB Ok
60 Correct 286 ms 19520 KB Ok
61 Correct 299 ms 19696 KB Ok
62 Correct 394 ms 20208 KB Ok
63 Correct 348 ms 19828 KB Ok
64 Correct 435 ms 20596 KB Ok
65 Correct 347 ms 19952 KB Ok
66 Correct 321 ms 19824 KB Ok
67 Correct 320 ms 19828 KB Ok
68 Correct 359 ms 20060 KB Ok
69 Correct 1549 ms 27780 KB Ok
70 Execution timed out 2069 ms 27680 KB Time limit exceeded
71 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 16960 KB Ok
2 Correct 103 ms 16760 KB Ok
3 Correct 99 ms 16760 KB Ok
4 Correct 111 ms 16764 KB Ok
5 Correct 101 ms 16760 KB Ok
6 Correct 100 ms 16760 KB Ok
7 Correct 101 ms 16760 KB Ok
8 Correct 107 ms 16860 KB Ok
9 Correct 108 ms 16860 KB Ok
10 Correct 105 ms 16760 KB Ok
11 Correct 107 ms 16840 KB Ok
12 Correct 103 ms 16844 KB Ok
13 Correct 100 ms 16760 KB Ok
14 Correct 100 ms 16860 KB Ok
15 Correct 100 ms 16888 KB Ok
16 Correct 109 ms 16764 KB Ok
17 Correct 99 ms 16760 KB Ok
18 Correct 113 ms 16896 KB Ok
19 Correct 144 ms 17660 KB Ok
20 Correct 122 ms 17272 KB Ok
21 Correct 142 ms 17628 KB Ok
22 Correct 130 ms 17272 KB Ok
23 Correct 52 ms 16760 KB Ok
24 Correct 100 ms 16808 KB Ok
25 Correct 100 ms 16760 KB Ok
26 Correct 102 ms 17016 KB Ok
27 Correct 99 ms 16760 KB Ok
28 Correct 100 ms 16760 KB Ok
29 Correct 101 ms 16812 KB Ok
30 Correct 100 ms 16860 KB Ok
31 Correct 102 ms 16760 KB Ok
32 Correct 101 ms 16764 KB Ok
33 Correct 104 ms 16760 KB Ok
34 Correct 99 ms 16764 KB Ok
35 Correct 99 ms 16760 KB Ok
36 Correct 101 ms 16764 KB Ok
37 Correct 103 ms 16760 KB Ok
38 Correct 101 ms 16804 KB Ok
39 Correct 570 ms 28012 KB Ok
40 Correct 499 ms 28400 KB Ok
41 Correct 951 ms 31540 KB Ok
42 Correct 644 ms 29420 KB Ok
43 Correct 368 ms 23148 KB Ok
44 Correct 569 ms 29748 KB Ok
45 Correct 104 ms 16872 KB Ok
46 Correct 106 ms 16840 KB Ok
47 Correct 112 ms 16928 KB Ok
48 Correct 110 ms 16860 KB Ok
49 Correct 104 ms 16888 KB Ok
50 Correct 105 ms 16888 KB Ok
51 Correct 105 ms 16888 KB Ok
52 Correct 105 ms 17016 KB Ok
53 Correct 105 ms 16892 KB Ok
54 Correct 105 ms 16888 KB Ok
55 Correct 119 ms 17016 KB Ok
56 Correct 126 ms 17016 KB Ok
57 Correct 125 ms 17144 KB Ok
58 Correct 129 ms 17220 KB Ok
59 Correct 137 ms 17144 KB Ok
60 Correct 121 ms 17016 KB Ok
61 Correct 133 ms 17144 KB Ok
62 Correct 129 ms 17148 KB Ok
63 Correct 159 ms 17144 KB Ok
64 Correct 142 ms 17172 KB Ok
65 Correct 412 ms 19992 KB Ok
66 Correct 448 ms 20332 KB Ok
67 Correct 438 ms 20572 KB Ok
68 Correct 306 ms 19700 KB Ok
69 Correct 354 ms 20088 KB Ok
70 Correct 300 ms 19828 KB Ok
71 Correct 286 ms 19520 KB Ok
72 Correct 299 ms 19696 KB Ok
73 Correct 394 ms 20208 KB Ok
74 Correct 348 ms 19828 KB Ok
75 Correct 435 ms 20596 KB Ok
76 Correct 347 ms 19952 KB Ok
77 Correct 321 ms 19824 KB Ok
78 Correct 320 ms 19828 KB Ok
79 Correct 359 ms 20060 KB Ok
80 Correct 1549 ms 27780 KB Ok
81 Execution timed out 2069 ms 27680 KB Time limit exceeded
82 Halted 0 ms 0 KB -