oj.uz

Submission #173784

# Submission time Handle Problem Language Result Execution time Memory
173784 2020-01-05T12:10:01 Z davitmarg Nice sequence (IZhO18_sequence) C++17
29 / 100
 72 ms 13432 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);
}

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

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

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();
    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;
        int l, r, mid;
        l = 0;
        r = lca(n, m) - 1;
        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: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 'bool check(int)':
sequence.cpp:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < t.size(); i++)
                     ~~^~~~~~~~~~
sequence.cpp:82: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 6 ms 4984 KB Ok
2 Correct 6 ms 4984 KB Ok
3 Correct 6 ms 4984 KB Ok
4 Correct 6 ms 4984 KB Ok
5 Correct 6 ms 5112 KB Ok
6 Correct 6 ms 4984 KB Ok
7 Correct 6 ms 5028 KB Ok
8 Correct 7 ms 5112 KB Ok
9 Correct 7 ms 5112 KB Ok
10 Correct 8 ms 5112 KB Ok
11 Correct 6 ms 5112 KB Ok
12 Correct 7 ms 5100 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Ok
2 Correct 6 ms 5112 KB Ok
3 Correct 6 ms 5112 KB Ok
4 Correct 10 ms 5084 KB Ok
5 Correct 7 ms 4984 KB Ok
6 Correct 17 ms 5340 KB Ok
7 Correct 61 ms 6320 KB Ok
8 Correct 30 ms 5624 KB Ok
9 Correct 72 ms 6492 KB Ok
10 Correct 38 ms 5928 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4988 KB Ok
2 Correct 6 ms 4984 KB Ok
3 Correct 6 ms 4984 KB Ok
4 Correct 6 ms 4984 KB Ok
5 Correct 6 ms 4984 KB Ok
6 Correct 6 ms 4984 KB Ok
7 Correct 6 ms 4984 KB Ok
8 Correct 7 ms 5112 KB Ok
9 Correct 6 ms 4984 KB Ok
10 Correct 7 ms 5112 KB Ok
11 Correct 6 ms 4984 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Ok
2 Correct 6 ms 4984 KB Ok
3 Correct 7 ms 5096 KB Ok
4 Correct 7 ms 4988 KB Ok
5 Correct 7 ms 4984 KB Ok
6 Runtime error 17 ms 13432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Ok
2 Correct 6 ms 4984 KB Ok
3 Correct 6 ms 4984 KB Ok
4 Correct 6 ms 4984 KB Ok
5 Correct 6 ms 5112 KB Ok
6 Correct 6 ms 4984 KB Ok
7 Correct 6 ms 5028 KB Ok
8 Correct 7 ms 5112 KB Ok
9 Correct 7 ms 5112 KB Ok
10 Correct 8 ms 5112 KB Ok
11 Correct 6 ms 5112 KB Ok
12 Correct 7 ms 5100 KB Ok
13 Correct 6 ms 4988 KB Ok
14 Correct 6 ms 4984 KB Ok
15 Correct 6 ms 4984 KB Ok
16 Correct 6 ms 4984 KB Ok
17 Correct 6 ms 4984 KB Ok
18 Correct 6 ms 4984 KB Ok
19 Correct 6 ms 4984 KB Ok
20 Correct 7 ms 5112 KB Ok
21 Correct 6 ms 4984 KB Ok
22 Correct 7 ms 5112 KB Ok
23 Correct 6 ms 4984 KB Ok
24 Correct 14 ms 5260 KB Ok
25 Correct 20 ms 6264 KB Ok
26 Correct 19 ms 6008 KB Ok
27 Correct 45 ms 9352 KB Ok
28 Correct 18 ms 5624 KB Ok
29 Correct 40 ms 11380 KB Ok
30 Correct 12 ms 5368 KB Ok
31 Correct 15 ms 5240 KB Ok
32 Correct 16 ms 5496 KB Ok
33 Correct 21 ms 6904 KB Ok
34 Runtime error 17 ms 13304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Ok
2 Correct 6 ms 4984 KB Ok
3 Correct 6 ms 4984 KB Ok
4 Correct 6 ms 4984 KB Ok
5 Correct 6 ms 5112 KB Ok
6 Correct 6 ms 4984 KB Ok
7 Correct 6 ms 5028 KB Ok
8 Correct 7 ms 5112 KB Ok
9 Correct 7 ms 5112 KB Ok
10 Correct 8 ms 5112 KB Ok
11 Correct 6 ms 5112 KB Ok
12 Correct 7 ms 5100 KB Ok
13 Correct 6 ms 4984 KB Ok
14 Correct 6 ms 5112 KB Ok
15 Correct 6 ms 5112 KB Ok
16 Correct 10 ms 5084 KB Ok
17 Correct 7 ms 4984 KB Ok
18 Correct 17 ms 5340 KB Ok
19 Correct 61 ms 6320 KB Ok
20 Correct 30 ms 5624 KB Ok
21 Correct 72 ms 6492 KB Ok
22 Correct 38 ms 5928 KB Ok
23 Correct 6 ms 4988 KB Ok
24 Correct 6 ms 4984 KB Ok
25 Correct 6 ms 4984 KB Ok
26 Correct 6 ms 4984 KB Ok
27 Correct 6 ms 4984 KB Ok
28 Correct 6 ms 4984 KB Ok
29 Correct 6 ms 4984 KB Ok
30 Correct 7 ms 5112 KB Ok
31 Correct 6 ms 4984 KB Ok
32 Correct 7 ms 5112 KB Ok
33 Correct 6 ms 4984 KB Ok
34 Correct 14 ms 5260 KB Ok
35 Correct 20 ms 6264 KB Ok
36 Correct 19 ms 6008 KB Ok
37 Correct 45 ms 9352 KB Ok
38 Correct 18 ms 5624 KB Ok
39 Correct 40 ms 11380 KB Ok
40 Correct 12 ms 5368 KB Ok
41 Correct 15 ms 5240 KB Ok
42 Correct 16 ms 5496 KB Ok
43 Correct 21 ms 6904 KB Ok
44 Runtime error 17 ms 13304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Ok
2 Correct 6 ms 4984 KB Ok
3 Correct 6 ms 4984 KB Ok
4 Correct 6 ms 4984 KB Ok
5 Correct 6 ms 5112 KB Ok
6 Correct 6 ms 4984 KB Ok
7 Correct 6 ms 5028 KB Ok
8 Correct 7 ms 5112 KB Ok
9 Correct 7 ms 5112 KB Ok
10 Correct 8 ms 5112 KB Ok
11 Correct 6 ms 5112 KB Ok
12 Correct 7 ms 5100 KB Ok
13 Correct 6 ms 4984 KB Ok
14 Correct 6 ms 5112 KB Ok
15 Correct 6 ms 5112 KB Ok
16 Correct 10 ms 5084 KB Ok
17 Correct 7 ms 4984 KB Ok
18 Correct 17 ms 5340 KB Ok
19 Correct 61 ms 6320 KB Ok
20 Correct 30 ms 5624 KB Ok
21 Correct 72 ms 6492 KB Ok
22 Correct 38 ms 5928 KB Ok
23 Correct 6 ms 4988 KB Ok
24 Correct 6 ms 4984 KB Ok
25 Correct 6 ms 4984 KB Ok
26 Correct 6 ms 4984 KB Ok
27 Correct 6 ms 4984 KB Ok
28 Correct 6 ms 4984 KB Ok
29 Correct 6 ms 4984 KB Ok
30 Correct 7 ms 5112 KB Ok
31 Correct 6 ms 4984 KB Ok
32 Correct 7 ms 5112 KB Ok
33 Correct 6 ms 4984 KB Ok
34 Correct 6 ms 4984 KB Ok
35 Correct 6 ms 4984 KB Ok
36 Correct 7 ms 5096 KB Ok
37 Correct 7 ms 4988 KB Ok
38 Correct 7 ms 4984 KB Ok
39 Runtime error 17 ms 13432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -