oj.uz

Submission #170538

# Submission time Handle Problem Language Result Execution time Memory
170538 2019-12-25T15:16:35 Z SamAnd Nice sequence (IZhO18_sequence) C++17
76 / 100
 1653 ms 26772 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 250005;

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()
{
    scanf("%d%d", &n, &m);
    int l = 0, 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;
    }
    printf("%d\n", ans);
    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)
        printf("%d ", p[i] - p[i - 1]);
    printf("\n");
}

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

Compilation message

sequence.cpp: In function 'bool dfs(int)':
sequence.cpp:13: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:51: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:96:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
sequence.cpp:64: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:106: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 62 ms 10616 KB Ok
2 Correct 62 ms 10616 KB Ok
3 Correct 62 ms 10616 KB Ok
4 Correct 62 ms 10616 KB Ok
5 Correct 62 ms 10616 KB Ok
6 Correct 62 ms 10616 KB Ok
7 Correct 66 ms 10648 KB Ok
8 Correct 67 ms 10616 KB Ok
9 Correct 63 ms 10616 KB Ok
10 Correct 63 ms 10652 KB Ok
11 Correct 62 ms 10616 KB Ok
12 Correct 63 ms 10616 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 10660 KB Ok
2 Correct 62 ms 10616 KB Ok
3 Correct 63 ms 10744 KB Ok
4 Correct 63 ms 10616 KB Ok
5 Correct 62 ms 10616 KB Ok
6 Correct 71 ms 10744 KB Ok
7 Correct 106 ms 11384 KB Ok
8 Correct 83 ms 11000 KB Ok
9 Correct 102 ms 11544 KB Ok
10 Correct 95 ms 11100 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 10616 KB Ok
2 Correct 62 ms 10684 KB Ok
3 Correct 62 ms 10616 KB Ok
4 Correct 65 ms 10764 KB Ok
5 Correct 61 ms 10616 KB Ok
6 Correct 63 ms 10744 KB Ok
7 Correct 63 ms 10616 KB Ok
8 Correct 63 ms 10616 KB Ok
9 Correct 63 ms 10616 KB Ok
10 Correct 64 ms 10744 KB Ok
11 Correct 67 ms 10616 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 10744 KB Ok
2 Correct 64 ms 10680 KB Ok
3 Correct 62 ms 10744 KB Ok
4 Correct 64 ms 10616 KB Ok
5 Correct 62 ms 10620 KB Ok
6 Correct 510 ms 22484 KB Ok
7 Correct 447 ms 23916 KB Ok
8 Correct 999 ms 26772 KB Ok
9 Correct 642 ms 24120 KB Ok
10 Correct 343 ms 16192 KB Ok
11 Correct 584 ms 25276 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 10616 KB Ok
2 Correct 62 ms 10616 KB Ok
3 Correct 62 ms 10616 KB Ok
4 Correct 62 ms 10616 KB Ok
5 Correct 62 ms 10616 KB Ok
6 Correct 62 ms 10616 KB Ok
7 Correct 66 ms 10648 KB Ok
8 Correct 67 ms 10616 KB Ok
9 Correct 63 ms 10616 KB Ok
10 Correct 63 ms 10652 KB Ok
11 Correct 62 ms 10616 KB Ok
12 Correct 63 ms 10616 KB Ok
13 Correct 33 ms 10616 KB Ok
14 Correct 62 ms 10684 KB Ok
15 Correct 62 ms 10616 KB Ok
16 Correct 65 ms 10764 KB Ok
17 Correct 61 ms 10616 KB Ok
18 Correct 63 ms 10744 KB Ok
19 Correct 63 ms 10616 KB Ok
20 Correct 63 ms 10616 KB Ok
21 Correct 63 ms 10616 KB Ok
22 Correct 64 ms 10744 KB Ok
23 Correct 67 ms 10616 KB Ok
24 Correct 67 ms 10936 KB Ok
25 Correct 67 ms 10744 KB Ok
26 Correct 69 ms 10616 KB Ok
27 Correct 68 ms 10744 KB Ok
28 Correct 66 ms 10716 KB Ok
29 Correct 67 ms 10668 KB Ok
30 Correct 65 ms 10664 KB Ok
31 Correct 66 ms 10636 KB Ok
32 Correct 67 ms 10616 KB Ok
33 Correct 66 ms 10716 KB Ok
34 Correct 80 ms 10880 KB Ok
35 Correct 86 ms 10952 KB Ok
36 Correct 84 ms 10920 KB Ok
37 Correct 89 ms 11004 KB Ok
38 Correct 84 ms 10920 KB Ok
39 Correct 80 ms 10872 KB Ok
40 Correct 90 ms 10912 KB Ok
41 Correct 85 ms 10980 KB Ok
42 Correct 82 ms 10928 KB Ok
43 Correct 85 ms 10976 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 10616 KB Ok
2 Correct 62 ms 10616 KB Ok
3 Correct 62 ms 10616 KB Ok
4 Correct 62 ms 10616 KB Ok
5 Correct 62 ms 10616 KB Ok
6 Correct 62 ms 10616 KB Ok
7 Correct 66 ms 10648 KB Ok
8 Correct 67 ms 10616 KB Ok
9 Correct 63 ms 10616 KB Ok
10 Correct 63 ms 10652 KB Ok
11 Correct 62 ms 10616 KB Ok
12 Correct 63 ms 10616 KB Ok
13 Correct 63 ms 10660 KB Ok
14 Correct 62 ms 10616 KB Ok
15 Correct 63 ms 10744 KB Ok
16 Correct 63 ms 10616 KB Ok
17 Correct 62 ms 10616 KB Ok
18 Correct 71 ms 10744 KB Ok
19 Correct 106 ms 11384 KB Ok
20 Correct 83 ms 11000 KB Ok
21 Correct 102 ms 11544 KB Ok
22 Correct 95 ms 11100 KB Ok
23 Correct 33 ms 10616 KB Ok
24 Correct 62 ms 10684 KB Ok
25 Correct 62 ms 10616 KB Ok
26 Correct 65 ms 10764 KB Ok
27 Correct 61 ms 10616 KB Ok
28 Correct 63 ms 10744 KB Ok
29 Correct 63 ms 10616 KB Ok
30 Correct 63 ms 10616 KB Ok
31 Correct 63 ms 10616 KB Ok
32 Correct 64 ms 10744 KB Ok
33 Correct 67 ms 10616 KB Ok
34 Correct 67 ms 10936 KB Ok
35 Correct 67 ms 10744 KB Ok
36 Correct 69 ms 10616 KB Ok
37 Correct 68 ms 10744 KB Ok
38 Correct 66 ms 10716 KB Ok
39 Correct 67 ms 10668 KB Ok
40 Correct 65 ms 10664 KB Ok
41 Correct 66 ms 10636 KB Ok
42 Correct 67 ms 10616 KB Ok
43 Correct 66 ms 10716 KB Ok
44 Correct 80 ms 10880 KB Ok
45 Correct 86 ms 10952 KB Ok
46 Correct 84 ms 10920 KB Ok
47 Correct 89 ms 11004 KB Ok
48 Correct 84 ms 10920 KB Ok
49 Correct 80 ms 10872 KB Ok
50 Correct 90 ms 10912 KB Ok
51 Correct 85 ms 10980 KB Ok
52 Correct 82 ms 10928 KB Ok
53 Correct 85 ms 10976 KB Ok
54 Correct 348 ms 13132 KB Ok
55 Correct 420 ms 13476 KB Ok
56 Correct 440 ms 13516 KB Ok
57 Correct 268 ms 12784 KB Ok
58 Correct 334 ms 12916 KB Ok
59 Correct 285 ms 12944 KB Ok
60 Correct 251 ms 12568 KB Ok
61 Correct 282 ms 12796 KB Ok
62 Correct 389 ms 13544 KB Ok
63 Correct 306 ms 12916 KB Ok
64 Correct 428 ms 13632 KB Ok
65 Correct 345 ms 13300 KB Ok
66 Correct 313 ms 12988 KB Ok
67 Correct 274 ms 12916 KB Ok
68 Correct 312 ms 13044 KB Ok
69 Correct 1578 ms 20772 KB Ok
70 Correct 1653 ms 21336 KB Ok
71 Correct 1107 ms 20768 KB Ok
72 Correct 1248 ms 20852 KB Ok
73 Correct 1146 ms 20976 KB Ok
74 Correct 1056 ms 20720 KB Ok
75 Correct 1135 ms 20340 KB Ok
76 Correct 1444 ms 21124 KB Ok
77 Correct 1055 ms 20268 KB Ok
78 Correct 1319 ms 20840 KB Ok
79 Correct 1273 ms 20932 KB Ok
80 Correct 1111 ms 21076 KB Ok
81 Correct 1234 ms 21104 KB Ok
82 Correct 1132 ms 20980 KB Ok
83 Correct 1182 ms 20204 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 10616 KB Ok
2 Correct 62 ms 10616 KB Ok
3 Correct 62 ms 10616 KB Ok
4 Correct 62 ms 10616 KB Ok
5 Correct 62 ms 10616 KB Ok
6 Correct 62 ms 10616 KB Ok
7 Correct 66 ms 10648 KB Ok
8 Correct 67 ms 10616 KB Ok
9 Correct 63 ms 10616 KB Ok
10 Correct 63 ms 10652 KB Ok
11 Correct 62 ms 10616 KB Ok
12 Correct 63 ms 10616 KB Ok
13 Correct 63 ms 10660 KB Ok
14 Correct 62 ms 10616 KB Ok
15 Correct 63 ms 10744 KB Ok
16 Correct 63 ms 10616 KB Ok
17 Correct 62 ms 10616 KB Ok
18 Correct 71 ms 10744 KB Ok
19 Correct 106 ms 11384 KB Ok
20 Correct 83 ms 11000 KB Ok
21 Correct 102 ms 11544 KB Ok
22 Correct 95 ms 11100 KB Ok
23 Correct 33 ms 10616 KB Ok
24 Correct 62 ms 10684 KB Ok
25 Correct 62 ms 10616 KB Ok
26 Correct 65 ms 10764 KB Ok
27 Correct 61 ms 10616 KB Ok
28 Correct 63 ms 10744 KB Ok
29 Correct 63 ms 10616 KB Ok
30 Correct 63 ms 10616 KB Ok
31 Correct 63 ms 10616 KB Ok
32 Correct 64 ms 10744 KB Ok
33 Correct 67 ms 10616 KB Ok
34 Correct 66 ms 10744 KB Ok
35 Correct 64 ms 10680 KB Ok
36 Correct 62 ms 10744 KB Ok
37 Correct 64 ms 10616 KB Ok
38 Correct 62 ms 10620 KB Ok
39 Correct 510 ms 22484 KB Ok
40 Correct 447 ms 23916 KB Ok
41 Correct 999 ms 26772 KB Ok
42 Correct 642 ms 24120 KB Ok
43 Correct 343 ms 16192 KB Ok
44 Correct 584 ms 25276 KB Ok
45 Correct 67 ms 10936 KB Ok
46 Correct 67 ms 10744 KB Ok
47 Correct 69 ms 10616 KB Ok
48 Correct 68 ms 10744 KB Ok
49 Correct 66 ms 10716 KB Ok
50 Correct 67 ms 10668 KB Ok
51 Correct 65 ms 10664 KB Ok
52 Correct 66 ms 10636 KB Ok
53 Correct 67 ms 10616 KB Ok
54 Correct 66 ms 10716 KB Ok
55 Correct 80 ms 10880 KB Ok
56 Correct 86 ms 10952 KB Ok
57 Correct 84 ms 10920 KB Ok
58 Correct 89 ms 11004 KB Ok
59 Correct 84 ms 10920 KB Ok
60 Correct 80 ms 10872 KB Ok
61 Correct 90 ms 10912 KB Ok
62 Correct 85 ms 10980 KB Ok
63 Correct 82 ms 10928 KB Ok
64 Correct 85 ms 10976 KB Ok
65 Correct 348 ms 13132 KB Ok
66 Correct 420 ms 13476 KB Ok
67 Correct 440 ms 13516 KB Ok
68 Correct 268 ms 12784 KB Ok
69 Correct 334 ms 12916 KB Ok
70 Correct 285 ms 12944 KB Ok
71 Correct 251 ms 12568 KB Ok
72 Correct 282 ms 12796 KB Ok
73 Correct 389 ms 13544 KB Ok
74 Correct 306 ms 12916 KB Ok
75 Correct 428 ms 13632 KB Ok
76 Correct 345 ms 13300 KB Ok
77 Correct 313 ms 12988 KB Ok
78 Correct 274 ms 12916 KB Ok
79 Correct 312 ms 13044 KB Ok
80 Correct 1578 ms 20772 KB Ok
81 Correct 1653 ms 21336 KB Ok
82 Correct 1107 ms 20768 KB Ok
83 Correct 1248 ms 20852 KB Ok
84 Correct 1146 ms 20976 KB Ok
85 Correct 1056 ms 20720 KB Ok
86 Correct 1135 ms 20340 KB Ok
87 Correct 1444 ms 21124 KB Ok
88 Correct 1055 ms 20268 KB Ok
89 Correct 1319 ms 20840 KB Ok
90 Correct 1273 ms 20932 KB Ok
91 Correct 1111 ms 21076 KB Ok
92 Correct 1234 ms 21104 KB Ok
93 Correct 1132 ms 20980 KB Ok
94 Correct 1182 ms 20204 KB Ok
95 Correct 1075 ms 21036 KB Ok
96 Incorrect 857 ms 21552 KB Jury has the better answer : jans = 280751, pans = 250004
97 Halted 0 ms 0 KB -