oj.uz

Submission #173801

# Submission time Handle Problem Language Result Execution time Memory
173801 2020-01-05T12:43:58 Z davitmarg Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 50196 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 = 200005;

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

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

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

inline 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);
}

bool check(int x)
{
    t.clear();
    a.resize(x + 2);
    used.resize(x + 2);
    tin.resize(x + 2);
    g.resize(x + 2);
    for (int i = 0; i <= x; i++)
    {
        g[i].clear();
        used[i] = 0;
        a[i] = i;
    }

    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);
    reverse(all(t));
    //cout << "!!!!!" << x << endl;
    for (int i = 0; i < t.size(); i++)
    {
        int v = t[i];
        for (int j = 0; j < g[v].size(); j++)
        {
            int to = g[v][j];
            if (tin[to] <= tin[v])
                return 0;
            //cout << v << " : " << to << endl;
            a[to] = max(a[to], a[v] + 1);
        }
    }
    return 1;
}

int main()
{
    cin >> q;
    while (q--)
    {
        k = 0;
        cin >> n >> m;
        LL l, r, mid;
        l = 0;
        // r = min(lca(n, m) - 1ll, 400000ll);
        // while (l <= r)
        // {
        //     mid = (l + r) / 2;
        //     if (check(mid))
        //     {
        //         k = mid;
        //         l = mid + 1;
        //     }
        //     else
        //         r = mid - 1;
        // }
        k = n + m - gcd(n, m) - 1;
        check(k);
        cout << k << endl;
        for (int i = 1; i <= k; i++)
            printf("%d ", a[i] - a[i - 1]);
        cout << endl;
    }
    return 0;
}

/*
 
4
3 1
2 3
1 1
2 2
 
 
*/

Compilation message

sequence.cpp: In function 'void dfs(int)':
sequence.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++)
                     ~~^~~~~~~~~~~~~
sequence.cpp: In function 'bool check(int)':
sequence.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < t.size(); i++)
                     ~~^~~~~~~~~~
sequence.cpp:87: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:106:12: warning: variable 'l' set but not used [-Wunused-but-set-variable]
         LL l, r, mid;
            ^
sequence.cpp:106:15: warning: unused variable 'r' [-Wunused-variable]
         LL l, r, mid;
               ^
sequence.cpp:106:18: warning: unused variable 'mid' [-Wunused-variable]
         LL l, r, mid;
                  ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Ok
