oj.uz

Submission #170541

# Submission time Handle Problem Language Result Execution time Memory
170541 2019-12-25T15:19:52 Z SamAnd Nice sequence (IZhO18_sequence) C++17
76 / 100
 1650 ms 27344 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;

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 = 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;
    }
    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 75 ms 12664 KB Ok
2 Correct 76 ms 12792 KB Ok
3 Correct 75 ms 12664 KB Ok
4 Correct 75 ms 12664 KB Ok
5 Correct 76 ms 12664 KB Ok
6 Correct 75 ms 12808 KB Ok
7 Correct 74 ms 12672 KB Ok
8 Correct 76 ms 12664 KB Ok
9 Correct 76 ms 12792 KB Ok
10 Correct 75 ms 12628 KB Ok
11 Correct 77 ms 12664 KB Ok
12 Correct 76 ms 12664 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 12664 KB Ok
2 Correct 76 ms 12736 KB Ok
3 Correct 81 ms 12664 KB Ok
4 Correct 80 ms 12664 KB Ok
5 Correct 83 ms 12664 KB Ok
6 Correct 92 ms 12796 KB Ok
7 Correct 126 ms 13432 KB Ok
8 Correct 113 ms 13120 KB Ok
9 Correct 112 ms 13560 KB Ok
10 Correct 110 ms 13176 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 12664 KB Ok
2 Correct 78 ms 12664 KB Ok
3 Correct 75 ms 12672 KB Ok
4 Correct 76 ms 12664 KB Ok
5 Correct 75 ms 12792 KB Ok
6 Correct 76 ms 12664 KB Ok
7 Correct 76 ms 12668 KB Ok
8 Correct 75 ms 12736 KB Ok
9 Correct 75 ms 12780 KB Ok
10 Correct 75 ms 12612 KB Ok
11 Correct 76 ms 12704 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 12796 KB Ok
2 Correct 75 ms 12636 KB Ok
3 Correct 76 ms 12668 KB Ok
4 Correct 75 ms 12764 KB Ok
5 Correct 76 ms 12664 KB Ok
6 Correct 542 ms 23856 KB Ok
7 Correct 496 ms 24404 KB Ok
8 Correct 911 ms 27344 KB Ok
9 Correct 628 ms 25456 KB Ok
10 Correct 360 ms 19224 KB Ok
11 Correct 571 ms 25920 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 12664 KB Ok
2 Correct 76 ms 12792 KB Ok
3 Correct 75 ms 12664 KB Ok
4 Correct 75 ms 12664 KB Ok
5 Correct 76 ms 12664 KB Ok
6 Correct 75 ms 12808 KB Ok
7 Correct 74 ms 12672 KB Ok
8 Correct 76 ms 12664 KB Ok
9 Correct 76 ms 12792 KB Ok
10 Correct 75 ms 12628 KB Ok
11 Correct 77 ms 12664 KB Ok
12 Correct 76 ms 12664 KB Ok
13 Correct 39 ms 12664 KB Ok
14 Correct 78 ms 12664 KB Ok
15 Correct 75 ms 12672 KB Ok
16 Correct 76 ms 12664 KB Ok
17 Correct 75 ms 12792 KB Ok
18 Correct 76 ms 12664 KB Ok
19 Correct 76 ms 12668 KB Ok
20 Correct 75 ms 12736 KB Ok
21 Correct 75 ms 12780 KB Ok
22 Correct 75 ms 12612 KB Ok
23 Correct 76 ms 12704 KB Ok
24 Correct 80 ms 12804 KB Ok
25 Correct 81 ms 12780 KB Ok
26 Correct 81 ms 12792 KB Ok
27 Correct 84 ms 12804 KB Ok
28 Correct 87 ms 12796 KB Ok
29 Correct 80 ms 12796 KB Ok
30 Correct 80 ms 12792 KB Ok
31 Correct 81 ms 12752 KB Ok
32 Correct 82 ms 12792 KB Ok
33 Correct 80 ms 12792 KB Ok
34 Correct 96 ms 13132 KB Ok
35 Correct 99 ms 13048 KB Ok
36 Correct 98 ms 13048 KB Ok
37 Correct 102 ms 13048 KB Ok
38 Correct 98 ms 12920 KB Ok
39 Correct 94 ms 12920 KB Ok
40 Correct 103 ms 13080 KB Ok
41 Correct 100 ms 13128 KB Ok
42 Correct 96 ms 12920 KB Ok
43 Correct 99 ms 13048 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 12664 KB Ok
2 Correct 76 ms 12792 KB Ok
3 Correct 75 ms 12664 KB Ok
4 Correct 75 ms 12664 KB Ok
5 Correct 76 ms 12664 KB Ok
6 Correct 75 ms 12808 KB Ok
7 Correct 74 ms 12672 KB Ok
8 Correct 76 ms 12664 KB Ok
9 Correct 76 ms 12792 KB Ok
10 Correct 75 ms 12628 KB Ok
11 Correct 77 ms 12664 KB Ok
12 Correct 76 ms 12664 KB Ok
13 Correct 84 ms 12664 KB Ok
14 Correct 76 ms 12736 KB Ok
15 Correct 81 ms 12664 KB Ok
16 Correct 80 ms 12664 KB Ok
17 Correct 83 ms 12664 KB Ok
18 Correct 92 ms 12796 KB Ok
19 Correct 126 ms 13432 KB Ok
20 Correct 113 ms 13120 KB Ok
21 Correct 112 ms 13560 KB Ok
22 Correct 110 ms 13176 KB Ok
23 Correct 39 ms 12664 KB Ok
24 Correct 78 ms 12664 KB Ok
25 Correct 75 ms 12672 KB Ok
26 Correct 76 ms 12664 KB Ok
27 Correct 75 ms 12792 KB Ok
28 Correct 76 ms 12664 KB Ok
29 Correct 76 ms 12668 KB Ok
30 Correct 75 ms 12736 KB Ok
31 Correct 75 ms 12780 KB Ok
32 Correct 75 ms 12612 KB Ok
33 Correct 76 ms 12704 KB Ok
34 Correct 80 ms 12804 KB Ok
35 Correct 81 ms 12780 KB Ok
36 Correct 81 ms 12792 KB Ok
37 Correct 84 ms 12804 KB Ok
38 Correct 87 ms 12796 KB Ok
39 Correct 80 ms 12796 KB Ok
40 Correct 80 ms 12792 KB Ok
41 Correct 81 ms 12752 KB Ok
42 Correct 82 ms 12792 KB Ok
43 Correct 80 ms 12792 KB Ok
44 Correct 96 ms 13132 KB Ok
45 Correct 99 ms 13048 KB Ok
46 Correct 98 ms 13048 KB Ok
47 Correct 102 ms 13048 KB Ok
48 Correct 98 ms 12920 KB Ok
49 Correct 94 ms 12920 KB Ok
50 Correct 103 ms 13080 KB Ok
51 Correct 100 ms 13128 KB Ok
52 Correct 96 ms 12920 KB Ok
53 Correct 99 ms 13048 KB Ok
54 Correct 380 ms 16116 KB Ok
55 Correct 441 ms 16244 KB Ok
56 Correct 444 ms 16604 KB Ok
57 Correct 302 ms 15444 KB Ok
58 Correct 353 ms 15844 KB Ok
59 Correct 311 ms 15608 KB Ok
60 Correct 279 ms 15344 KB Ok
61 Correct 298 ms 15620 KB Ok
62 Correct 397 ms 15984 KB Ok
63 Correct 333 ms 15692 KB Ok
64 Correct 421 ms 16404 KB Ok
65 Correct 363 ms 15864 KB Ok
66 Correct 319 ms 15804 KB Ok
67 Correct 320 ms 15660 KB Ok
68 Correct 336 ms 15772 KB Ok
69 Correct 1477 ms 23548 KB Ok
70 Correct 1568 ms 24188 KB Ok
71 Correct 1398 ms 23588 KB Ok
72 Correct 1465 ms 23556 KB Ok
73 Correct 1339 ms 23648 KB Ok
74 Correct 1159 ms 23592 KB Ok
75 Correct 1461 ms 23156 KB Ok
76 Correct 1549 ms 23876 KB Ok
77 Correct 1200 ms 23212 KB Ok
78 Correct 1650 ms 23800 KB Ok
79 Correct 1475 ms 23920 KB Ok
80 Correct 1266 ms 23920 KB Ok
81 Correct 1472 ms 23840 KB Ok
82 Correct 1294 ms 23836 KB Ok
83 Correct 1150 ms 23156 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 12664 KB Ok
2 Correct 76 ms 12792 KB Ok
3 Correct 75 ms 12664 KB Ok
4 Correct 75 ms 12664 KB Ok
5 Correct 76 ms 12664 KB Ok
6 Correct 75 ms 12808 KB Ok
7 Correct 74 ms 12672 KB Ok
8 Correct 76 ms 12664 KB Ok
9 Correct 76 ms 12792 KB Ok
10 Correct 75 ms 12628 KB Ok
11 Correct 77 ms 12664 KB Ok
12 Correct 76 ms 12664 KB Ok
13 Correct 84 ms 12664 KB Ok
14 Correct 76 ms 12736 KB Ok
15 Correct 81 ms 12664 KB Ok
16 Correct 80 ms 12664 KB Ok
17 Correct 83 ms 12664 KB Ok
18 Correct 92 ms 12796 KB Ok
19 Correct 126 ms 13432 KB Ok
20 Correct 113 ms 13120 KB Ok
21 Correct 112 ms 13560 KB Ok
22 Correct 110 ms 13176 KB Ok
23 Correct 39 ms 12664 KB Ok
24 Correct 78 ms 12664 KB Ok
25 Correct 75 ms 12672 KB Ok
26 Correct 76 ms 12664 KB Ok
27 Correct 75 ms 12792 KB Ok
28 Correct 76 ms 12664 KB Ok
29 Correct 76 ms 12668 KB Ok
30 Correct 75 ms 12736 KB Ok
31 Correct 75 ms 12780 KB Ok
32 Correct 75 ms 12612 KB Ok
33 Correct 76 ms 12704 KB Ok
34 Correct 76 ms 12796 KB Ok
35 Correct 75 ms 12636 KB Ok
36 Correct 76 ms 12668 KB Ok
37 Correct 75 ms 12764 KB Ok
38 Correct 76 ms 12664 KB Ok
39 Correct 542 ms 23856 KB Ok
40 Correct 496 ms 24404 KB Ok
41 Correct 911 ms 27344 KB Ok
42 Correct 628 ms 25456 KB Ok
43 Correct 360 ms 19224 KB Ok
44 Correct 571 ms 25920 KB Ok
45 Correct 80 ms 12804 KB Ok
46 Correct 81 ms 12780 KB Ok
47 Correct 81 ms 12792 KB Ok
48 Correct 84 ms 12804 KB Ok
49 Correct 87 ms 12796 KB Ok
50 Correct 80 ms 12796 KB Ok
51 Correct 80 ms 12792 KB Ok
52 Correct 81 ms 12752 KB Ok
53 Correct 82 ms 12792 KB Ok
54 Correct 80 ms 12792 KB Ok
55 Correct 96 ms 13132 KB Ok
56 Correct 99 ms 13048 KB Ok
57 Correct 98 ms 13048 KB Ok
58 Correct 102 ms 13048 KB Ok
59 Correct 98 ms 12920 KB Ok
60 Correct 94 ms 12920 KB Ok
61 Correct 103 ms 13080 KB Ok
62 Correct 100 ms 13128 KB Ok
63 Correct 96 ms 12920 KB Ok
64 Correct 99 ms 13048 KB Ok
65 Correct 380 ms 16116 KB Ok
66 Correct 441 ms 16244 KB Ok
67 Correct 444 ms 16604 KB Ok
68 Correct 302 ms 15444 KB Ok
69 Correct 353 ms 15844 KB Ok
70 Correct 311 ms 15608 KB Ok
71 Correct 279 ms 15344 KB Ok
72 Correct 298 ms 15620 KB Ok
73 Correct 397 ms 15984 KB Ok
74 Correct 333 ms 15692 KB Ok
75 Correct 421 ms 16404 KB Ok
76 Correct 363 ms 15864 KB Ok
77 Correct 319 ms 15804 KB Ok
78 Correct 320 ms 15660 KB Ok
79 Correct 336 ms 15772 KB Ok
80 Correct 1477 ms 23548 KB Ok
81 Correct 1568 ms 24188 KB Ok
82 Correct 1398 ms 23588 KB Ok
83 Correct 1465 ms 23556 KB Ok
84 Correct 1339 ms 23648 KB Ok
85 Correct 1159 ms 23592 KB Ok
86 Correct 1461 ms 23156 KB Ok
87 Correct 1549 ms 23876 KB Ok
88 Correct 1200 ms 23212 KB Ok
89 Correct 1650 ms 23800 KB Ok
90 Correct 1475 ms 23920 KB Ok
91 Correct 1266 ms 23920 KB Ok
92 Correct 1472 ms 23840 KB Ok
93 Correct 1294 ms 23836 KB Ok
94 Correct 1150 ms 23156 KB Ok
95 Correct 844 ms 22736 KB Ok
96 Incorrect 1260 ms 25892 KB Jury has the better answer : jans = 311847, pans = 300004
97 Halted 0 ms 0 KB -