oj.uz

Submission #229043

# Submission time Handle Problem Language Result Execution time Memory
229043 2020-05-03T09:50:58 Z davitmarg Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 149964 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 4000006;

int gcd(int a, int b)
{
    if (!a || !b)
        return a + b;
    return gcd(b, a % b);
}

int lca(int a,int b)
{
    return a / gcd(a, b) * b;
}

int q, n, m, k, a[N], used[N], tin[N];
vector<int> t, g[N];

void dfs(int v)
{
    used[v] = 1;
    for (int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i];
        if (used[to])
            continue;
        dfs(to);
    }
    //tin[v] = -t.size();
    t.PB(v);
}

void check(int x)
{
    t.clear();
    for (int i = 0; i <= x; i++)
        g[i].clear();

    for (int i = 0; i <= x; i++)
    {
        if (i - m >= 0)
            g[i - m].PB(i);
        if (i + n <= x)
            g[i + n].PB(i);
    }
    for (int i = 0; i <= x; i++)
        if (!used[i])
            dfs(i);

    int v, to;
    for (int i = t.size() - 1; i >= 0; i--)
    {
        v = t[i];
        a[v] = t.size() - i;
        for (int j = 0; j < g[v].size(); j++)
        {
            to = g[v][j];
            a[to] = a[v] + 1;
        }
    }
}


int main()
{
    cin >> q;
    while (q--)
    {
        k = 0;
        scanf("%d%d", &n, &m);
        k = n + m - gcd(n, m) - 1;
        check(k);
        printf("%d\n", k);
        for (int i = 1; i <= k; i++)
        {
            printf("%d ",a[i] - a[i - 1]);
            used[i] = 0;
        }
        used[0] = 0;
        printf("\n");
    }
    return 0;
}

/*



*/

Compilation message

sequence.cpp: In function 'void dfs(int)':
sequence.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++)
                     ~~^~~~~~~~~~~~~
sequence.cpp: In function 'void check(int)':
sequence.cpp:79:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[v].size(); j++)
                         ~~^~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &n, &m);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94328 KB Ok
