oj.uz

Submission #170540

# Submission time Handle Problem Language Result Execution time Memory
170540 2019-12-25T15:18:14 Z SamAnd Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 27276 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 76 ms 12664 KB Ok
2 Correct 75 ms 12664 KB Ok
3 Correct 76 ms 12920 KB Ok
4 Correct 74 ms 12664 KB Ok
5 Correct 75 ms 12664 KB Ok
6 Correct 75 ms 12664 KB Ok
7 Correct 74 ms 12664 KB Ok
8 Correct 81 ms 12792 KB Ok
9 Correct 75 ms 12684 KB Ok
10 Correct 79 ms 12664 KB Ok
11 Correct 75 ms 12792 KB Ok
12 Correct 75 ms 12664 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 12664 KB Ok
2 Correct 76 ms 12684 KB Ok
3 Correct 75 ms 12664 KB Ok
4 Correct 74 ms 12664 KB Ok
5 Correct 78 ms 12636 KB Ok
6 Correct 82 ms 12792 KB Ok
7 Correct 117 ms 13532 KB Ok
8 Correct 94 ms 13020 KB Ok
9 Correct 116 ms 13684 KB Ok
10 Correct 103 ms 13304 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12664 KB Ok
2 Correct 88 ms 12668 KB Ok
3 Correct 75 ms 12792 KB Ok
4 Correct 75 ms 12664 KB Ok
5 Correct 78 ms 12792 KB Ok
6 Correct 75 ms 12664 KB Ok
7 Correct 76 ms 12664 KB Ok
8 Correct 74 ms 12664 KB Ok
9 Correct 75 ms 12664 KB Ok
10 Correct 81 ms 12808 KB Ok
11 Correct 75 ms 12664 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 12664 KB Ok
2 Correct 76 ms 12700 KB Ok
3 Correct 77 ms 12664 KB Ok
4 Correct 77 ms 12704 KB Ok
5 Correct 76 ms 12664 KB Ok
6 Correct 533 ms 23916 KB Ok
7 Correct 467 ms 24304 KB Ok
8 Correct 911 ms 27276 KB Ok
9 Correct 630 ms 25356 KB Ok
10 Correct 352 ms 19148 KB Ok
11 Correct 591 ms 25716 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 12664 KB Ok
2 Correct 75 ms 12664 KB Ok
3 Correct 76 ms 12920 KB Ok
4 Correct 74 ms 12664 KB Ok
5 Correct 75 ms 12664 KB Ok
6 Correct 75 ms 12664 KB Ok
7 Correct 74 ms 12664 KB Ok
8 Correct 81 ms 12792 KB Ok
9 Correct 75 ms 12684 KB Ok
10 Correct 79 ms 12664 KB Ok
11 Correct 75 ms 12792 KB Ok
12 Correct 75 ms 12664 KB Ok
13 Correct 40 ms 12664 KB Ok
14 Correct 88 ms 12668 KB Ok
15 Correct 75 ms 12792 KB Ok
16 Correct 75 ms 12664 KB Ok
17 Correct 78 ms 12792 KB Ok
18 Correct 75 ms 12664 KB Ok
19 Correct 76 ms 12664 KB Ok
20 Correct 74 ms 12664 KB Ok
21 Correct 75 ms 12664 KB Ok
22 Correct 81 ms 12808 KB Ok
23 Correct 75 ms 12664 KB Ok
24 Correct 79 ms 12792 KB Ok
25 Correct 80 ms 12792 KB Ok
26 Correct 80 ms 12792 KB Ok
27 Correct 87 ms 12808 KB Ok
28 Correct 85 ms 12792 KB Ok
29 Correct 84 ms 12788 KB Ok
30 Correct 87 ms 12792 KB Ok
31 Correct 81 ms 12792 KB Ok
32 Correct 80 ms 12792 KB Ok
33 Correct 79 ms 12664 KB Ok
34 Correct 95 ms 13048 KB Ok
35 Correct 99 ms 12920 KB Ok
36 Correct 98 ms 13020 KB Ok
37 Correct 99 ms 13048 KB Ok
38 Correct 100 ms 12920 KB Ok
39 Correct 103 ms 13100 KB Ok
40 Correct 109 ms 13020 KB Ok
41 Correct 114 ms 13048 KB Ok
42 Correct 98 ms 13048 KB Ok
43 Correct 99 ms 13048 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 12664 KB Ok
2 Correct 75 ms 12664 KB Ok
3 Correct 76 ms 12920 KB Ok
4 Correct 74 ms 12664 KB Ok
5 Correct 75 ms 12664 KB Ok
6 Correct 75 ms 12664 KB Ok
7 Correct 74 ms 12664 KB Ok
8 Correct 81 ms 12792 KB Ok
9 Correct 75 ms 12684 KB Ok
10 Correct 79 ms 12664 KB Ok
11 Correct 75 ms 12792 KB Ok
12 Correct 75 ms 12664 KB Ok
13 Correct 74 ms 12664 KB Ok
14 Correct 76 ms 12684 KB Ok
15 Correct 75 ms 12664 KB Ok
16 Correct 74 ms 12664 KB Ok
17 Correct 78 ms 12636 KB Ok
18 Correct 82 ms 12792 KB Ok
19 Correct 117 ms 13532 KB Ok
20 Correct 94 ms 13020 KB Ok
21 Correct 116 ms 13684 KB Ok
22 Correct 103 ms 13304 KB Ok
23 Correct 40 ms 12664 KB Ok
24 Correct 88 ms 12668 KB Ok
25 Correct 75 ms 12792 KB Ok
26 Correct 75 ms 12664 KB Ok
27 Correct 78 ms 12792 KB Ok
28 Correct 75 ms 12664 KB Ok
29 Correct 76 ms 12664 KB Ok
30 Correct 74 ms 12664 KB Ok
31 Correct 75 ms 12664 KB Ok
32 Correct 81 ms 12808 KB Ok
33 Correct 75 ms 12664 KB Ok
34 Correct 79 ms 12792 KB Ok
35 Correct 80 ms 12792 KB Ok
36 Correct 80 ms 12792 KB Ok
37 Correct 87 ms 12808 KB Ok
38 Correct 85 ms 12792 KB Ok
39 Correct 84 ms 12788 KB Ok
40 Correct 87 ms 12792 KB Ok
41 Correct 81 ms 12792 KB Ok
42 Correct 80 ms 12792 KB Ok
43 Correct 79 ms 12664 KB Ok
44 Correct 95 ms 13048 KB Ok
45 Correct 99 ms 12920 KB Ok
46 Correct 98 ms 13020 KB Ok
47 Correct 99 ms 13048 KB Ok
48 Correct 100 ms 12920 KB Ok
49 Correct 103 ms 13100 KB Ok
50 Correct 109 ms 13020 KB Ok
51 Correct 114 ms 13048 KB Ok
52 Correct 98 ms 13048 KB Ok
53 Correct 99 ms 13048 KB Ok
54 Correct 409 ms 16080 KB Ok
55 Correct 437 ms 16244 KB Ok
56 Correct 452 ms 16664 KB Ok
57 Correct 296 ms 15468 KB Ok
58 Correct 351 ms 15832 KB Ok
59 Correct 316 ms 15824 KB Ok
60 Correct 274 ms 15376 KB Ok
61 Correct 303 ms 15592 KB Ok
62 Correct 404 ms 15956 KB Ok
63 Correct 330 ms 15860 KB Ok
64 Correct 430 ms 16368 KB Ok
65 Correct 376 ms 15988 KB Ok
66 Correct 324 ms 15796 KB Ok
67 Correct 298 ms 15732 KB Ok
68 Correct 332 ms 15976 KB Ok
69 Correct 1500 ms 23536 KB Ok
70 Correct 1668 ms 24184 KB Ok
71 Correct 1248 ms 23896 KB Ok
72 Correct 1652 ms 23704 KB Ok
73 Correct 1259 ms 23788 KB Ok
74 Correct 1149 ms 23532 KB Ok
75 Correct 1217 ms 23284 KB Ok
76 Execution timed out 2049 ms 23464 KB Time limit exceeded
77 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 12664 KB Ok
2 Correct 75 ms 12664 KB Ok
3 Correct 76 ms 12920 KB Ok
4 Correct 74 ms 12664 KB Ok
5 Correct 75 ms 12664 KB Ok
6 Correct 75 ms 12664 KB Ok
7 Correct 74 ms 12664 KB Ok
8 Correct 81 ms 12792 KB Ok
9 Correct 75 ms 12684 KB Ok
10 Correct 79 ms 12664 KB Ok
11 Correct 75 ms 12792 KB Ok
12 Correct 75 ms 12664 KB Ok
13 Correct 74 ms 12664 KB Ok
14 Correct 76 ms 12684 KB Ok
15 Correct 75 ms 12664 KB Ok
16 Correct 74 ms 12664 KB Ok
17 Correct 78 ms 12636 KB Ok
18 Correct 82 ms 12792 KB Ok
19 Correct 117 ms 13532 KB Ok
20 Correct 94 ms 13020 KB Ok
21 Correct 116 ms 13684 KB Ok
22 Correct 103 ms 13304 KB Ok
23 Correct 40 ms 12664 KB Ok
24 Correct 88 ms 12668 KB Ok
25 Correct 75 ms 12792 KB Ok
26 Correct 75 ms 12664 KB Ok
27 Correct 78 ms 12792 KB Ok
28 Correct 75 ms 12664 KB Ok
29 Correct 76 ms 12664 KB Ok
30 Correct 74 ms 12664 KB Ok
31 Correct 75 ms 12664 KB Ok
32 Correct 81 ms 12808 KB Ok
33 Correct 75 ms 12664 KB Ok
34 Correct 74 ms 12664 KB Ok
35 Correct 76 ms 12700 KB Ok
36 Correct 77 ms 12664 KB Ok
37 Correct 77 ms 12704 KB Ok
38 Correct 76 ms 12664 KB Ok
39 Correct 533 ms 23916 KB Ok
40 Correct 467 ms 24304 KB Ok
41 Correct 911 ms 27276 KB Ok
42 Correct 630 ms 25356 KB Ok
43 Correct 352 ms 19148 KB Ok
44 Correct 591 ms 25716 KB Ok
45 Correct 79 ms 12792 KB Ok
46 Correct 80 ms 12792 KB Ok
47 Correct 80 ms 12792 KB Ok
48 Correct 87 ms 12808 KB Ok
49 Correct 85 ms 12792 KB Ok
50 Correct 84 ms 12788 KB Ok
51 Correct 87 ms 12792 KB Ok
52 Correct 81 ms 12792 KB Ok
53 Correct 80 ms 12792 KB Ok
54 Correct 79 ms 12664 KB Ok
55 Correct 95 ms 13048 KB Ok
56 Correct 99 ms 12920 KB Ok
57 Correct 98 ms 13020 KB Ok
58 Correct 99 ms 13048 KB Ok
59 Correct 100 ms 12920 KB Ok
60 Correct 103 ms 13100 KB Ok
61 Correct 109 ms 13020 KB Ok
62 Correct 114 ms 13048 KB Ok
63 Correct 98 ms 13048 KB Ok
64 Correct 99 ms 13048 KB Ok
65 Correct 409 ms 16080 KB Ok
66 Correct 437 ms 16244 KB Ok
67 Correct 452 ms 16664 KB Ok
68 Correct 296 ms 15468 KB Ok
69 Correct 351 ms 15832 KB Ok
70 Correct 316 ms 15824 KB Ok
71 Correct 274 ms 15376 KB Ok
72 Correct 303 ms 15592 KB Ok
73 Correct 404 ms 15956 KB Ok
74 Correct 330 ms 15860 KB Ok
75 Correct 430 ms 16368 KB Ok
76 Correct 376 ms 15988 KB Ok
77 Correct 324 ms 15796 KB Ok
78 Correct 298 ms 15732 KB Ok
79 Correct 332 ms 15976 KB Ok
80 Correct 1500 ms 23536 KB Ok
81 Correct 1668 ms 24184 KB Ok
82 Correct 1248 ms 23896 KB Ok
83 Correct 1652 ms 23704 KB Ok
84 Correct 1259 ms 23788 KB Ok
85 Correct 1149 ms 23532 KB Ok
86 Correct 1217 ms 23284 KB Ok
87 Execution timed out 2049 ms 23464 KB Time limit exceeded
88 Halted 0 ms 0 KB -