oj.uz

Submission #172163

# Submission time Handle Problem Language Result Execution time Memory
172163 2019-12-31T11:58:22 Z emil_physmath Nice sequence (IZhO18_sequence) C++17
43 / 100
 2000 ms 29148 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 = max(n, m) - 1;
        vector<int> ansArr(max(n, m) - 1, n < m ? -1 : 1);
        int l = max(n, m) + 0.5 * min(n, m) - 1, r = 2 * max(n, m) - max(n, m) % min(n, m) - 1 - 1;
        r = min(r, n + m + max(n, m) % min(n, m) - 2);
        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 12 ms 9692 KB Ok
2 Correct 12 ms 9720 KB Ok
3 Correct 10 ms 9720 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 9720 KB Ok
9 Correct 10 ms 9720 KB Ok
10 Correct 10 ms 9720 KB Ok
11 Correct 11 ms 9744 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 9720 KB Ok
5 Correct 10 ms 9720 KB Ok
6 Correct 13 ms 9976 KB Ok
7 Correct 27 ms 11028 KB Ok
8 Correct 17 ms 10360 KB Ok
9 Correct 29 ms 11260 KB Ok
10 Correct 21 ms 10728 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 9720 KB Ok
3 Correct 12 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 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 9724 KB Ok
2 Correct 10 ms 9720 KB Ok
3 Correct 10 ms 9708 KB Ok
4 Correct 10 ms 9720 KB Ok
5 Correct 12 ms 9720 KB Ok
6 Correct 1812 ms 28344 KB Ok
7 Correct 1399 ms 27704 KB Ok
8 Execution timed out 2060 ms 29148 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9692 KB Ok
2 Correct 12 ms 9720 KB Ok
3 Correct 10 ms 9720 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 9720 KB Ok
9 Correct 10 ms 9720 KB Ok
10 Correct 10 ms 9720 KB Ok
11 Correct 11 ms 9744 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 12 ms 9728 KB Ok
16 Correct 10 ms 9720 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 21 ms 9980 KB Ok
25 Correct 21 ms 9976 KB Ok
26 Correct 23 ms 10060 KB Ok
27 Correct 21 ms 9976 KB Ok
28 Correct 20 ms 9976 KB Ok
29 Correct 20 ms 9996 KB Ok
30 Correct 18 ms 9848 KB Ok
31 Correct 22 ms 9976 KB Ok
32 Correct 22 ms 9976 KB Ok
33 Correct 21 ms 9976 KB Ok
34 Correct 38 ms 10184 KB Ok
35 Correct 37 ms 10232 KB Ok
36 Correct 37 ms 10284 KB Ok
37 Correct 37 ms 10232 KB Ok
38 Correct 38 ms 10232 KB Ok
39 Correct 36 ms 10232 KB Ok
40 Correct 39 ms 10232 KB Ok
41 Correct 37 ms 10232 KB Ok
42 Correct 38 ms 10232 KB Ok
43 Correct 38 ms 10232 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9692 KB Ok
2 Correct 12 ms 9720 KB Ok
3 Correct 10 ms 9720 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 9720 KB Ok
9 Correct 10 ms 9720 KB Ok
10 Correct 10 ms 9720 KB Ok
11 Correct 11 ms 9744 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 9720 KB Ok
17 Correct 10 ms 9720 KB Ok
18 Correct 13 ms 9976 KB Ok
19 Correct 27 ms 11028 KB Ok
20 Correct 17 ms 10360 KB Ok
21 Correct 29 ms 11260 KB Ok
22 Correct 21 ms 10728 KB Ok
23 Correct 10 ms 9720 KB Ok
24 Correct 10 ms 9720 KB Ok
25 Correct 12 ms 9728 KB Ok
26 Correct 10 ms 9720 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 21 ms 9980 KB Ok
35 Correct 21 ms 9976 KB Ok
36 Correct 23 ms 10060 KB Ok
37 Correct 21 ms 9976 KB Ok
38 Correct 20 ms 9976 KB Ok
39 Correct 20 ms 9996 KB Ok
40 Correct 18 ms 9848 KB Ok
41 Correct 22 ms 9976 KB Ok
42 Correct 22 ms 9976 KB Ok
43 Correct 21 ms 9976 KB Ok
44 Correct 38 ms 10184 KB Ok
45 Correct 37 ms 10232 KB Ok
46 Correct 37 ms 10284 KB Ok
47 Correct 37 ms 10232 KB Ok
48 Correct 38 ms 10232 KB Ok
49 Correct 36 ms 10232 KB Ok
50 Correct 39 ms 10232 KB Ok
51 Correct 37 ms 10232 KB Ok
52 Correct 38 ms 10232 KB Ok
53 Correct 38 ms 10232 KB Ok
54 Correct 1042 ms 16564 KB Ok
55 Correct 1234 ms 17084 KB Ok
56 Correct 1172 ms 16964 KB Ok
57 Correct 900 ms 15592 KB Ok
58 Correct 1109 ms 16860 KB Ok
59 Correct 1132 ms 16496 KB Ok
60 Correct 980 ms 15968 KB Ok
61 Correct 896 ms 16200 KB Ok
62 Correct 1232 ms 17408 KB Ok
63 Correct 1160 ms 16028 KB Ok
64 Correct 1230 ms 17192 KB Ok
65 Correct 1131 ms 16952 KB Ok
66 Correct 1070 ms 16316 KB Ok
67 Correct 899 ms 16040 KB Ok
68 Correct 1083 ms 16452 KB Ok
69 Correct 1898 ms 25400 KB Ok
70 Correct 1973 ms 25488 KB Ok
71 Execution timed out 2073 ms 23056 KB Time limit exceeded
72 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9692 KB Ok
2 Correct 12 ms 9720 KB Ok
3 Correct 10 ms 9720 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 9720 KB Ok
9 Correct 10 ms 9720 KB Ok
10 Correct 10 ms 9720 KB Ok
11 Correct 11 ms 9744 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 9720 KB Ok
17 Correct 10 ms 9720 KB Ok
18 Correct 13 ms 9976 KB Ok
19 Correct 27 ms 11028 KB Ok
20 Correct 17 ms 10360 KB Ok
21 Correct 29 ms 11260 KB Ok
22 Correct 21 ms 10728 KB Ok
23 Correct 10 ms 9720 KB Ok
24 Correct 10 ms 9720 KB Ok
25 Correct 12 ms 9728 KB Ok
26 Correct 10 ms 9720 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 9724 KB Ok
35 Correct 10 ms 9720 KB Ok
36 Correct 10 ms 9708 KB Ok
37 Correct 10 ms 9720 KB Ok
38 Correct 12 ms 9720 KB Ok
39 Correct 1812 ms 28344 KB Ok
40 Correct 1399 ms 27704 KB Ok
41 Execution timed out 2060 ms 29148 KB Time limit exceeded
42 Halted 0 ms 0 KB -