oj.uz

Submission #173799

# Submission time Handle Problem Language Result Execution time Memory
173799 2020-01-05T12:40:58 Z davitmarg Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 22996 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;
        }
        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++)
                         ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 256 KB Ok
3 Correct 2 ms 256 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 276 KB Ok
6 Correct 2 ms 256 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 256 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 2 ms 376 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 376 KB Ok
2 Correct 2 ms 256 KB Ok
3 Correct 2 ms 256 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 256 KB Ok
6 Correct 15 ms 632 KB Ok
7 Correct 60 ms 1836 KB Ok
8 Correct 25 ms 1144 KB Ok
9 Correct 67 ms 2056 KB Ok
10 Correct 36 ms 1364 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 252 KB Ok
3 Correct 2 ms 252 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 256 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 256 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 376 KB Ok
2 Correct 3 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 1008 ms 21160 KB Ok
7 Correct 835 ms 20392 KB Ok
8 Correct 1429 ms 22480 KB Ok
9 Correct 1147 ms 22996 KB Ok
10 Correct 794 ms 19836 KB Ok
11 Correct 1185 ms 21896 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 256 KB Ok
3 Correct 2 ms 256 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 276 KB Ok
6 Correct 2 ms 256 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 256 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 2 ms 376 KB Ok
12 Correct 2 ms 376 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 2 ms 252 KB Ok
15 Correct 2 ms 252 KB Ok
16 Correct 2 ms 256 KB Ok
17 Correct 2 ms 256 KB Ok
18 Correct 2 ms 376 KB Ok
19 Correct 2 ms 376 KB Ok
20 Correct 2 ms 256 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 10 ms 632 KB Ok
25 Correct 16 ms 2040 KB Ok
26 Correct 18 ms 1656 KB Ok
27 Correct 36 ms 6388 KB Ok
28 Correct 11 ms 1272 KB Ok
29 Correct 39 ms 8728 KB Ok
30 Correct 9 ms 632 KB Ok
31 Correct 12 ms 860 KB Ok
32 Correct 13 ms 988 KB Ok
33 Correct 19 ms 2936 KB Ok
34 Correct 613 ms 18512 KB Ok
35 Correct 586 ms 18592 KB Ok
36 Correct 609 ms 18552 KB Ok
37 Correct 586 ms 18544 KB Ok
38 Correct 585 ms 18512 KB Ok
39 Correct 613 ms 18456 KB Ok
40 Correct 656 ms 18668 KB Ok
41 Correct 584 ms 18544 KB Ok
42 Correct 611 ms 18556 KB Ok
43 Correct 576 ms 18544 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 256 KB Ok
3 Correct 2 ms 256 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 276 KB Ok
6 Correct 2 ms 256 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 256 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 2 ms 376 KB Ok
12 Correct 2 ms 376 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 2 ms 256 KB Ok
15 Correct 2 ms 256 KB Ok
16 Correct 2 ms 376 KB Ok
17 Correct 2 ms 256 KB Ok
18 Correct 15 ms 632 KB Ok
19 Correct 60 ms 1836 KB Ok
20 Correct 25 ms 1144 KB Ok
21 Correct 67 ms 2056 KB Ok
22 Correct 36 ms 1364 KB Ok
23 Correct 2 ms 376 KB Ok
24 Correct 2 ms 252 KB Ok
25 Correct 2 ms 252 KB Ok
26 Correct 2 ms 256 KB Ok
27 Correct 2 ms 256 KB Ok
28 Correct 2 ms 376 KB Ok
29 Correct 2 ms 376 KB Ok
30 Correct 2 ms 256 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 10 ms 632 KB Ok
35 Correct 16 ms 2040 KB Ok
36 Correct 18 ms 1656 KB Ok
37 Correct 36 ms 6388 KB Ok
38 Correct 11 ms 1272 KB Ok
39 Correct 39 ms 8728 KB Ok
40 Correct 9 ms 632 KB Ok
41 Correct 12 ms 860 KB Ok
42 Correct 13 ms 988 KB Ok
43 Correct 19 ms 2936 KB Ok
44 Correct 613 ms 18512 KB Ok
45 Correct 586 ms 18592 KB Ok
46 Correct 609 ms 18552 KB Ok
47 Correct 586 ms 18544 KB Ok
48 Correct 585 ms 18512 KB Ok
49 Correct 613 ms 18456 KB Ok
50 Correct 656 ms 18668 KB Ok
51 Correct 584 ms 18544 KB Ok
52 Correct 611 ms 18556 KB Ok
53 Correct 576 ms 18544 KB Ok
54 Correct 743 ms 16084 KB Ok
55 Correct 982 ms 16236 KB Ok
56 Correct 909 ms 18852 KB Ok
57 Correct 471 ms 15852 KB Ok
58 Correct 805 ms 16404 KB Ok
59 Correct 843 ms 16376 KB Ok
60 Correct 661 ms 15948 KB Ok
61 Correct 544 ms 16108 KB Ok
62 Correct 1081 ms 16068 KB Ok
63 Correct 800 ms 16548 KB Ok
64 Correct 1022 ms 16876 KB Ok
65 Correct 943 ms 16212 KB Ok
66 Correct 634 ms 16416 KB Ok
67 Correct 593 ms 16620 KB Ok
68 Correct 752 ms 15892 KB Ok
69 Execution timed out 2069 ms 20848 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 256 KB Ok
3 Correct 2 ms 256 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 276 KB Ok
6 Correct 2 ms 256 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 256 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 2 ms 376 KB Ok
12 Correct 2 ms 376 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 2 ms 256 KB Ok
15 Correct 2 ms 256 KB Ok
16 Correct 2 ms 376 KB Ok
17 Correct 2 ms 256 KB Ok
18 Correct 15 ms 632 KB Ok
19 Correct 60 ms 1836 KB Ok
20 Correct 25 ms 1144 KB Ok
21 Correct 67 ms 2056 KB Ok
22 Correct 36 ms 1364 KB Ok
23 Correct 2 ms 376 KB Ok
24 Correct 2 ms 252 KB Ok
25 Correct 2 ms 252 KB Ok
26 Correct 2 ms 256 KB Ok
27 Correct 2 ms 256 KB Ok
28 Correct 2 ms 376 KB Ok
29 Correct 2 ms 376 KB Ok
30 Correct 2 ms 256 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 376 KB Ok
35 Correct 3 ms 376 KB Ok
36 Correct 2 ms 376 KB Ok
37 Correct 2 ms 376 KB Ok
38 Correct 2 ms 376 KB Ok
39 Correct 1008 ms 21160 KB Ok
40 Correct 835 ms 20392 KB Ok
41 Correct 1429 ms 22480 KB Ok
42 Correct 1147 ms 22996 KB Ok
43 Correct 794 ms 19836 KB Ok
44 Correct 1185 ms 21896 KB Ok
45 Correct 10 ms 632 KB Ok
46 Correct 16 ms 2040 KB Ok
47 Correct 18 ms 1656 KB Ok
48 Correct 36 ms 6388 KB Ok
49 Correct 11 ms 1272 KB Ok
50 Correct 39 ms 8728 KB Ok
51 Correct 9 ms 632 KB Ok
52 Correct 12 ms 860 KB Ok
53 Correct 13 ms 988 KB Ok
54 Correct 19 ms 2936 KB Ok
55 Correct 613 ms 18512 KB Ok
56 Correct 586 ms 18592 KB Ok
57 Correct 609 ms 18552 KB Ok
58 Correct 586 ms 18544 KB Ok
59 Correct 585 ms 18512 KB Ok
60 Correct 613 ms 18456 KB Ok
61 Correct 656 ms 18668 KB Ok
62 Correct 584 ms 18544 KB Ok
63 Correct 611 ms 18556 KB Ok
64 Correct 576 ms 18544 KB Ok
65 Correct 743 ms 16084 KB Ok
66 Correct 982 ms 16236 KB Ok
67 Correct 909 ms 18852 KB Ok
68 Correct 471 ms 15852 KB Ok
69 Correct 805 ms 16404 KB Ok
70 Correct 843 ms 16376 KB Ok
71 Correct 661 ms 15948 KB Ok
72 Correct 544 ms 16108 KB Ok
73 Correct 1081 ms 16068 KB Ok
74 Correct 800 ms 16548 KB Ok
75 Correct 1022 ms 16876 KB Ok
76 Correct 943 ms 16212 KB Ok
77 Correct 634 ms 16416 KB Ok
78 Correct 593 ms 16620 KB Ok
79 Correct 752 ms 15892 KB Ok
80 Execution timed out 2069 ms 20848 KB Time limit exceeded
81 Halted 0 ms 0 KB -