2 Correct 64 ms 94328 KB Ok
3 Correct 56 ms 94328 KB Ok
4 Correct 55 ms 94200 KB Ok
5 Correct 54 ms 94328 KB Ok
6 Correct 58 ms 94300 KB Ok
7 Correct 58 ms 94328 KB Ok
8 Correct 59 ms 94332 KB Ok
9 Correct 61 ms 94328 KB Ok
10 Correct 58 ms 94328 KB Ok
11 Correct 57 ms 94332 KB Ok
12 Correct 61 ms 94304 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94432 KB Ok
2 Correct 61 ms 94304 KB Ok
3 Correct 58 ms 94232 KB Ok
4 Correct 61 ms 94312 KB Ok
5 Correct 59 ms 94264 KB Ok
6 Correct 61 ms 94456 KB Ok
7 Correct 70 ms 95224 KB Ok
8 Correct 67 ms 94688 KB Ok
9 Correct 69 ms 95512 KB Ok
10 Correct 69 ms 94832 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94328 KB Ok
2 Correct 59 ms 94336 KB Ok
3 Correct 59 ms 94292 KB Ok
4 Correct 56 ms 94296 KB Ok
5 Correct 62 ms 94200 KB Ok
6 Correct 58 ms 94376 KB Ok
7 Correct 62 ms 94236 KB Ok
8 Correct 60 ms 94200 KB Ok
9 Correct 57 ms 94200 KB Ok
10 Correct 58 ms 94268 KB Ok
11 Correct 56 ms 94328 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 94200 KB Ok
2 Correct 60 ms 94324 KB Ok
3 Correct 60 ms 94240 KB Ok
4 Correct 60 ms 94324 KB Ok
5 Correct 69 ms 94328 KB Ok
6 Correct 180 ms 109916 KB Ok
7 Correct 156 ms 109424 KB Ok
8 Correct 246 ms 112644 KB Ok
9 Correct 211 ms 109808 KB Ok
10 Correct 149 ms 105072 KB Ok
11 Correct 208 ms 113748 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94328 KB Ok
2 Correct 64 ms 94328 KB Ok
3 Correct 56 ms 94328 KB Ok
4 Correct 55 ms 94200 KB Ok
5 Correct 54 ms 94328 KB Ok
6 Correct 58 ms 94300 KB Ok
7 Correct 58 ms 94328 KB Ok
8 Correct 59 ms 94332 KB Ok
9 Correct 61 ms 94328 KB Ok
10 Correct 58 ms 94328 KB Ok
11 Correct 57 ms 94332 KB Ok
12 Correct 61 ms 94304 KB Ok
13 Correct 57 ms 94328 KB Ok
14 Correct 59 ms 94336 KB Ok
15 Correct 59 ms 94292 KB Ok
16 Correct 56 ms 94296 KB Ok
17 Correct 62 ms 94200 KB Ok
18 Correct 58 ms 94376 KB Ok
19 Correct 62 ms 94236 KB Ok
20 Correct 60 ms 94200 KB Ok
21 Correct 57 ms 94200 KB Ok
22 Correct 58 ms 94268 KB Ok
23 Correct 56 ms 94328 KB Ok
24 Correct 61 ms 94456 KB Ok
25 Correct 60 ms 94456 KB Ok
26 Correct 60 ms 94432 KB Ok
27 Correct 64 ms 94432 KB Ok
28 Correct 59 ms 94456 KB Ok
29 Correct 59 ms 94452 KB Ok
30 Correct 62 ms 94456 KB Ok
31 Correct 61 ms 94456 KB Ok
32 Correct 60 ms 94456 KB Ok
33 Correct 64 ms 94560 KB Ok
34 Correct 67 ms 94712 KB Ok
35 Correct 60 ms 94712 KB Ok
36 Correct 65 ms 94712 KB Ok
37 Correct 64 ms 94764 KB Ok
38 Correct 62 ms 94712 KB Ok
39 Correct 62 ms 94584 KB Ok
40 Correct 65 ms 94684 KB Ok
41 Correct 61 ms 94712 KB Ok
42 Correct 62 ms 94712 KB Ok
43 Correct 63 ms 94688 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94328 KB Ok
2 Correct 64 ms 94328 KB Ok
3 Correct 56 ms 94328 KB Ok
4 Correct 55 ms 94200 KB Ok
5 Correct 54 ms 94328 KB Ok
6 Correct 58 ms 94300 KB Ok
7 Correct 58 ms 94328 KB Ok
8 Correct 59 ms 94332 KB Ok
9 Correct 61 ms 94328 KB Ok
10 Correct 58 ms 94328 KB Ok
11 Correct 57 ms 94332 KB Ok
12 Correct 61 ms 94304 KB Ok
13 Correct 62 ms 94432 KB Ok
14 Correct 61 ms 94304 KB Ok
15 Correct 58 ms 94232 KB Ok
16 Correct 61 ms 94312 KB Ok
17 Correct 59 ms 94264 KB Ok
18 Correct 61 ms 94456 KB Ok
19 Correct 70 ms 95224 KB Ok
20 Correct 67 ms 94688 KB Ok
21 Correct 69 ms 95512 KB Ok
22 Correct 69 ms 94832 KB Ok
23 Correct 57 ms 94328 KB Ok
24 Correct 59 ms 94336 KB Ok
25 Correct 59 ms 94292 KB Ok
26 Correct 56 ms 94296 KB Ok
27 Correct 62 ms 94200 KB Ok
28 Correct 58 ms 94376 KB Ok
29 Correct 62 ms 94236 KB Ok
30 Correct 60 ms 94200 KB Ok
31 Correct 57 ms 94200 KB Ok
32 Correct 58 ms 94268 KB Ok
33 Correct 56 ms 94328 KB Ok
34 Correct 61 ms 94456 KB Ok
35 Correct 60 ms 94456 KB Ok
36 Correct 60 ms 94432 KB Ok
37 Correct 64 ms 94432 KB Ok
38 Correct 59 ms 94456 KB Ok
39 Correct 59 ms 94452 KB Ok
40 Correct 62 ms 94456 KB Ok
41 Correct 61 ms 94456 KB Ok
42 Correct 60 ms 94456 KB Ok
43 Correct 64 ms 94560 KB Ok
44 Correct 67 ms 94712 KB Ok
45 Correct 60 ms 94712 KB Ok
46 Correct 65 ms 94712 KB Ok
47 Correct 64 ms 94764 KB Ok
48 Correct 62 ms 94712 KB Ok
49 Correct 62 ms 94584 KB Ok
50 Correct 65 ms 94684 KB Ok
51 Correct 61 ms 94712 KB Ok
52 Correct 62 ms 94712 KB Ok
53 Correct 63 ms 94688 KB Ok
54 Correct 146 ms 100456 KB Ok
55 Correct 154 ms 100828 KB Ok
56 Correct 153 ms 100848 KB Ok
57 Correct 131 ms 99712 KB Ok
58 Correct 155 ms 100624 KB Ok
59 Correct 147 ms 100336 KB Ok
60 Correct 139 ms 99820 KB Ok
61 Correct 131 ms 100204 KB Ok
62 Correct 168 ms 100980 KB Ok
63 Correct 138 ms 100076 KB Ok
64 Correct 155 ms 100716 KB Ok
65 Correct 151 ms 100720 KB Ok
66 Correct 134 ms 100336 KB Ok
67 Correct 130 ms 99948 KB Ok
68 Correct 147 ms 100592 KB Ok
69 Correct 377 ms 107892 KB Ok
70 Correct 430 ms 108020 KB Ok
71 Correct 309 ms 106352 KB Ok
72 Correct 336 ms 107760 KB Ok
73 Correct 380 ms 106740 KB Ok
74 Correct 414 ms 107248 KB Ok
75 Correct 325 ms 107636 KB Ok
76 Correct 396 ms 107764 KB Ok
77 Correct 308 ms 106860 KB Ok
78 Correct 423 ms 107764 KB Ok
79 Correct 348 ms 107380 KB Ok
80 Correct 368 ms 106484 KB Ok
81 Correct 360 ms 107892 KB Ok
82 Correct 350 ms 107480 KB Ok
83 Correct 387 ms 108020 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94328 KB Ok
2 Correct 64 ms 94328 KB Ok
3 Correct 56 ms 94328 KB Ok
4 Correct 55 ms 94200 KB Ok
5 Correct 54 ms 94328 KB Ok
6 Correct 58 ms 94300 KB Ok
7 Correct 58 ms 94328 KB Ok
8 Correct 59 ms 94332 KB Ok
9 Correct 61 ms 94328 KB Ok
10 Correct 58 ms 94328 KB Ok
11 Correct 57 ms 94332 KB Ok
12 Correct 61 ms 94304 KB Ok
13 Correct 62 ms 94432 KB Ok
14 Correct 61 ms 94304 KB Ok
15 Correct 58 ms 94232 KB Ok
16 Correct 61 ms 94312 KB Ok
17 Correct 59 ms 94264 KB Ok
18 Correct 61 ms 94456 KB Ok
19 Correct 70 ms 95224 KB Ok
20 Correct 67 ms 94688 KB Ok
21 Correct 69 ms 95512 KB Ok
22 Correct 69 ms 94832 KB Ok
23 Correct 57 ms 94328 KB Ok
24 Correct 59 ms 94336 KB Ok
25 Correct 59 ms 94292 KB Ok
26 Correct 56 ms 94296 KB Ok
27 Correct 62 ms 94200 KB Ok
28 Correct 58 ms 94376 KB Ok
29 Correct 62 ms 94236 KB Ok
30 Correct 60 ms 94200 KB Ok
31 Correct 57 ms 94200 KB Ok
32 Correct 58 ms 94268 KB Ok
33 Correct 56 ms 94328 KB Ok
34 Correct 61 ms 94200 KB Ok
35 Correct 60 ms 94324 KB Ok
36 Correct 60 ms 94240 KB Ok
37 Correct 60 ms 94324 KB Ok
38 Correct 69 ms 94328 KB Ok
39 Correct 180 ms 109916 KB Ok
40 Correct 156 ms 109424 KB Ok
41 Correct 246 ms 112644 KB Ok
42 Correct 211 ms 109808 KB Ok
43 Correct 149 ms 105072 KB Ok
44 Correct 208 ms 113748 KB Ok
45 Correct 61 ms 94456 KB Ok
46 Correct 60 ms 94456 KB Ok
47 Correct 60 ms 94432 KB Ok
48 Correct 64 ms 94432 KB Ok
49 Correct 59 ms 94456 KB Ok
50 Correct 59 ms 94452 KB Ok
51 Correct 62 ms 94456 KB Ok
52 Correct 61 ms 94456 KB Ok
53 Correct 60 ms 94456 KB Ok
54 Correct 64 ms 94560 KB Ok
55 Correct 67 ms 94712 KB Ok
56 Correct 60 ms 94712 KB Ok
57 Correct 65 ms 94712 KB Ok
58 Correct 64 ms 94764 KB Ok
59 Correct 62 ms 94712 KB Ok
60 Correct 62 ms 94584 KB Ok
61 Correct 65 ms 94684 KB Ok
62 Correct 61 ms 94712 KB Ok
63 Correct 62 ms 94712 KB Ok
64 Correct 63 ms 94688 KB Ok
65 Correct 146 ms 100456 KB Ok
66 Correct 154 ms 100828 KB Ok
67 Correct 153 ms 100848 KB Ok
68 Correct 131 ms 99712 KB Ok
69 Correct 155 ms 100624 KB Ok
70 Correct 147 ms 100336 KB Ok
71 Correct 139 ms 99820 KB Ok
72 Correct 131 ms 100204 KB Ok
73 Correct 168 ms 100980 KB Ok
74 Correct 138 ms 100076 KB Ok
75 Correct 155 ms 100716 KB Ok
76 Correct 151 ms 100720 KB Ok
77 Correct 134 ms 100336 KB Ok
78 Correct 130 ms 99948 KB Ok
79 Correct 147 ms 100592 KB Ok
80 Correct 377 ms 107892 KB Ok
81 Correct 430 ms 108020 KB Ok
82 Correct 309 ms 106352 KB Ok
83 Correct 336 ms 107760 KB Ok
84 Correct 380 ms 106740 KB Ok
85 Correct 414 ms 107248 KB Ok
86 Correct 325 ms 107636 KB Ok
87 Correct 396 ms 107764 KB Ok
88 Correct 308 ms 106860 KB Ok
89 Correct 423 ms 107764 KB Ok
90 Correct 348 ms 107380 KB Ok
91 Correct 368 ms 106484 KB Ok
92 Correct 360 ms 107892 KB Ok
93 Correct 350 ms 107480 KB Ok
94 Correct 387 ms 108020 KB Ok
95 Correct 286 ms 110312 KB Ok
96 Correct 386 ms 118132 KB Ok
97 Correct 391 ms 114020 KB Ok
98 Correct 289 ms 113636 KB Ok
99 Correct 326 ms 113128 KB Ok
100 Correct 355 ms 113484 KB Ok
101 Correct 342 ms 115684 KB Ok
102 Correct 323 ms 114148 KB Ok
103 Correct 334 ms 115404 KB Ok
104 Correct 376 ms 116964 KB Ok
105 Correct 385 ms 117612 KB Ok
106 Correct 313 ms 116708 KB Ok
107 Correct 370 ms 116452 KB Ok
108 Correct 406 ms 117764 KB Ok
109 Correct 354 ms 118124 KB Ok
110 Execution timed out 2001 ms 149964 KB Time limit exceeded
111 Halted 0 ms 0 KB -