2 Correct 2 ms 380 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 3 ms 376 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 256 KB Ok
11 Correct 2 ms 256 KB Ok
12 Correct 2 ms 376 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Ok
2 Correct 2 ms 376 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 4 ms 504 KB Ok
7 Correct 13 ms 1456 KB Ok
8 Correct 7 ms 888 KB Ok
9 Correct 16 ms 1676 KB Ok
10 Correct 10 ms 1136 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Ok
2 Correct 4 ms 504 KB Ok
3 Correct 2 ms 256 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 380 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 376 KB Ok
9 Correct 2 ms 256 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 2 ms 376 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Ok
2 Correct 2 ms 256 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 256 KB Ok
6 Correct 131 ms 17748 KB Ok
7 Correct 115 ms 19552 KB Ok
8 Correct 203 ms 21216 KB Ok
9 Correct 166 ms 18596 KB Ok
10 Correct 104 ms 12192 KB Ok
11 Correct 165 ms 21604 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Ok
2 Correct 2 ms 380 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 3 ms 376 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 256 KB Ok
11 Correct 2 ms 256 KB Ok
12 Correct 2 ms 376 KB Ok
13 Correct 2 ms 256 KB Ok
14 Correct 4 ms 504 KB Ok
15 Correct 2 ms 256 KB Ok
16 Correct 2 ms 256 KB Ok
17 Correct 2 ms 376 KB Ok
18 Correct 2 ms 380 KB Ok
19 Correct 2 ms 376 KB Ok
20 Correct 2 ms 376 KB Ok
21 Correct 2 ms 256 KB Ok
22 Correct 2 ms 376 KB Ok
23 Correct 2 ms 376 KB Ok
24 Correct 4 ms 632 KB Ok
25 Correct 4 ms 632 KB Ok
26 Correct 4 ms 632 KB Ok
27 Correct 4 ms 504 KB Ok
28 Correct 4 ms 504 KB Ok
29 Correct 4 ms 504 KB Ok
30 Correct 4 ms 504 KB Ok
31 Correct 4 ms 632 KB Ok
32 Correct 5 ms 604 KB Ok
33 Correct 4 ms 632 KB Ok
34 Correct 7 ms 888 KB Ok
35 Correct 7 ms 888 KB Ok
36 Correct 8 ms 888 KB Ok
37 Correct 8 ms 888 KB Ok
38 Correct 8 ms 888 KB Ok
39 Correct 7 ms 760 KB Ok
40 Correct 8 ms 888 KB Ok
41 Correct 7 ms 764 KB Ok
42 Correct 8 ms 760 KB Ok
43 Correct 8 ms 888 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Ok
2 Correct 2 ms 380 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 3 ms 376 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 256 KB Ok
11 Correct 2 ms 256 KB Ok
12 Correct 2 ms 376 KB Ok
13 Correct 2 ms 256 KB Ok
14 Correct 2 ms 376 KB Ok
15 Correct 2 ms 376 KB Ok
16 Correct 2 ms 376 KB Ok
17 Correct 2 ms 376 KB Ok
18 Correct 4 ms 504 KB Ok
19 Correct 13 ms 1456 KB Ok
20 Correct 7 ms 888 KB Ok
21 Correct 16 ms 1676 KB Ok
22 Correct 10 ms 1136 KB Ok
23 Correct 2 ms 256 KB Ok
24 Correct 4 ms 504 KB Ok
25 Correct 2 ms 256 KB Ok
26 Correct 2 ms 256 KB Ok
27 Correct 2 ms 376 KB Ok
28 Correct 2 ms 380 KB Ok
29 Correct 2 ms 376 KB Ok
30 Correct 2 ms 376 KB Ok
31 Correct 2 ms 256 KB Ok
32 Correct 2 ms 376 KB Ok
33 Correct 2 ms 376 KB Ok
34 Correct 4 ms 632 KB Ok
35 Correct 4 ms 632 KB Ok
36 Correct 4 ms 632 KB Ok
37 Correct 4 ms 504 KB Ok
38 Correct 4 ms 504 KB Ok
39 Correct 4 ms 504 KB Ok
40 Correct 4 ms 504 KB Ok
41 Correct 4 ms 632 KB Ok
42 Correct 5 ms 604 KB Ok
43 Correct 4 ms 632 KB Ok
44 Correct 7 ms 888 KB Ok
45 Correct 7 ms 888 KB Ok
46 Correct 8 ms 888 KB Ok
47 Correct 8 ms 888 KB Ok
48 Correct 8 ms 888 KB Ok
49 Correct 7 ms 760 KB Ok
50 Correct 8 ms 888 KB Ok
51 Correct 7 ms 764 KB Ok
52 Correct 8 ms 760 KB Ok
53 Correct 8 ms 888 KB Ok
54 Correct 100 ms 9000 KB Ok
55 Correct 115 ms 8388 KB Ok
56 Correct 111 ms 8592 KB Ok
57 Correct 84 ms 7444 KB Ok
58 Correct 120 ms 8880 KB Ok
59 Correct 105 ms 7764 KB Ok
60 Correct 91 ms 7404 KB Ok
61 Correct 91 ms 8588 KB Ok
62 Correct 123 ms 8496 KB Ok
63 Correct 95 ms 7364 KB Ok
64 Correct 137 ms 8324 KB Ok
65 Correct 111 ms 8504 KB Ok
66 Correct 95 ms 7960 KB Ok
67 Correct 86 ms 8112 KB Ok
68 Correct 104 ms 8164 KB Ok
69 Correct 278 ms 14516 KB Ok
70 Correct 402 ms 15676 KB Ok
71 Correct 331 ms 12852 KB Ok
72 Correct 326 ms 15028 KB Ok
73 Correct 339 ms 13492 KB Ok
74 Correct 298 ms 12856 KB Ok
75 Correct 329 ms 13172 KB Ok
76 Correct 374 ms 15544 KB Ok
77 Correct 318 ms 12424 KB Ok
78 Correct 338 ms 15312 KB Ok
79 Correct 375 ms 14400 KB Ok
80 Correct 292 ms 13628 KB Ok
81 Correct 307 ms 14800 KB Ok
82 Correct 307 ms 14256 KB Ok
83 Correct 315 ms 13492 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Ok
2 Correct 2 ms 380 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 3 ms 376 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 256 KB Ok
11 Correct 2 ms 256 KB Ok
12 Correct 2 ms 376 KB Ok
13 Correct 2 ms 256 KB Ok
14 Correct 2 ms 376 KB Ok
15 Correct 2 ms 376 KB Ok
16 Correct 2 ms 376 KB Ok
17 Correct 2 ms 376 KB Ok
18 Correct 4 ms 504 KB Ok
19 Correct 13 ms 1456 KB Ok
20 Correct 7 ms 888 KB Ok
21 Correct 16 ms 1676 KB Ok
22 Correct 10 ms 1136 KB Ok
23 Correct 2 ms 256 KB Ok
24 Correct 4 ms 504 KB Ok
25 Correct 2 ms 256 KB Ok
26 Correct 2 ms 256 KB Ok
27 Correct 2 ms 376 KB Ok
28 Correct 2 ms 380 KB Ok
29 Correct 2 ms 376 KB Ok
30 Correct 2 ms 376 KB Ok
31 Correct 2 ms 256 KB Ok
32 Correct 2 ms 376 KB Ok
33 Correct 2 ms 376 KB Ok
34 Correct 2 ms 256 KB Ok
35 Correct 2 ms 256 KB Ok
36 Correct 2 ms 376 KB Ok
37 Correct 2 ms 256 KB Ok
38 Correct 2 ms 256 KB Ok
39 Correct 131 ms 17748 KB Ok
40 Correct 115 ms 19552 KB Ok
41 Correct 203 ms 21216 KB Ok
42 Correct 166 ms 18596 KB Ok
43 Correct 104 ms 12192 KB Ok
44 Correct 165 ms 21604 KB Ok
45 Correct 4 ms 632 KB Ok
46 Correct 4 ms 632 KB Ok
47 Correct 4 ms 632 KB Ok
48 Correct 4 ms 504 KB Ok
49 Correct 4 ms 504 KB Ok
50 Correct 4 ms 504 KB Ok
51 Correct 4 ms 504 KB Ok
52 Correct 4 ms 632 KB Ok
53 Correct 5 ms 604 KB Ok
54 Correct 4 ms 632 KB Ok
55 Correct 7 ms 888 KB Ok
56 Correct 7 ms 888 KB Ok
57 Correct 8 ms 888 KB Ok
58 Correct 8 ms 888 KB Ok
59 Correct 8 ms 888 KB Ok
60 Correct 7 ms 760 KB Ok
61 Correct 8 ms 888 KB Ok
62 Correct 7 ms 764 KB Ok
63 Correct 8 ms 760 KB Ok
64 Correct 8 ms 888 KB Ok
65 Correct 100 ms 9000 KB Ok
66 Correct 115 ms 8388 KB Ok
67 Correct 111 ms 8592 KB Ok
68 Correct 84 ms 7444 KB Ok
69 Correct 120 ms 8880 KB Ok
70 Correct 105 ms 7764 KB Ok
71 Correct 91 ms 7404 KB Ok
72 Correct 91 ms 8588 KB Ok
73 Correct 123 ms 8496 KB Ok
74 Correct 95 ms 7364 KB Ok
75 Correct 137 ms 8324 KB Ok
76 Correct 111 ms 8504 KB Ok
77 Correct 95 ms 7960 KB Ok
78 Correct 86 ms 8112 KB Ok
79 Correct 104 ms 8164 KB Ok
80 Correct 278 ms 14516 KB Ok
81 Correct 402 ms 15676 KB Ok
82 Correct 331 ms 12852 KB Ok
83 Correct 326 ms 15028 KB Ok
84 Correct 339 ms 13492 KB Ok
85 Correct 298 ms 12856 KB Ok
86 Correct 329 ms 13172 KB Ok
87 Correct 374 ms 15544 KB Ok
88 Correct 318 ms 12424 KB Ok
89 Correct 338 ms 15312 KB Ok
90 Correct 375 ms 14400 KB Ok
91 Correct 292 ms 13628 KB Ok
92 Correct 307 ms 14800 KB Ok
93 Correct 307 ms 14256 KB Ok
94 Correct 315 ms 13492 KB Ok
95 Correct 286 ms 20708 KB Ok
96 Correct 462 ms 30264 KB Ok
97 Correct 410 ms 24640 KB Ok
98 Correct 300 ms 25656 KB Ok
99 Correct 310 ms 24472 KB Ok
100 Correct 411 ms 23568 KB Ok
101 Correct 351 ms 28548 KB Ok
102 Correct 399 ms 26468 KB Ok
103 Correct 431 ms 30544 KB Ok
104 Correct 461 ms 34088 KB Ok
105 Correct 502 ms 35624 KB Ok
106 Correct 382 ms 30172 KB Ok
107 Correct 411 ms 29068 KB Ok
108 Correct 500 ms 35536 KB Ok
109 Correct 418 ms 31468 KB Ok
110 Execution timed out 2051 ms 50196 KB Time limit exceeded
111 Halted 0 ms 0 KB -