oj.uz

Submission #234113

# Submission time Handle Problem Language Result Execution time Memory
234113 2020-05-23T07:59:43 Z davitmarg Nice sequence (IZhO18_sequence) C++17
43 / 100
 2000 ms 112136 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()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.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]) << endl;
            used[i] = 0;
        }
        used[0] = 0;
        cout << "\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++)
                         ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94328 KB Ok
2 Correct 54 ms 94328 KB Ok
3 Correct 56 ms 94328 KB Ok
4 Correct 53 ms 94328 KB Ok
5 Correct 54 ms 94328 KB Ok
6 Correct 54 ms 94328 KB Ok
7 Correct 53 ms 94328 KB Ok
8 Correct 53 ms 94328 KB Ok
9 Correct 55 ms 94328 KB Ok
10 Correct 55 ms 94328 KB Ok
11 Correct 56 ms 94332 KB Ok
12 Correct 57 ms 94328 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94236 KB Ok
2 Correct 55 ms 94328 KB Ok
3 Correct 54 ms 94328 KB Ok
4 Correct 54 ms 94332 KB Ok
5 Correct 54 ms 94328 KB Ok
6 Correct 86 ms 94456 KB Ok
7 Correct 214 ms 95224 KB Ok
8 Correct 126 ms 94840 KB Ok
9 Correct 241 ms 95484 KB Ok
10 Correct 160 ms 94996 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94328 KB Ok
2 Correct 53 ms 94332 KB Ok
3 Correct 54 ms 94328 KB Ok
4 Correct 54 ms 94328 KB Ok
5 Correct 53 ms 94328 KB Ok
6 Correct 53 ms 94312 KB Ok
7 Correct 53 ms 94328 KB Ok
8 Correct 53 ms 94328 KB Ok
9 Correct 53 ms 94328 KB Ok
10 Correct 53 ms 94328 KB Ok
11 Correct 54 ms 94328 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94328 KB Ok
2 Correct 55 ms 94328 KB Ok
3 Correct 55 ms 94328 KB Ok
4 Correct 55 ms 94328 KB Ok
5 Correct 55 ms 94328 KB Ok
6 Correct 1573 ms 109932 KB Ok
7 Correct 1310 ms 109528 KB Ok
8 Execution timed out 2086 ms 112136 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94328 KB Ok
2 Correct 54 ms 94328 KB Ok
3 Correct 56 ms 94328 KB Ok
4 Correct 53 ms 94328 KB Ok
5 Correct 54 ms 94328 KB Ok
6 Correct 54 ms 94328 KB Ok
7 Correct 53 ms 94328 KB Ok
8 Correct 53 ms 94328 KB Ok
9 Correct 55 ms 94328 KB Ok
10 Correct 55 ms 94328 KB Ok
11 Correct 56 ms 94332 KB Ok
12 Correct 57 ms 94328 KB Ok
13 Correct 53 ms 94328 KB Ok
14 Correct 53 ms 94332 KB Ok
15 Correct 54 ms 94328 KB Ok
16 Correct 54 ms 94328 KB Ok
17 Correct 53 ms 94328 KB Ok
18 Correct 53 ms 94312 KB Ok
19 Correct 53 ms 94328 KB Ok
20 Correct 53 ms 94328 KB Ok
21 Correct 53 ms 94328 KB Ok
22 Correct 53 ms 94328 KB Ok
23 Correct 54 ms 94328 KB Ok
24 Correct 88 ms 94584 KB Ok
25 Correct 86 ms 94556 KB Ok
26 Correct 89 ms 94456 KB Ok
27 Correct 87 ms 94456 KB Ok
28 Correct 81 ms 94456 KB Ok
29 Correct 78 ms 94456 KB Ok
30 Correct 78 ms 94456 KB Ok
31 Correct 87 ms 94456 KB Ok
32 Correct 89 ms 94456 KB Ok
33 Correct 88 ms 94456 KB Ok
34 Correct 118 ms 94712 KB Ok
35 Correct 121 ms 94712 KB Ok
36 Correct 119 ms 94712 KB Ok
37 Correct 113 ms 94852 KB Ok
38 Correct 116 ms 94712 KB Ok
39 Correct 123 ms 94712 KB Ok
40 Correct 117 ms 94716 KB Ok
41 Correct 116 ms 94712 KB Ok
42 Correct 123 ms 94712 KB Ok
43 Correct 120 ms 94716 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94328 KB Ok
2 Correct 54 ms 94328 KB Ok
3 Correct 56 ms 94328 KB Ok
4 Correct 53 ms 94328 KB Ok
5 Correct 54 ms 94328 KB Ok
6 Correct 54 ms 94328 KB Ok
7 Correct 53 ms 94328 KB Ok
8 Correct 53 ms 94328 KB Ok
9 Correct 55 ms 94328 KB Ok
10 Correct 55 ms 94328 KB Ok
11 Correct 56 ms 94332 KB Ok
12 Correct 57 ms 94328 KB Ok
13 Correct 54 ms 94236 KB Ok
14 Correct 55 ms 94328 KB Ok
15 Correct 54 ms 94328 KB Ok
16 Correct 54 ms 94332 KB Ok
17 Correct 54 ms 94328 KB Ok
18 Correct 86 ms 94456 KB Ok
19 Correct 214 ms 95224 KB Ok
20 Correct 126 ms 94840 KB Ok
21 Correct 241 ms 95484 KB Ok
22 Correct 160 ms 94996 KB Ok
23 Correct 53 ms 94328 KB Ok
24 Correct 53 ms 94332 KB Ok
25 Correct 54 ms 94328 KB Ok
26 Correct 54 ms 94328 KB Ok
27 Correct 53 ms 94328 KB Ok
28 Correct 53 ms 94312 KB Ok
29 Correct 53 ms 94328 KB Ok
30 Correct 53 ms 94328 KB Ok
31 Correct 53 ms 94328 KB Ok
32 Correct 53 ms 94328 KB Ok
33 Correct 54 ms 94328 KB Ok
34 Correct 88 ms 94584 KB Ok
35 Correct 86 ms 94556 KB Ok
36 Correct 89 ms 94456 KB Ok
37 Correct 87 ms 94456 KB Ok
38 Correct 81 ms 94456 KB Ok
39 Correct 78 ms 94456 KB Ok
40 Correct 78 ms 94456 KB Ok
41 Correct 87 ms 94456 KB Ok
42 Correct 89 ms 94456 KB Ok
43 Correct 88 ms 94456 KB Ok
44 Correct 118 ms 94712 KB Ok
45 Correct 121 ms 94712 KB Ok
46 Correct 119 ms 94712 KB Ok
47 Correct 113 ms 94852 KB Ok
48 Correct 116 ms 94712 KB Ok
49 Correct 123 ms 94712 KB Ok
50 Correct 117 ms 94716 KB Ok
51 Correct 116 ms 94712 KB Ok
52 Correct 123 ms 94712 KB Ok
53 Correct 120 ms 94716 KB Ok
54 Correct 1317 ms 100444 KB Ok
55 Correct 1527 ms 100980 KB Ok
56 Correct 1508 ms 101024 KB Ok
57 Correct 1170 ms 99828 KB Ok
58 Correct 1432 ms 100812 KB Ok
59 Correct 1373 ms 100332 KB Ok
60 Correct 1223 ms 100096 KB Ok
61 Correct 1189 ms 100472 KB Ok
62 Correct 1531 ms 101360 KB Ok
63 Correct 1263 ms 100212 KB Ok
64 Correct 1485 ms 101108 KB Ok
65 Correct 1423 ms 100852 KB Ok
66 Correct 1285 ms 100676 KB Ok
67 Correct 1150 ms 100340 KB Ok
68 Correct 1303 ms 100808 KB Ok
69 Execution timed out 2025 ms 108144 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94328 KB Ok
2 Correct 54 ms 94328 KB Ok
3 Correct 56 ms 94328 KB Ok
4 Correct 53 ms 94328 KB Ok
5 Correct 54 ms 94328 KB Ok
6 Correct 54 ms 94328 KB Ok
7 Correct 53 ms 94328 KB Ok
8 Correct 53 ms 94328 KB Ok
9 Correct 55 ms 94328 KB Ok
10 Correct 55 ms 94328 KB Ok
11 Correct 56 ms 94332 KB Ok
12 Correct 57 ms 94328 KB Ok
13 Correct 54 ms 94236 KB Ok
14 Correct 55 ms 94328 KB Ok
15 Correct 54 ms 94328 KB Ok
16 Correct 54 ms 94332 KB Ok
17 Correct 54 ms 94328 KB Ok
18 Correct 86 ms 94456 KB Ok
19 Correct 214 ms 95224 KB Ok
20 Correct 126 ms 94840 KB Ok
21 Correct 241 ms 95484 KB Ok
22 Correct 160 ms 94996 KB Ok
23 Correct 53 ms 94328 KB Ok
24 Correct 53 ms 94332 KB Ok
25 Correct 54 ms 94328 KB Ok
26 Correct 54 ms 94328 KB Ok
27 Correct 53 ms 94328 KB Ok
28 Correct 53 ms 94312 KB Ok
29 Correct 53 ms 94328 KB Ok
30 Correct 53 ms 94328 KB Ok
31 Correct 53 ms 94328 KB Ok
32 Correct 53 ms 94328 KB Ok
33 Correct 54 ms 94328 KB Ok
34 Correct 53 ms 94328 KB Ok
35 Correct 55 ms 94328 KB Ok
36 Correct 55 ms 94328 KB Ok
37 Correct 55 ms 94328 KB Ok
38 Correct 55 ms 94328 KB Ok
39 Correct 1573 ms 109932 KB Ok
40 Correct 1310 ms 109528 KB Ok
41 Execution timed out 2086 ms 112136 KB Time limit exceeded
42 Halted 0 ms 0 KB -