oj.uz

Submission #172172

# Submission time Handle Problem Language Result Execution time Memory
172172 2019-12-31T12:11:09 Z emil_physmath Nice sequence (IZhO18_sequence) C++17
43 / 100
 2000 ms 27592 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);
        bool up = false;
        int prevLen = 0;
        while (l <= r)
        {
            int len = (l + r) / 2;
            for (int i = 0; i <= len; ++i)
            {
                used[i] = false;
                if (!up) vector<int>().swap(nei[i]);
            }
            for (int i = (up ? prevLen + 1 : 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;
                // up = true;
                prevLen = len;
            }
            else
            {
                r = len - 1;
                up = false;
            }
        }
        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:92:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < order.size(); ++i)
                             ~~^~~~~~~~~~~~~~
sequence.cpp:94: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 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 13 ms 9720 KB Ok
10 Correct 11 ms 9720 KB Ok
11 Correct 10 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 9720 KB Ok
5 Correct 10 ms 9720 KB Ok
6 Correct 13 ms 9976 KB Ok
7 Correct 27 ms 11024 KB Ok
8 Correct 18 ms 10360 KB Ok
9 Correct 29 ms 11232 KB Ok
10 Correct 21 ms 10600 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 10 ms 9720 KB Ok
4 Correct 10 ms 9592 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 12 ms 9720 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 12 ms 9724 KB Ok
3 Correct 10 ms 9720 KB Ok
4 Correct 10 ms 9720 KB Ok
5 Correct 10 ms 9720 KB Ok
6 Execution timed out 2045 ms 27592 KB Time limit exceeded
7 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 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 13 ms 9720 KB Ok
10 Correct 11 ms 9720 KB Ok
11 Correct 10 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 9592 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 12 ms 9720 KB Ok
24 Correct 21 ms 9976 KB Ok
25 Correct 22 ms 9976 KB Ok
26 Correct 22 ms 9976 KB Ok
27 Correct 21 ms 9976 KB Ok
28 Correct 19 ms 9976 KB Ok
29 Correct 18 ms 9976 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 39 ms 10232 KB Ok
35 Correct 40 ms 10232 KB Ok
36 Correct 39 ms 10232 KB Ok
37 Correct 39 ms 10232 KB Ok
38 Correct 38 ms 10360 KB Ok
39 Correct 39 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 40 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 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 13 ms 9720 KB Ok
10 Correct 11 ms 9720 KB Ok
11 Correct 10 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 9720 KB Ok
17 Correct 10 ms 9720 KB Ok
18 Correct 13 ms 9976 KB Ok
19 Correct 27 ms 11024 KB Ok
20 Correct 18 ms 10360 KB Ok
21 Correct 29 ms 11232 KB Ok
22 Correct 21 ms 10600 KB Ok
23 Correct 10 ms 9720 KB Ok
24 Correct 10 ms 9720 KB Ok
25 Correct 10 ms 9720 KB Ok
26 Correct 10 ms 9592 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 12 ms 9720 KB Ok
34 Correct 21 ms 9976 KB Ok
35 Correct 22 ms 9976 KB Ok
36 Correct 22 ms 9976 KB Ok
37 Correct 21 ms 9976 KB Ok
38 Correct 19 ms 9976 KB Ok
39 Correct 18 ms 9976 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 39 ms 10232 KB Ok
45 Correct 40 ms 10232 KB Ok
46 Correct 39 ms 10232 KB Ok
47 Correct 39 ms 10232 KB Ok
48 Correct 38 ms 10360 KB Ok
49 Correct 39 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 40 ms 10360 KB Ok
54 Correct 1000 ms 16584 KB Ok
55 Correct 1326 ms 17080 KB Ok
56 Correct 1122 ms 16916 KB Ok
57 Correct 853 ms 15800 KB Ok
58 Correct 1069 ms 16868 KB Ok
59 Correct 1037 ms 16372 KB Ok
60 Correct 838 ms 15968 KB Ok
61 Correct 814 ms 16164 KB Ok
62 Correct 1299 ms 17368 KB Ok
63 Correct 919 ms 16412 KB Ok
64 Correct 1267 ms 16988 KB Ok
65 Correct 1207 ms 16856 KB Ok
66 Correct 959 ms 16388 KB Ok
67 Correct 734 ms 16028 KB Ok
68 Correct 1047 ms 16652 KB Ok
69 Execution timed out 2058 ms 24160 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 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 13 ms 9720 KB Ok
10 Correct 11 ms 9720 KB Ok
11 Correct 10 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 9720 KB Ok
17 Correct 10 ms 9720 KB Ok
18 Correct 13 ms 9976 KB Ok
19 Correct 27 ms 11024 KB Ok
20 Correct 18 ms 10360 KB Ok
21 Correct 29 ms 11232 KB Ok
22 Correct 21 ms 10600 KB Ok
23 Correct 10 ms 9720 KB Ok
24 Correct 10 ms 9720 KB Ok
25 Correct 10 ms 9720 KB Ok
26 Correct 10 ms 9592 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 12 ms 9720 KB Ok
34 Correct 10 ms 9720 KB Ok
35 Correct 12 ms 9724 KB Ok
36 Correct 10 ms 9720 KB Ok
37 Correct 10 ms 9720 KB Ok
38 Correct 10 ms 9720 KB Ok
39 Execution timed out 2045 ms 27592 KB Time limit exceeded
40 Halted 0 ms 0 KB -