oj.uz

Submission #234120

# Submission time Handle Problem Language Result Execution time Memory
234120 2020-05-23T08:08:39 Z davitmarg Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 149992 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)
{
    while (a && b)
    {
        a %= b;
        swap(a, b);
    }
    return a + 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()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> q;
    while (q--)
    {
        cin >> n >> m;
        k = n + m - gcd(n, m) - 1;
        check(k);
        cout << k << "\n";
        for (int i = 1; i <= k; i++)
        {
            cout << (a[i] - a[i - 1]) << " ";
            used[i] = 0;
        }
        used[0] = 0;
        cout << "\n";
    }
    return 0;
}

/*



*/

Compilation message

sequence.cpp: In function 'void dfs(int)':
sequence.cpp:44: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:77:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[v].size(); j++)
                         ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94456 KB Ok
2 Correct 58 ms 94328 KB Ok
3 Correct 66 ms 94328 KB Ok
4 Correct 68 ms 94328 KB Ok
5 Correct 57 ms 94328 KB Ok
6 Correct 61 ms 94328 KB Ok
7 Correct 68 ms 94328 KB Ok
8 Correct 57 ms 94328 KB Ok
9 Correct 59 ms 94328 KB Ok
10 Correct 58 ms 94328 KB Ok
11 Correct 60 ms 94328 KB Ok
12 Correct 60 ms 94328 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 94328 KB Ok
2 Correct 61 ms 94328 KB Ok
3 Correct 58 ms 94328 KB Ok
4 Correct 58 ms 94328 KB Ok
5 Correct 69 ms 94336 KB Ok
6 Correct 60 ms 94456 KB Ok
7 Correct 70 ms 95352 KB Ok
8 Correct 63 ms 94712 KB Ok
9 Correct 77 ms 95480 KB Ok
10 Correct 65 ms 94840 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94328 KB Ok
2 Correct 59 ms 94328 KB Ok
3 Correct 59 ms 94328 KB Ok
4 Correct 57 ms 94328 KB Ok
5 Correct 58 ms 94328 KB Ok
6 Correct 59 ms 94336 KB Ok
7 Correct 60 ms 94336 KB Ok
8 Correct 68 ms 94328 KB Ok
9 Correct 63 ms 94328 KB Ok
10 Correct 60 ms 94456 KB Ok
11 Correct 57 ms 94328 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 94332 KB Ok
2 Correct 59 ms 94328 KB Ok
3 Correct 57 ms 94328 KB Ok
4 Correct 60 ms 94328 KB Ok
5 Correct 60 ms 94328 KB Ok
6 Correct 162 ms 109932 KB Ok
7 Correct 153 ms 109548 KB Ok
8 Correct 215 ms 112620 KB Ok
9 Correct 192 ms 109800 KB Ok
10 Correct 140 ms 105072 KB Ok
11 Correct 200 ms 113772 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94456 KB Ok
2 Correct 58 ms 94328 KB Ok
3 Correct 66 ms 94328 KB Ok
4 Correct 68 ms 94328 KB Ok
5 Correct 57 ms 94328 KB Ok
6 Correct 61 ms 94328 KB Ok
7 Correct 68 ms 94328 KB Ok
8 Correct 57 ms 94328 KB Ok
9 Correct 59 ms 94328 KB Ok
10 Correct 58 ms 94328 KB Ok
11 Correct 60 ms 94328 KB Ok
12 Correct 60 ms 94328 KB Ok
13 Correct 59 ms 94328 KB Ok
14 Correct 59 ms 94328 KB Ok
15 Correct 59 ms 94328 KB Ok
16 Correct 57 ms 94328 KB Ok
17 Correct 58 ms 94328 KB Ok
18 Correct 59 ms 94336 KB Ok
19 Correct 60 ms 94336 KB Ok
20 Correct 68 ms 94328 KB Ok
21 Correct 63 ms 94328 KB Ok
22 Correct 60 ms 94456 KB Ok
23 Correct 57 ms 94328 KB Ok
24 Correct 59 ms 94456 KB Ok
25 Correct 63 ms 94456 KB Ok
26 Correct 61 ms 94456 KB Ok
27 Correct 59 ms 94456 KB Ok
28 Correct 59 ms 94456 KB Ok
29 Correct 58 ms 94456 KB Ok
30 Correct 68 ms 94584 KB Ok
31 Correct 61 ms 94456 KB Ok
32 Correct 75 ms 94456 KB Ok
33 Correct 60 ms 94464 KB Ok
34 Correct 62 ms 94712 KB Ok
35 Correct 62 ms 94712 KB Ok
36 Correct 63 ms 94720 KB Ok
37 Correct 61 ms 94688 KB Ok
38 Correct 64 ms 94716 KB Ok
39 Correct 61 ms 94712 KB Ok
40 Correct 65 ms 94712 KB Ok
41 Correct 61 ms 94712 KB Ok
42 Correct 64 ms 94712 KB Ok
43 Correct 63 ms 94708 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94456 KB Ok
2 Correct 58 ms 94328 KB Ok
3 Correct 66 ms 94328 KB Ok
4 Correct 68 ms 94328 KB Ok
5 Correct 57 ms 94328 KB Ok
6 Correct 61 ms 94328 KB Ok
7 Correct 68 ms 94328 KB Ok
8 Correct 57 ms 94328 KB Ok
9 Correct 59 ms 94328 KB Ok
10 Correct 58 ms 94328 KB Ok
11 Correct 60 ms 94328 KB Ok
12 Correct 60 ms 94328 KB Ok
13 Correct 56 ms 94328 KB Ok
14 Correct 61 ms 94328 KB Ok
15 Correct 58 ms 94328 KB Ok
16 Correct 58 ms 94328 KB Ok
17 Correct 69 ms 94336 KB Ok
18 Correct 60 ms 94456 KB Ok
19 Correct 70 ms 95352 KB Ok
20 Correct 63 ms 94712 KB Ok
21 Correct 77 ms 95480 KB Ok
22 Correct 65 ms 94840 KB Ok
23 Correct 59 ms 94328 KB Ok
24 Correct 59 ms 94328 KB Ok
25 Correct 59 ms 94328 KB Ok
26 Correct 57 ms 94328 KB Ok
27 Correct 58 ms 94328 KB Ok
28 Correct 59 ms 94336 KB Ok
29 Correct 60 ms 94336 KB Ok
30 Correct 68 ms 94328 KB Ok
31 Correct 63 ms 94328 KB Ok
32 Correct 60 ms 94456 KB Ok
33 Correct 57 ms 94328 KB Ok
34 Correct 59 ms 94456 KB Ok
35 Correct 63 ms 94456 KB Ok
36 Correct 61 ms 94456 KB Ok
37 Correct 59 ms 94456 KB Ok
38 Correct 59 ms 94456 KB Ok
39 Correct 58 ms 94456 KB Ok
40 Correct 68 ms 94584 KB Ok
41 Correct 61 ms 94456 KB Ok
42 Correct 75 ms 94456 KB Ok
43 Correct 60 ms 94464 KB Ok
44 Correct 62 ms 94712 KB Ok
45 Correct 62 ms 94712 KB Ok
46 Correct 63 ms 94720 KB Ok
47 Correct 61 ms 94688 KB Ok
48 Correct 64 ms 94716 KB Ok
49 Correct 61 ms 94712 KB Ok
50 Correct 65 ms 94712 KB Ok
51 Correct 61 ms 94712 KB Ok
52 Correct 64 ms 94712 KB Ok
53 Correct 63 ms 94708 KB Ok
54 Correct 137 ms 100464 KB Ok
55 Correct 172 ms 101020 KB Ok
56 Correct 154 ms 100848 KB Ok
57 Correct 137 ms 99700 KB Ok
58 Correct 142 ms 100724 KB Ok
59 Correct 146 ms 100336 KB Ok
60 Correct 136 ms 99968 KB Ok
61 Correct 128 ms 100212 KB Ok
62 Correct 156 ms 101076 KB Ok
63 Correct 137 ms 100124 KB Ok
64 Correct 148 ms 100724 KB Ok
65 Correct 140 ms 100724 KB Ok
66 Correct 125 ms 100340 KB Ok
67 Correct 119 ms 99956 KB Ok
68 Correct 148 ms 100612 KB Ok
69 Correct 371 ms 107900 KB Ok
70 Correct 400 ms 108016 KB Ok
71 Correct 318 ms 106480 KB Ok
72 Correct 371 ms 107888 KB Ok
73 Correct 447 ms 106824 KB Ok
74 Correct 342 ms 107244 KB Ok
75 Correct 323 ms 107676 KB Ok
76 Correct 421 ms 107944 KB Ok
77 Correct 367 ms 107116 KB Ok
78 Correct 371 ms 107888 KB Ok
79 Correct 369 ms 107496 KB Ok
80 Correct 357 ms 106480 KB Ok
81 Correct 332 ms 107924 KB Ok
82 Correct 317 ms 107248 KB Ok
83 Correct 331 ms 107888 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94456 KB Ok
2 Correct 58 ms 94328 KB Ok
3 Correct 66 ms 94328 KB Ok
4 Correct 68 ms 94328 KB Ok
5 Correct 57 ms 94328 KB Ok
6 Correct 61 ms 94328 KB Ok
7 Correct 68 ms 94328 KB Ok
8 Correct 57 ms 94328 KB Ok
9 Correct 59 ms 94328 KB Ok
10 Correct 58 ms 94328 KB Ok
11 Correct 60 ms 94328 KB Ok
12 Correct 60 ms 94328 KB Ok
13 Correct 56 ms 94328 KB Ok
14 Correct 61 ms 94328 KB Ok
15 Correct 58 ms 94328 KB Ok
16 Correct 58 ms 94328 KB Ok
17 Correct 69 ms 94336 KB Ok
18 Correct 60 ms 94456 KB Ok
19 Correct 70 ms 95352 KB Ok
20 Correct 63 ms 94712 KB Ok
21 Correct 77 ms 95480 KB Ok
22 Correct 65 ms 94840 KB Ok
23 Correct 59 ms 94328 KB Ok
24 Correct 59 ms 94328 KB Ok
25 Correct 59 ms 94328 KB Ok
26 Correct 57 ms 94328 KB Ok
27 Correct 58 ms 94328 KB Ok
28 Correct 59 ms 94336 KB Ok
29 Correct 60 ms 94336 KB Ok
30 Correct 68 ms 94328 KB Ok
31 Correct 63 ms 94328 KB Ok
32 Correct 60 ms 94456 KB Ok
33 Correct 57 ms 94328 KB Ok
34 Correct 58 ms 94332 KB Ok
35 Correct 59 ms 94328 KB Ok
36 Correct 57 ms 94328 KB Ok
37 Correct 60 ms 94328 KB Ok
38 Correct 60 ms 94328 KB Ok
39 Correct 162 ms 109932 KB Ok
40 Correct 153 ms 109548 KB Ok
41 Correct 215 ms 112620 KB Ok
42 Correct 192 ms 109800 KB Ok
43 Correct 140 ms 105072 KB Ok
44 Correct 200 ms 113772 KB Ok
45 Correct 59 ms 94456 KB Ok
46 Correct 63 ms 94456 KB Ok
47 Correct 61 ms 94456 KB Ok
48 Correct 59 ms 94456 KB Ok
49 Correct 59 ms 94456 KB Ok
50 Correct 58 ms 94456 KB Ok
51 Correct 68 ms 94584 KB Ok
52 Correct 61 ms 94456 KB Ok
53 Correct 75 ms 94456 KB Ok
54 Correct 60 ms 94464 KB Ok
55 Correct 62 ms 94712 KB Ok
56 Correct 62 ms 94712 KB Ok
57 Correct 63 ms 94720 KB Ok
58 Correct 61 ms 94688 KB Ok
59 Correct 64 ms 94716 KB Ok
60 Correct 61 ms 94712 KB Ok
61 Correct 65 ms 94712 KB Ok
62 Correct 61 ms 94712 KB Ok
63 Correct 64 ms 94712 KB Ok
64 Correct 63 ms 94708 KB Ok
65 Correct 137 ms 100464 KB Ok
66 Correct 172 ms 101020 KB Ok
67 Correct 154 ms 100848 KB Ok
68 Correct 137 ms 99700 KB Ok
69 Correct 142 ms 100724 KB Ok
70 Correct 146 ms 100336 KB Ok
71 Correct 136 ms 99968 KB Ok
72 Correct 128 ms 100212 KB Ok
73 Correct 156 ms 101076 KB Ok
74 Correct 137 ms 100124 KB Ok
75 Correct 148 ms 100724 KB Ok
76 Correct 140 ms 100724 KB Ok
77 Correct 125 ms 100340 KB Ok
78 Correct 119 ms 99956 KB Ok
79 Correct 148 ms 100612 KB Ok
80 Correct 371 ms 107900 KB Ok
81 Correct 400 ms 108016 KB Ok
82 Correct 318 ms 106480 KB Ok
83 Correct 371 ms 107888 KB Ok
84 Correct 447 ms 106824 KB Ok
85 Correct 342 ms 107244 KB Ok
86 Correct 323 ms 107676 KB Ok
87 Correct 421 ms 107944 KB Ok
88 Correct 367 ms 107116 KB Ok
89 Correct 371 ms 107888 KB Ok
90 Correct 369 ms 107496 KB Ok
91 Correct 357 ms 106480 KB Ok
92 Correct 332 ms 107924 KB Ok
93 Correct 317 ms 107248 KB Ok
94 Correct 331 ms 107888 KB Ok
95 Correct 275 ms 110320 KB Ok
96 Correct 365 ms 118096 KB Ok
97 Correct 368 ms 114148 KB Ok
98 Correct 274 ms 113644 KB Ok
99 Correct 306 ms 113252 KB Ok
100 Correct 313 ms 113512 KB Ok
101 Correct 312 ms 115688 KB Ok
102 Correct 308 ms 114152 KB Ok
103 Correct 313 ms 115428 KB Ok
104 Correct 359 ms 117096 KB Ok
105 Correct 369 ms 117860 KB Ok
106 Correct 303 ms 116840 KB Ok
107 Correct 325 ms 116460 KB Ok
108 Correct 370 ms 117896 KB Ok
109 Correct 324 ms 118116 KB Ok
110 Execution timed out 2071 ms 149992 KB Time limit exceeded
111 Halted 0 ms 0 KB -