oj.uz

Submission #170549

# Submission time Handle Problem Language Result Execution time Memory
170549 2019-12-25T15:36:45 Z SamAnd Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 31372 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 100 ms 16816 KB Ok
2 Correct 102 ms 16816 KB Ok
3 Correct 100 ms 16816 KB Ok
4 Correct 102 ms 16808 KB Ok
5 Correct 103 ms 16888 KB Ok
6 Correct 100 ms 16760 KB Ok
7 Correct 102 ms 16732 KB Ok
8 Correct 100 ms 16812 KB Ok
9 Correct 101 ms 16864 KB Ok
10 Correct 100 ms 16792 KB Ok
11 Correct 103 ms 16888 KB Ok
12 Correct 100 ms 16812 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 16816 KB Ok
2 Correct 105 ms 16812 KB Ok
3 Correct 107 ms 16888 KB Ok
4 Correct 107 ms 16808 KB Ok
5 Correct 115 ms 16824 KB Ok
6 Correct 110 ms 16952 KB Ok
7 Correct 145 ms 17644 KB Ok
8 Correct 123 ms 17136 KB Ok
9 Correct 140 ms 17704 KB Ok
10 Correct 131 ms 17376 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 16732 KB Ok
2 Correct 106 ms 16820 KB Ok
3 Correct 100 ms 16860 KB Ok
4 Correct 101 ms 16808 KB Ok
5 Correct 100 ms 16732 KB Ok
6 Correct 100 ms 16816 KB Ok
7 Correct 99 ms 16760 KB Ok
8 Correct 102 ms 16808 KB Ok
9 Correct 100 ms 16892 KB Ok
10 Correct 100 ms 16808 KB Ok
11 Correct 104 ms 16732 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 16888 KB Ok
2 Correct 102 ms 16760 KB Ok
3 Correct 103 ms 16812 KB Ok
4 Correct 102 ms 16760 KB Ok
5 Correct 99 ms 16760 KB Ok
6 Correct 596 ms 27856 KB Ok
7 Correct 498 ms 28492 KB Ok
8 Correct 969 ms 31372 KB Ok
9 Correct 671 ms 29660 KB Ok
10 Correct 390 ms 23280 KB Ok
11 Correct 606 ms 29956 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 16816 KB Ok
2 Correct 102 ms 16816 KB Ok
3 Correct 100 ms 16816 KB Ok
4 Correct 102 ms 16808 KB Ok
5 Correct 103 ms 16888 KB Ok
6 Correct 100 ms 16760 KB Ok
7 Correct 102 ms 16732 KB Ok
8 Correct 100 ms 16812 KB Ok
9 Correct 101 ms 16864 KB Ok
10 Correct 100 ms 16792 KB Ok
11 Correct 103 ms 16888 KB Ok
12 Correct 100 ms 16812 KB Ok
13 Correct 51 ms 16732 KB Ok
14 Correct 106 ms 16820 KB Ok
15 Correct 100 ms 16860 KB Ok
16 Correct 101 ms 16808 KB Ok
17 Correct 100 ms 16732 KB Ok
18 Correct 100 ms 16816 KB Ok
19 Correct 99 ms 16760 KB Ok
20 Correct 102 ms 16808 KB Ok
21 Correct 100 ms 16892 KB Ok
22 Correct 100 ms 16808 KB Ok
23 Correct 104 ms 16732 KB Ok
24 Correct 108 ms 16888 KB Ok
25 Correct 117 ms 17000 KB Ok
26 Correct 114 ms 16888 KB Ok
27 Correct 108 ms 16888 KB Ok
28 Correct 104 ms 16888 KB Ok
29 Correct 108 ms 17144 KB Ok
30 Correct 103 ms 17016 KB Ok
31 Correct 107 ms 17016 KB Ok
32 Correct 108 ms 17012 KB Ok
33 Correct 108 ms 16860 KB Ok
34 Correct 120 ms 17072 KB Ok
35 Correct 139 ms 17144 KB Ok
36 Correct 131 ms 17076 KB Ok
37 Correct 125 ms 17100 KB Ok
38 Correct 122 ms 17144 KB Ok
39 Correct 119 ms 17144 KB Ok
40 Correct 131 ms 17112 KB Ok
41 Correct 127 ms 17144 KB Ok
42 Correct 125 ms 17144 KB Ok
43 Correct 126 ms 17144 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 16816 KB Ok
2 Correct 102 ms 16816 KB Ok
3 Correct 100 ms 16816 KB Ok
4 Correct 102 ms 16808 KB Ok
5 Correct 103 ms 16888 KB Ok
6 Correct 100 ms 16760 KB Ok
7 Correct 102 ms 16732 KB Ok
8 Correct 100 ms 16812 KB Ok
9 Correct 101 ms 16864 KB Ok
10 Correct 100 ms 16792 KB Ok
11 Correct 103 ms 16888 KB Ok
12 Correct 100 ms 16812 KB Ok
13 Correct 100 ms 16816 KB Ok
14 Correct 105 ms 16812 KB Ok
15 Correct 107 ms 16888 KB Ok
16 Correct 107 ms 16808 KB Ok
17 Correct 115 ms 16824 KB Ok
18 Correct 110 ms 16952 KB Ok
19 Correct 145 ms 17644 KB Ok
20 Correct 123 ms 17136 KB Ok
21 Correct 140 ms 17704 KB Ok
22 Correct 131 ms 17376 KB Ok
23 Correct 51 ms 16732 KB Ok
24 Correct 106 ms 16820 KB Ok
25 Correct 100 ms 16860 KB Ok
26 Correct 101 ms 16808 KB Ok
27 Correct 100 ms 16732 KB Ok
28 Correct 100 ms 16816 KB Ok
29 Correct 99 ms 16760 KB Ok
30 Correct 102 ms 16808 KB Ok
31 Correct 100 ms 16892 KB Ok
32 Correct 100 ms 16808 KB Ok
33 Correct 104 ms 16732 KB Ok
34 Correct 108 ms 16888 KB Ok
35 Correct 117 ms 17000 KB Ok
36 Correct 114 ms 16888 KB Ok
37 Correct 108 ms 16888 KB Ok
38 Correct 104 ms 16888 KB Ok
39 Correct 108 ms 17144 KB Ok
40 Correct 103 ms 17016 KB Ok
41 Correct 107 ms 17016 KB Ok
42 Correct 108 ms 17012 KB Ok
43 Correct 108 ms 16860 KB Ok
44 Correct 120 ms 17072 KB Ok
45 Correct 139 ms 17144 KB Ok
46 Correct 131 ms 17076 KB Ok
47 Correct 125 ms 17100 KB Ok
48 Correct 122 ms 17144 KB Ok
49 Correct 119 ms 17144 KB Ok
50 Correct 131 ms 17112 KB Ok
51 Correct 127 ms 17144 KB Ok
52 Correct 125 ms 17144 KB Ok
53 Correct 126 ms 17144 KB Ok
54 Correct 414 ms 20112 KB Ok
55 Correct 476 ms 20460 KB Ok
56 Correct 510 ms 20644 KB Ok
57 Correct 339 ms 19768 KB Ok
58 Correct 407 ms 20076 KB Ok
59 Correct 337 ms 19728 KB Ok
60 Correct 306 ms 19572 KB Ok
61 Correct 323 ms 19824 KB Ok
62 Correct 433 ms 20084 KB Ok
63 Correct 380 ms 20008 KB Ok
64 Correct 462 ms 20608 KB Ok
65 Correct 379 ms 20080 KB Ok
66 Correct 347 ms 19868 KB Ok
67 Correct 347 ms 19756 KB Ok
68 Correct 374 ms 19824 KB Ok
69 Correct 1590 ms 27684 KB Ok
70 Correct 1882 ms 28312 KB Ok
71 Correct 1587 ms 27748 KB Ok
72 Correct 1755 ms 27604 KB Ok
73 Correct 1603 ms 27712 KB Ok
74 Correct 1661 ms 27576 KB Ok
75 Correct 1410 ms 27204 KB Ok
76 Correct 1830 ms 28020 KB Ok
77 Correct 1455 ms 27188 KB Ok
78 Execution timed out 2045 ms 26140 KB Time limit exceeded
79 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 16816 KB Ok
2 Correct 102 ms 16816 KB Ok
3 Correct 100 ms 16816 KB Ok
4 Correct 102 ms 16808 KB Ok
5 Correct 103 ms 16888 KB Ok
6 Correct 100 ms 16760 KB Ok
7 Correct 102 ms 16732 KB Ok
8 Correct 100 ms 16812 KB Ok
9 Correct 101 ms 16864 KB Ok
10 Correct 100 ms 16792 KB Ok
11 Correct 103 ms 16888 KB Ok
12 Correct 100 ms 16812 KB Ok
13 Correct 100 ms 16816 KB Ok
14 Correct 105 ms 16812 KB Ok
15 Correct 107 ms 16888 KB Ok
16 Correct 107 ms 16808 KB Ok
17 Correct 115 ms 16824 KB Ok
18 Correct 110 ms 16952 KB Ok
19 Correct 145 ms 17644 KB Ok
20 Correct 123 ms 17136 KB Ok
21 Correct 140 ms 17704 KB Ok
22 Correct 131 ms 17376 KB Ok
23 Correct 51 ms 16732 KB Ok
24 Correct 106 ms 16820 KB Ok
25 Correct 100 ms 16860 KB Ok
26 Correct 101 ms 16808 KB Ok
27 Correct 100 ms 16732 KB Ok
28 Correct 100 ms 16816 KB Ok
29 Correct 99 ms 16760 KB Ok
30 Correct 102 ms 16808 KB Ok
31 Correct 100 ms 16892 KB Ok
32 Correct 100 ms 16808 KB Ok
33 Correct 104 ms 16732 KB Ok
34 Correct 101 ms 16888 KB Ok
35 Correct 102 ms 16760 KB Ok
36 Correct 103 ms 16812 KB Ok
37 Correct 102 ms 16760 KB Ok
38 Correct 99 ms 16760 KB Ok
39 Correct 596 ms 27856 KB Ok
40 Correct 498 ms 28492 KB Ok
41 Correct 969 ms 31372 KB Ok
42 Correct 671 ms 29660 KB Ok
43 Correct 390 ms 23280 KB Ok
44 Correct 606 ms 29956 KB Ok
45 Correct 108 ms 16888 KB Ok
46 Correct 117 ms 17000 KB Ok
47 Correct 114 ms 16888 KB Ok
48 Correct 108 ms 16888 KB Ok
49 Correct 104 ms 16888 KB Ok
50 Correct 108 ms 17144 KB Ok
51 Correct 103 ms 17016 KB Ok
52 Correct 107 ms 17016 KB Ok
53 Correct 108 ms 17012 KB Ok
54 Correct 108 ms 16860 KB Ok
55 Correct 120 ms 17072 KB Ok
56 Correct 139 ms 17144 KB Ok
57 Correct 131 ms 17076 KB Ok
58 Correct 125 ms 17100 KB Ok
59 Correct 122 ms 17144 KB Ok
60 Correct 119 ms 17144 KB Ok
61 Correct 131 ms 17112 KB Ok
62 Correct 127 ms 17144 KB Ok
63 Correct 125 ms 17144 KB Ok
64 Correct 126 ms 17144 KB Ok
65 Correct 414 ms 20112 KB Ok
66 Correct 476 ms 20460 KB Ok
67 Correct 510 ms 20644 KB Ok
68 Correct 339 ms 19768 KB Ok
69 Correct 407 ms 20076 KB Ok
70 Correct 337 ms 19728 KB Ok
71 Correct 306 ms 19572 KB Ok
72 Correct 323 ms 19824 KB Ok
73 Correct 433 ms 20084 KB Ok
74 Correct 380 ms 20008 KB Ok
75 Correct 462 ms 20608 KB Ok
76 Correct 379 ms 20080 KB Ok
77 Correct 347 ms 19868 KB Ok
78 Correct 347 ms 19756 KB Ok
79 Correct 374 ms 19824 KB Ok
80 Correct 1590 ms 27684 KB Ok
81 Correct 1882 ms 28312 KB Ok
82 Correct 1587 ms 27748 KB Ok
83 Correct 1755 ms 27604 KB Ok
84 Correct 1603 ms 27712 KB Ok
85 Correct 1661 ms 27576 KB Ok
86 Correct 1410 ms 27204 KB Ok
87 Correct 1830 ms 28020 KB Ok
88 Correct 1455 ms 27188 KB Ok
89 Execution timed out 2045 ms 26140 KB Time limit exceeded
90 Halted 0 ms 0 KB -