oj.uz

Submission #172143

# Submission time Handle Problem Language Result Execution time Memory
172143 2019-12-31T11:20:49 Z emil_physmath Nice sequence (IZhO18_sequence) C++17
43 / 100
 2000 ms 30696 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef double ldouble;
typedef long long llong;
typedef unsigned int uint;
const int maxN = 100001;

vector<int> nei[400001];
int a[400001];
bool used[400001];

void DFS(int v, vector<int>& order)
{
    used[v] = true;
    for (int to: nei[v])
        if (!used[to])
            DFS(to, order);
    order.push_back(v);
}
bool Check(int n, int m, int len)
{
    if (len >= n)
    {
        llong sum = 0;
        for (int i = 1; i <= n; ++i)
            sum += a[i];
        if (sum >= 0) return false;
        for (int i = 2; i + n - 1 <= len; ++i)
        {
            sum -= a[i - 1];
            sum += a[i + n - 1];
            if (sum >= 0) return false;
        }
    }
    if (len >= m)
    {
        llong sum = 0;
        for (int i = 1; i <= m; ++i)
            sum += a[i];
        if (sum <= 0) return false;
        for (int i = 2; i + m - 1 <= len; ++i)
        {
            sum -= a[i - 1];
            sum += a[i + m - 1];
            if (sum <= 0) return false;
        }
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        int ans = 0;
        vector<int> ansArr;
        int l = max(n, m) - 1, r = max(n, m) + max(n, m)/* % min(n, m)*/;
        while (l <= r)
        {
            int len = (l + r) / 2;
            for (int i = 0; i <= len; ++i)
            {
                used[i] = false;
                vector<int>().swap(nei[i]);
            }
            for (int i = 1; i <= len; ++i)
            {
                if (i - n >= 0)
                    nei[i].push_back(i - n);
                if (i - m >= 0)
                    nei[i - m].push_back(i);
            }
            vector<int> order;
            for (int i = 0; i <= len; ++i)
                if (!used[i])
                    DFS(i, order);
            reverse(order.begin(), order.end());
            vector<int> pref(len + 1);
            for (int i = 0; i < order.size(); ++i)
                pref[order[i]] = i;
            for (int i = 1; i < pref.size(); ++i)
                pref[i] -= pref[0];
            pref[0] = 0;
            for (int i = 1; i <= len; ++i)
                a[i] = pref[i] - pref[i - 1];
            if (Check(n, m, len))
            {
                ans = len;
                ansArr.resize(len);
                for (int i = 0; i < len; ++i)
                    ansArr[i] = a[i + 1];
                l = len + 1;
            }
            else
                r = len - 1;
        }
        cout << ans << endl;
        for (int i = 0; i < ans; ++i)
            cout << ansArr[i] << ' ';
        cout << '\n';
    }
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:89:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < order.size(); ++i)
                             ~~^~~~~~~~~~~~~~
sequence.cpp:91:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 1; i < pref.size(); ++i)
                             ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 10 ms 9720 KB Ok
