oj.uz

Submission #170536

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

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 99 ms 17016 KB Ok
2 Correct 98 ms 16760 KB Ok
3 Correct 100 ms 16812 KB Ok
4 Correct 100 ms 16888 KB Ok
5 Correct 99 ms 16888 KB Ok
6 Correct 99 ms 16808 KB Ok
7 Correct 99 ms 16760 KB Ok
8 Correct 99 ms 16812 KB Ok
9 Correct 99 ms 16760 KB Ok
10 Correct 100 ms 16760 KB Ok
11 Correct 99 ms 16760 KB Ok
12 Correct 101 ms 16760 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 16760 KB Ok
2 Correct 101 ms 16760 KB Ok
3 Correct 103 ms 16776 KB Ok
4 Correct 102 ms 16888 KB Ok
5 Correct 101 ms 16932 KB Ok
6 Correct 107 ms 16888 KB Ok
7 Correct 145 ms 17656 KB Ok
8 Correct 124 ms 17164 KB Ok
9 Correct 141 ms 17656 KB Ok
10 Correct 131 ms 17336 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 16888 KB Ok
2 Correct 98 ms 16760 KB Ok
3 Correct 98 ms 16816 KB Ok
4 Correct 100 ms 16888 KB Ok
5 Correct 99 ms 16812 KB Ok
6 Correct 572 ms 26584 KB Ok
7 Correct 486 ms 26860 KB Ok
8 Correct 893 ms 29852 KB Ok
9 Correct 610 ms 28276 KB Ok
10 Correct 370 ms 22512 KB Ok
11 Correct 565 ms 28276 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 17016 KB Ok
2 Correct 98 ms 16760 KB Ok
3 Correct 100 ms 16812 KB Ok
4 Correct 100 ms 16888 KB Ok
5 Correct 99 ms 16888 KB Ok
6 Correct 99 ms 16808 KB Ok
7 Correct 99 ms 16760 KB Ok
8 Correct 99 ms 16812 KB Ok
9 Correct 99 ms 16760 KB Ok
10 Correct 100 ms 16760 KB Ok
11 Correct 99 ms 16760 KB Ok
12 Correct 101 ms 16760 KB Ok
13 Correct 52 ms 16888 KB Ok
14 Correct 101 ms 16812 KB Ok
15 Correct 100 ms 16760 KB Ok
16 Correct 100 ms 16764 KB Ok
17 Correct 104 ms 16888 KB Ok
18 Correct 107 ms 16892 KB Ok
19 Correct 100 ms 17016 KB Ok
20 Correct 100 ms 16760 KB Ok
21 Correct 99 ms 16888 KB Ok
22 Correct 104 ms 16888 KB Ok
23 Correct 102 ms 16760 KB Ok
24 Correct 105 ms 17048 KB Ok
25 Correct 106 ms 16888 KB Ok
26 Correct 105 ms 16888 KB Ok
27 Correct 114 ms 16888 KB Ok
28 Correct 117 ms 17016 KB Ok
29 Correct 114 ms 16888 KB Ok
30 Correct 103 ms 16988 KB Ok
31 Correct 103 ms 17028 KB Ok
32 Correct 105 ms 16888 KB Ok
33 Correct 105 ms 16980 KB Ok
34 Correct 118 ms 17048 KB Ok
35 Correct 130 ms 17116 KB Ok
36 Correct 125 ms 17016 KB Ok
37 Correct 125 ms 17116 KB Ok
38 Correct 122 ms 17116 KB Ok
39 Correct 121 ms 17016 KB Ok
40 Correct 128 ms 17144 KB Ok
41 Correct 126 ms 17144 KB Ok
42 Correct 120 ms 17272 KB Ok
43 Correct 123 ms 17144 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 17016 KB Ok
2 Correct 98 ms 16760 KB Ok
3 Correct 100 ms 16812 KB Ok
4 Correct 100 ms 16888 KB Ok
5 Correct 99 ms 16888 KB Ok
6 Correct 99 ms 16808 KB Ok
7 Correct 99 ms 16760 KB Ok
8 Correct 99 ms 16812 KB Ok
9 Correct 99 ms 16760 KB Ok
10 Correct 100 ms 16760 KB Ok
11 Correct 99 ms 16760 KB Ok
12 Correct 101 ms 16760 KB Ok
13 Correct 100 ms 16760 KB Ok
14 Correct 101 ms 16760 KB Ok
15 Correct 103 ms 16776 KB Ok
16 Correct 102 ms 16888 KB Ok
17 Correct 101 ms 16932 KB Ok
18 Correct 107 ms 16888 KB Ok
19 Correct 145 ms 17656 KB Ok
20 Correct 124 ms 17164 KB Ok
21 Correct 141 ms 17656 KB Ok
22 Correct 131 ms 17336 KB Ok
23 Correct 52 ms 16888 KB Ok
24 Correct 101 ms 16812 KB Ok
25 Correct 100 ms 16760 KB Ok
26 Correct 100 ms 16764 KB Ok
27 Correct 104 ms 16888 KB Ok
28 Correct 107 ms 16892 KB Ok
29 Correct 100 ms 17016 KB Ok
30 Correct 100 ms 16760 KB Ok
31 Correct 99 ms 16888 KB Ok
32 Correct 104 ms 16888 KB Ok
33 Correct 102 ms 16760 KB Ok
34 Correct 105 ms 17048 KB Ok
35 Correct 106 ms 16888 KB Ok
36 Correct 105 ms 16888 KB Ok
37 Correct 114 ms 16888 KB Ok
38 Correct 117 ms 17016 KB Ok
39 Correct 114 ms 16888 KB Ok
40 Correct 103 ms 16988 KB Ok
41 Correct 103 ms 17028 KB Ok
42 Correct 105 ms 16888 KB Ok
43 Correct 105 ms 16980 KB Ok
44 Correct 118 ms 17048 KB Ok
45 Correct 130 ms 17116 KB Ok
46 Correct 125 ms 17016 KB Ok
47 Correct 125 ms 17116 KB Ok
48 Correct 122 ms 17116 KB Ok
49 Correct 121 ms 17016 KB Ok
50 Correct 128 ms 17144 KB Ok
51 Correct 126 ms 17144 KB Ok
52 Correct 120 ms 17272 KB Ok
53 Correct 123 ms 17144 KB Ok
54 Correct 375 ms 19312 KB Ok
55 Correct 462 ms 19824 KB Ok
56 Correct 478 ms 19696 KB Ok
57 Correct 305 ms 19056 KB Ok
58 Correct 373 ms 19180 KB Ok
59 Correct 323 ms 19088 KB Ok
60 Correct 290 ms 18908 KB Ok
61 Correct 319 ms 19056 KB Ok
62 Correct 410 ms 19444 KB Ok
63 Correct 332 ms 19312 KB Ok
64 Correct 453 ms 19836 KB Ok
65 Correct 376 ms 19408 KB Ok
66 Correct 351 ms 19188 KB Ok
67 Correct 352 ms 19056 KB Ok
68 Correct 357 ms 19376 KB Ok
69 Correct 1272 ms 26824 KB Ok
70 Correct 1382 ms 27552 KB Ok
71 Correct 1212 ms 27056 KB Ok
72 Correct 1344 ms 26740 KB Ok
73 Correct 1209 ms 26940 KB Ok
74 Correct 1223 ms 26824 KB Ok
75 Correct 1255 ms 26324 KB Ok
76 Correct 1562 ms 27204 KB Ok
77 Correct 1048 ms 26408 KB Ok
78 Correct 1562 ms 27096 KB Ok
79 Correct 1412 ms 27080 KB Ok
80 Correct 1305 ms 27244 KB Ok
81 Correct 1481 ms 27020 KB Ok
82 Correct 1202 ms 27044 KB Ok
83 Correct 1091 ms 26428 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 17016 KB Ok
2 Correct 98 ms 16760 KB Ok
3 Correct 100 ms 16812 KB Ok
4 Correct 100 ms 16888 KB Ok
5 Correct 99 ms 16888 KB Ok
6 Correct 99 ms 16808 KB Ok
7 Correct 99 ms 16760 KB Ok
8 Correct 99 ms 16812 KB Ok
9 Correct 99 ms 16760 KB Ok
10 Correct 100 ms 16760 KB Ok
11 Correct 99 ms 16760 KB Ok
12 Correct 101 ms 16760 KB Ok
13 Correct 100 ms 16760 KB Ok
14 Correct 101 ms 16760 KB Ok
15 Correct 103 ms 16776 KB Ok
16 Correct 102 ms 16888 KB Ok
17 Correct 101 ms 16932 KB Ok
18 Correct 107 ms 16888 KB Ok
19 Correct 145 ms 17656 KB Ok
20 Correct 124 ms 17164 KB Ok
21 Correct 141 ms 17656 KB Ok
22 Correct 131 ms 17336 KB Ok
23 Correct 52 ms 16888 KB Ok
24 Correct 101 ms 16812 KB Ok
25 Correct 100 ms 16760 KB Ok
26 Correct 100 ms 16764 KB Ok
27 Correct 104 ms 16888 KB Ok
28 Correct 107 ms 16892 KB Ok
29 Correct 100 ms 17016 KB Ok
30 Correct 100 ms 16760 KB Ok
31 Correct 99 ms 16888 KB Ok
32 Correct 104 ms 16888 KB Ok
33 Correct 102 ms 16760 KB Ok
34 Correct 100 ms 16888 KB Ok
35 Correct 98 ms 16760 KB Ok
36 Correct 98 ms 16816 KB Ok
37 Correct 100 ms 16888 KB Ok
38 Correct 99 ms 16812 KB Ok
39 Correct 572 ms 26584 KB Ok
40 Correct 486 ms 26860 KB Ok
41 Correct 893 ms 29852 KB Ok
42 Correct 610 ms 28276 KB Ok
43 Correct 370 ms 22512 KB Ok
44 Correct 565 ms 28276 KB Ok
45 Correct 105 ms 17048 KB Ok
46 Correct 106 ms 16888 KB Ok
47 Correct 105 ms 16888 KB Ok
48 Correct 114 ms 16888 KB Ok
49 Correct 117 ms 17016 KB Ok
50 Correct 114 ms 16888 KB Ok
51 Correct 103 ms 16988 KB Ok
52 Correct 103 ms 17028 KB Ok
53 Correct 105 ms 16888 KB Ok
54 Correct 105 ms 16980 KB Ok
55 Correct 118 ms 17048 KB Ok
56 Correct 130 ms 17116 KB Ok
57 Correct 125 ms 17016 KB Ok
58 Correct 125 ms 17116 KB Ok
59 Correct 122 ms 17116 KB Ok
60 Correct 121 ms 17016 KB Ok
61 Correct 128 ms 17144 KB Ok
62 Correct 126 ms 17144 KB Ok
63 Correct 120 ms 17272 KB Ok
64 Correct 123 ms 17144 KB Ok
65 Correct 375 ms 19312 KB Ok
66 Correct 462 ms 19824 KB Ok
67 Correct 478 ms 19696 KB Ok
68 Correct 305 ms 19056 KB Ok
69 Correct 373 ms 19180 KB Ok
70 Correct 323 ms 19088 KB Ok
71 Correct 290 ms 18908 KB Ok
72 Correct 319 ms 19056 KB Ok
73 Correct 410 ms 19444 KB Ok
74 Correct 332 ms 19312 KB Ok
75 Correct 453 ms 19836 KB Ok
76 Correct 376 ms 19408 KB Ok
77 Correct 351 ms 19188 KB Ok
78 Correct 352 ms 19056 KB Ok
79 Correct 357 ms 19376 KB Ok
80 Correct 1272 ms 26824 KB Ok
81 Correct 1382 ms 27552 KB Ok
82 Correct 1212 ms 27056 KB Ok
83 Correct 1344 ms 26740 KB Ok
84 Correct 1209 ms 26940 KB Ok
85 Correct 1223 ms 26824 KB Ok
86 Correct 1255 ms 26324 KB Ok
87 Correct 1562 ms 27204 KB Ok
88 Correct 1048 ms 26408 KB Ok
89 Correct 1562 ms 27096 KB Ok
90 Correct 1412 ms 27080 KB Ok
91 Correct 1305 ms 27244 KB Ok
92 Correct 1481 ms 27020 KB Ok
93 Correct 1202 ms 27044 KB Ok
94 Correct 1091 ms 26428 KB Ok
95 Correct 854 ms 26524 KB Ok
96 Correct 1324 ms 31364 KB Ok
97 Correct 1261 ms 27852 KB Ok
98 Correct 769 ms 28704 KB Ok
99 Correct 1216 ms 27196 KB Ok
100 Correct 1284 ms 27360 KB Ok
101 Correct 1253 ms 29668 KB Ok
102 Correct 1070 ms 27876 KB Ok
103 Correct 983 ms 29624 KB Ok
104 Correct 1573 ms 30820 KB Ok
105 Correct 1526 ms 31196 KB Ok
106 Correct 1339 ms 30992 KB Ok
107 Correct 1323 ms 30024 KB Ok
108 Correct 1783 ms 30988 KB Ok
109 Correct 1453 ms 32080 KB Ok
110 Execution timed out 2060 ms 37968 KB Time limit exceeded
111 Halted 0 ms 0 KB -