oj.uz

Submission #172153

# Submission time Handle Problem Language Result Execution time Memory
172153 2019-12-31T11:47:28 Z emil_physmath Nice sequence (IZhO18_sequence) C++17
43 / 100
 2000 ms 29648 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 = 2 * max(n, m) - max(n, m) % min(n, m) - 1;
        --r;
        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:90:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < order.size(); ++i)
                             ~~^~~~~~~~~~~~~~
sequence.cpp:92: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 11 ms 9720 KB Ok
3 Correct 12 ms 9720 KB Ok
4 Correct 13 ms 9720 KB Ok
5 Correct 11 ms 9720 KB Ok
6 Correct 10 ms 9720 KB Ok
7 Correct 11 ms 9720 KB Ok
8 Correct 10 ms 9720 KB Ok
9 Correct 11 ms 9720 KB Ok
10 Correct 10 ms 9720 KB Ok
11 Correct 10 ms 9724 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 11 ms 9720 KB Ok
4 Correct 11 ms 9720 KB Ok
5 Correct 11 ms 9720 KB Ok
6 Correct 27 ms 9904 KB Ok
7 Correct 101 ms 11300 KB Ok
8 Correct 53 ms 10488 KB Ok
9 Correct 126 ms 11572 KB Ok
10 Correct 66 ms 10872 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9720 KB Ok
2 Correct 10 ms 9720 KB Ok
3 Correct 11 ms 9720 KB Ok
4 Correct 10 ms 9720 KB Ok
5 Correct 11 ms 9720 KB Ok
6 Correct 1814 ms 28164 KB Ok
7 Correct 1581 ms 27808 KB Ok
8 Execution timed out 2076 ms 29648 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 11 ms 9720 KB Ok
3 Correct 12 ms 9720 KB Ok
4 Correct 13 ms 9720 KB Ok
5 Correct 11 ms 9720 KB Ok
6 Correct 10 ms 9720 KB Ok
7 Correct 11 ms 9720 KB Ok
8 Correct 10 ms 9720 KB Ok
9 Correct 11 ms 9720 KB Ok
10 Correct 10 ms 9720 KB Ok
11 Correct 10 ms 9724 KB Ok
12 Correct 10 ms 9720 KB Ok
13 Correct 10 ms 9720 KB Ok
14 Correct 11 ms 9720 KB Ok
15 Correct 10 ms 9720 KB Ok
16 Correct 10 ms 9720 KB Ok
17 Correct 12 ms 9720 KB Ok
18 Correct 10 ms 9720 KB Ok
19 Correct 10 ms 9724 KB Ok
20 Correct 10 ms 9720 KB Ok
21 Correct 11 ms 9720 KB Ok
22 Correct 10 ms 9720 KB Ok
23 Correct 11 ms 9720 KB Ok
24 Correct 23 ms 9976 KB Ok
25 Correct 23 ms 9980 KB Ok
26 Correct 23 ms 9976 KB Ok
27 Correct 22 ms 9976 KB Ok
28 Correct 19 ms 9976 KB Ok
29 Correct 19 ms 9976 KB Ok
30 Correct 20 ms 9976 KB Ok
31 Correct 23 ms 9976 KB Ok
32 Correct 23 ms 9976 KB Ok
33 Correct 22 ms 9916 KB Ok
34 Correct 40 ms 10296 KB Ok
35 Correct 39 ms 10232 KB Ok
36 Correct 40 ms 10232 KB Ok
37 Correct 39 ms 10280 KB Ok
38 Correct 39 ms 10232 KB Ok
39 Correct 38 ms 10232 KB Ok
40 Correct 42 ms 10232 KB Ok
41 Correct 40 ms 10232 KB Ok
42 Correct 41 ms 10232 KB Ok
43 Correct 41 ms 10252 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 11 ms 9720 KB Ok
3 Correct 12 ms 9720 KB Ok
4 Correct 13 ms 9720 KB Ok
5 Correct 11 ms 9720 KB Ok
6 Correct 10 ms 9720 KB Ok
7 Correct 11 ms 9720 KB Ok
8 Correct 10 ms 9720 KB Ok
9 Correct 11 ms 9720 KB Ok
10 Correct 10 ms 9720 KB Ok
11 Correct 10 ms 9724 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 11 ms 9720 KB Ok
16 Correct 11 ms 9720 KB Ok
17 Correct 11 ms 9720 KB Ok
18 Correct 27 ms 9904 KB Ok
19 Correct 101 ms 11300 KB Ok
20 Correct 53 ms 10488 KB Ok
21 Correct 126 ms 11572 KB Ok
22 Correct 66 ms 10872 KB Ok
23 Correct 10 ms 9720 KB Ok
24 Correct 11 ms 9720 KB Ok
25 Correct 10 ms 9720 KB Ok
26 Correct 10 ms 9720 KB Ok
27 Correct 12 ms 9720 KB Ok
28 Correct 10 ms 9720 KB Ok
29 Correct 10 ms 9724 KB Ok
30 Correct 10 ms 9720 KB Ok
31 Correct 11 ms 9720 KB Ok
32 Correct 10 ms 9720 KB Ok
33 Correct 11 ms 9720 KB Ok
34 Correct 23 ms 9976 KB Ok
35 Correct 23 ms 9980 KB Ok
36 Correct 23 ms 9976 KB Ok
37 Correct 22 ms 9976 KB Ok
38 Correct 19 ms 9976 KB Ok
39 Correct 19 ms 9976 KB Ok
40 Correct 20 ms 9976 KB Ok
41 Correct 23 ms 9976 KB Ok
42 Correct 23 ms 9976 KB Ok
43 Correct 22 ms 9916 KB Ok
44 Correct 40 ms 10296 KB Ok
45 Correct 39 ms 10232 KB Ok
46 Correct 40 ms 10232 KB Ok
47 Correct 39 ms 10280 KB Ok
48 Correct 39 ms 10232 KB Ok
49 Correct 38 ms 10232 KB Ok
50 Correct 42 ms 10232 KB Ok
51 Correct 40 ms 10232 KB Ok
52 Correct 41 ms 10232 KB Ok
53 Correct 41 ms 10252 KB Ok
54 Correct 988 ms 16876 KB Ok
55 Correct 1211 ms 17232 KB Ok
56 Correct 1114 ms 17180 KB Ok
57 Correct 773 ms 15840 KB Ok
58 Correct 1118 ms 16828 KB Ok
59 Correct 1032 ms 16492 KB Ok
60 Correct 786 ms 16084 KB Ok
61 Correct 819 ms 16452 KB Ok
62 Correct 1309 ms 17480 KB Ok
63 Correct 862 ms 16268 KB Ok
64 Correct 1203 ms 17012 KB Ok
65 Correct 1117 ms 17076 KB Ok
66 Correct 1039 ms 16920 KB Ok
67 Correct 735 ms 16172 KB Ok
68 Correct 1012 ms 16588 KB Ok
69 Execution timed out 2033 ms 24232 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 11 ms 9720 KB Ok
3 Correct 12 ms 9720 KB Ok
4 Correct 13 ms 9720 KB Ok
5 Correct 11 ms 9720 KB Ok
6 Correct 10 ms 9720 KB Ok
7 Correct 11 ms 9720 KB Ok
8 Correct 10 ms 9720 KB Ok
9 Correct 11 ms 9720 KB Ok
10 Correct 10 ms 9720 KB Ok
11 Correct 10 ms 9724 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 11 ms 9720 KB Ok
16 Correct 11 ms 9720 KB Ok
17 Correct 11 ms 9720 KB Ok
18 Correct 27 ms 9904 KB Ok
19 Correct 101 ms 11300 KB Ok
20 Correct 53 ms 10488 KB Ok
21 Correct 126 ms 11572 KB Ok
22 Correct 66 ms 10872 KB Ok
23 Correct 10 ms 9720 KB Ok
24 Correct 11 ms 9720 KB Ok
25 Correct 10 ms 9720 KB Ok
26 Correct 10 ms 9720 KB Ok
27 Correct 12 ms 9720 KB Ok
28 Correct 10 ms 9720 KB Ok
29 Correct 10 ms 9724 KB Ok
30 Correct 10 ms 9720 KB Ok
31 Correct 11 ms 9720 KB Ok
32 Correct 10 ms 9720 KB Ok
33 Correct 11 ms 9720 KB Ok
34 Correct 13 ms 9720 KB Ok
35 Correct 10 ms 9720 KB Ok
36 Correct 11 ms 9720 KB Ok
37 Correct 10 ms 9720 KB Ok
38 Correct 11 ms 9720 KB Ok
39 Correct 1814 ms 28164 KB Ok
40 Correct 1581 ms 27808 KB Ok
41 Execution timed out 2076 ms 29648 KB Time limit exceeded
42 Halted 0 ms 0 KB -