3 Correct 11 ms 9728 KB Ok
4 Correct 10 ms 9720 KB Ok
5 Correct 10 ms 9720 KB Ok
6 Correct 10 ms 9720 KB Ok
7 Correct 10 ms 9720 KB Ok
8 Correct 10 ms 9692 KB Ok
9 Correct 10 ms 9692 KB Ok
10 Correct 10 ms 9720 KB Ok
11 Correct 11 ms 9720 KB Ok
12 Correct 10 ms 9720 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 10 ms 9720 KB Ok
3 Correct 10 ms 9720 KB Ok
4 Correct 10 ms 9848 KB Ok
5 Correct 10 ms 9720 KB Ok
6 Correct 26 ms 10104 KB Ok
7 Correct 99 ms 11336 KB Ok
8 Correct 49 ms 10488 KB Ok
9 Correct 116 ms 11700 KB Ok
10 Correct 66 ms 10744 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 10 ms 9720 KB Ok
3 Correct 10 ms 9720 KB Ok
4 Correct 11 ms 9720 KB Ok
5 Correct 10 ms 9720 KB Ok
6 Correct 1696 ms 28176 KB Ok
7 Correct 1413 ms 30524 KB Ok
8 Execution timed out 2072 ms 30696 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 10 ms 9720 KB Ok
3 Correct 11 ms 9728 KB Ok
4 Correct 10 ms 9720 KB Ok
5 Correct 10 ms 9720 KB Ok
6 Correct 10 ms 9720 KB Ok
7 Correct 10 ms 9720 KB Ok
8 Correct 10 ms 9692 KB Ok
9 Correct 10 ms 9692 KB Ok
10 Correct 10 ms 9720 KB Ok
11 Correct 11 ms 9720 KB Ok
12 Correct 10 ms 9720 KB Ok
13 Correct 10 ms 9720 KB Ok
14 Correct 10 ms 9724 KB Ok
15 Correct 10 ms 9720 KB Ok
16 Correct 10 ms 9724 KB Ok
17 Correct 10 ms 9720 KB Ok
18 Correct 10 ms 9720 KB Ok
19 Correct 10 ms 9720 KB Ok
20 Correct 10 ms 9720 KB Ok
21 Correct 10 ms 9720 KB Ok
22 Correct 10 ms 9720 KB Ok
23 Correct 10 ms 9720 KB Ok
24 Correct 24 ms 10104 KB Ok
25 Correct 24 ms 9976 KB Ok
26 Correct 24 ms 9976 KB Ok
27 Correct 22 ms 9980 KB Ok
28 Correct 19 ms 9976 KB Ok
29 Correct 19 ms 10008 KB Ok
30 Correct 20 ms 9976 KB Ok
31 Correct 24 ms 9976 KB Ok
32 Correct 24 ms 9976 KB Ok
33 Correct 22 ms 9976 KB Ok
34 Correct 42 ms 10304 KB Ok
35 Correct 41 ms 10360 KB Ok
36 Correct 41 ms 10360 KB Ok
37 Correct 42 ms 10360 KB Ok
38 Correct 42 ms 10360 KB Ok
39 Correct 40 ms 10360 KB Ok
40 Correct 44 ms 10360 KB Ok
41 Correct 41 ms 10360 KB Ok
42 Correct 43 ms 10488 KB Ok
43 Correct 42 ms 10360 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 10 ms 9720 KB Ok
3 Correct 11 ms 9728 KB Ok
4 Correct 10 ms 9720 KB Ok
5 Correct 10 ms 9720 KB Ok
6 Correct 10 ms 9720 KB Ok
7 Correct 10 ms 9720 KB Ok
8 Correct 10 ms 9692 KB Ok
9 Correct 10 ms 9692 KB Ok
10 Correct 10 ms 9720 KB Ok
11 Correct 11 ms 9720 KB Ok
12 Correct 10 ms 9720 KB Ok
13 Correct 10 ms 9720 KB Ok
14 Correct 10 ms 9720 KB Ok
15 Correct 10 ms 9720 KB Ok
16 Correct 10 ms 9848 KB Ok
17 Correct 10 ms 9720 KB Ok
18 Correct 26 ms 10104 KB Ok
19 Correct 99 ms 11336 KB Ok
20 Correct 49 ms 10488 KB Ok
21 Correct 116 ms 11700 KB Ok
22 Correct 66 ms 10744 KB Ok
23 Correct 10 ms 9720 KB Ok
24 Correct 10 ms 9724 KB Ok
25 Correct 10 ms 9720 KB Ok
26 Correct 10 ms 9724 KB Ok
27 Correct 10 ms 9720 KB Ok
28 Correct 10 ms 9720 KB Ok
29 Correct 10 ms 9720 KB Ok
30 Correct 10 ms 9720 KB Ok
31 Correct 10 ms 9720 KB Ok
32 Correct 10 ms 9720 KB Ok
33 Correct 10 ms 9720 KB Ok
34 Correct 24 ms 10104 KB Ok
35 Correct 24 ms 9976 KB Ok
36 Correct 24 ms 9976 KB Ok
37 Correct 22 ms 9980 KB Ok
38 Correct 19 ms 9976 KB Ok
39 Correct 19 ms 10008 KB Ok
40 Correct 20 ms 9976 KB Ok
41 Correct 24 ms 9976 KB Ok
42 Correct 24 ms 9976 KB Ok
43 Correct 22 ms 9976 KB Ok
44 Correct 42 ms 10304 KB Ok
45 Correct 41 ms 10360 KB Ok
46 Correct 41 ms 10360 KB Ok
47 Correct 42 ms 10360 KB Ok
48 Correct 42 ms 10360 KB Ok
49 Correct 40 ms 10360 KB Ok
50 Correct 44 ms 10360 KB Ok
51 Correct 41 ms 10360 KB Ok
52 Correct 43 ms 10488 KB Ok
53 Correct 42 ms 10360 KB Ok
54 Correct 1018 ms 16892 KB Ok
55 Correct 1239 ms 17300 KB Ok
56 Correct 1133 ms 17168 KB Ok
57 Correct 808 ms 16492 KB Ok
58 Correct 1126 ms 16840 KB Ok
59 Correct 1024 ms 16884 KB Ok
60 Correct 830 ms 16548 KB Ok
61 Correct 841 ms 16464 KB Ok
62 Correct 1349 ms 17424 KB Ok
63 Correct 898 ms 16260 KB Ok
64 Correct 1272 ms 17228 KB Ok
65 Correct 1101 ms 17144 KB Ok
66 Correct 975 ms 16748 KB Ok
67 Correct 777 ms 16476 KB Ok
68 Correct 1042 ms 16752 KB Ok
69 Execution timed out 2051 ms 25572 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 10 ms 9720 KB Ok
3 Correct 11 ms 9728 KB Ok
4 Correct 10 ms 9720 KB Ok
5 Correct 10 ms 9720 KB Ok
6 Correct 10 ms 9720 KB Ok
7 Correct 10 ms 9720 KB Ok
8 Correct 10 ms 9692 KB Ok
9 Correct 10 ms 9692 KB Ok
10 Correct 10 ms 9720 KB Ok
11 Correct 11 ms 9720 KB Ok
12 Correct 10 ms 9720 KB Ok
13 Correct 10 ms 9720 KB Ok
14 Correct 10 ms 9720 KB Ok
15 Correct 10 ms 9720 KB Ok
16 Correct 10 ms 9848 KB Ok
17 Correct 10 ms 9720 KB Ok
18 Correct 26 ms 10104 KB Ok
19 Correct 99 ms 11336 KB Ok
20 Correct 49 ms 10488 KB Ok
21 Correct 116 ms 11700 KB Ok
22 Correct 66 ms 10744 KB Ok
23 Correct 10 ms 9720 KB Ok
24 Correct 10 ms 9724 KB Ok
25 Correct 10 ms 9720 KB Ok
26 Correct 10 ms 9724 KB Ok
27 Correct 10 ms 9720 KB Ok
28 Correct 10 ms 9720 KB Ok
29 Correct 10 ms 9720 KB Ok
30 Correct 10 ms 9720 KB Ok
31 Correct 10 ms 9720 KB Ok
32 Correct 10 ms 9720 KB Ok
33 Correct 10 ms 9720 KB Ok
34 Correct 10 ms 9720 KB Ok
35 Correct 10 ms 9720 KB Ok
36 Correct 10 ms 9720 KB Ok
37 Correct 11 ms 9720 KB Ok
38 Correct 10 ms 9720 KB Ok
39 Correct 1696 ms 28176 KB Ok
40 Correct 1413 ms 30524 KB Ok
41 Execution timed out 2072 ms 30696 KB Time limit exceeded
42 Halted 0 ms 0 KB -