oj.uz

Submission #1114168

# Submission time Handle Problem Language Result Execution time Memory
1114168 2024-11-18T09:10:49 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 63916 KB 
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int INF = int(1E9) - 5;
constexpr int C = 1000;

void print(bool s, std::vector<int> x) {
    int n = int(x.size());
    std::cout << n << '\n';
    for (int i = 0; i < n; ++i) {
        std::cout << (s ? -1 : +1) * x[i] << " \n"[i == n - 1];
    }
}

void solve() {
    int N, M;
    std::cin >> N >> M;

    bool swapped = false;
    if (N < M) {
        swapped = true;
        std::swap(N, M);
    }

    if (N % M == 0) {
        std::vector<int> p(N - 1);
        for (int i = 0; i < N - 1; ++i) {
            p[i] = 1;
        }
        print(swapped, p);
    } else {
        std::vector<std::vector<int>> adj;
        auto check = [&](int n) -> std::pair<bool, std::vector<int>> {
            adj.assign(n + 1, {});
            std::vector<int> pre(n + 1), ans(n), ein(n + 1);
            for (int i = 0; i <= n; ++i) {
                if (i - N >= 0) {
                    adj[i].emplace_back(i - N);
                    ++ein[i - N];
                } 
                if (i + M <= n) {
                    adj[i].emplace_back(i + M);
                    ++ein[i + M];
                }
            }

            int cur = 0;
            std::queue<int> que;
            for (int i = 0; i <= n; ++i) {
                if (ein[i] == 0) {
                    pre[i] = (++cur) * C;
                    que.emplace(i);
                }
            }
            while (!que.empty()) {
                int v = que.front();
                que.pop();
                for (auto u : adj[v]) {
                    --ein[u];
                    pre[u] = std::max(pre[u], pre[v] + 1);
                    if (ein[u] == 0) {
                        que.emplace(u);
                    }
                }
            }
            for (int i = n; i >= 0; --i) {
                if (pre[i] == 0) {
                    return {false, {}};
                }
                pre[i] -= pre[0];
            }

            for (int i = 0; i < n; ++i) {
                ans[i] = pre[i + 1] - pre[i];
            }
            return {true, ans};
        };

        int lo = 0, hi = N + M;
        while (lo < hi) {
            int mid = (lo + hi + 1) >> 1;
            if (check(mid).first) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        print(swapped, check(lo).second);
    }
    
    return;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int TT = 1; std::cin >> TT;
    for (int i = 1; i <= TT; ++i) {
        solve();
    }

    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Ok
2 Correct 1 ms 336 KB Ok
3 Correct 1 ms 336 KB Ok
4 Correct 1 ms 336 KB Ok
5 Correct 1 ms 336 KB Ok
6 Correct 6 ms 592 KB Ok
7 Correct 55 ms 1620 KB Ok
8 Correct 24 ms 936 KB Ok
9 Correct 38 ms 1940 KB Ok
10 Correct 19 ms 1120 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Ok
2 Correct 1 ms 336 KB Ok
3 Correct 1 ms 336 KB Ok
4 Correct 1 ms 336 KB Ok
5 Correct 1 ms 336 KB Ok
6 Correct 685 ms 20164 KB Ok
7 Correct 603 ms 23076 KB Ok
8 Correct 1270 ms 26932 KB Ok
9 Correct 929 ms 29304 KB Ok
10 Correct 532 ms 17096 KB Ok
11 Correct 891 ms 25484 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Ok
2 Correct 1 ms 336 KB Ok
3 Correct 1 ms 336 KB Ok
4 Correct 1 ms 336 KB Ok
5 Correct 1 ms 420 KB Ok
6 Correct 1 ms 336 KB Ok
7 Correct 1 ms 336 KB Ok
8 Correct 1 ms 336 KB Ok
9 Correct 1 ms 336 KB Ok
10 Correct 1 ms 336 KB Ok
11 Correct 1 ms 336 KB Ok
12 Correct 1 ms 336 KB Ok
13 Correct 1 ms 336 KB Ok
14 Correct 1 ms 336 KB Ok
15 Correct 1 ms 336 KB Ok
16 Correct 1 ms 336 KB Ok
17 Correct 1 ms 336 KB Ok
18 Correct 1 ms 336 KB Ok
19 Correct 1 ms 336 KB Ok
20 Correct 1 ms 336 KB Ok
21 Correct 1 ms 336 KB Ok
22 Correct 1 ms 336 KB Ok
23 Correct 1 ms 336 KB Ok
24 Correct 4 ms 592 KB Ok
25 Correct 5 ms 788 KB Ok
26 Correct 5 ms 780 KB Ok
27 Correct 5 ms 704 KB Ok
28 Correct 4 ms 716 KB Ok
29 Correct 3 ms 592 KB Ok
30 Correct 3 ms 592 KB Ok
31 Correct 10 ms 752 KB Ok
32 Correct 6 ms 808 KB Ok
33 Correct 6 ms 760 KB Ok
34 Correct 21 ms 1048 KB Ok
35 Correct 35 ms 944 KB Ok
36 Correct 19 ms 1040 KB Ok
37 Correct 34 ms 956 KB Ok
38 Correct 19 ms 1080 KB Ok
39 Correct 18 ms 1068 KB Ok
40 Correct 20 ms 976 KB Ok
41 Correct 17 ms 848 KB Ok
42 Correct 19 ms 1156 KB Ok
43 Correct 19 ms 964 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Ok
2 Correct 1 ms 336 KB Ok
3 Correct 1 ms 336 KB Ok
4 Correct 1 ms 336 KB Ok
5 Correct 1 ms 420 KB Ok
6 Correct 1 ms 336 KB Ok
7 Correct 1 ms 336 KB Ok
8 Correct 1 ms 336 KB Ok
9 Correct 1 ms 336 KB Ok
10 Correct 1 ms 336 KB Ok
11 Correct 1 ms 336 KB Ok
12 Correct 1 ms 336 KB Ok
13 Correct 1 ms 336 KB Ok
14 Correct 1 ms 336 KB Ok
15 Correct 1 ms 336 KB Ok
16 Correct 1 ms 336 KB Ok
17 Correct 1 ms 336 KB Ok
18 Correct 6 ms 592 KB Ok
19 Correct 55 ms 1620 KB Ok
20 Correct 24 ms 936 KB Ok
21 Correct 38 ms 1940 KB Ok
22 Correct 19 ms 1120 KB Ok
23 Correct 1 ms 336 KB Ok
24 Correct 1 ms 336 KB Ok
25 Correct 1 ms 336 KB Ok
26 Correct 1 ms 336 KB Ok
27 Correct 1 ms 336 KB Ok
28 Correct 1 ms 336 KB Ok
29 Correct 1 ms 336 KB Ok
30 Correct 1 ms 336 KB Ok
31 Correct 1 ms 336 KB Ok
32 Correct 1 ms 336 KB Ok
33 Correct 1 ms 336 KB Ok
34 Correct 4 ms 592 KB Ok
35 Correct 5 ms 788 KB Ok
36 Correct 5 ms 780 KB Ok
37 Correct 5 ms 704 KB Ok
38 Correct 4 ms 716 KB Ok
39 Correct 3 ms 592 KB Ok
40 Correct 3 ms 592 KB Ok
41 Correct 10 ms 752 KB Ok
42 Correct 6 ms 808 KB Ok
43 Correct 6 ms 760 KB Ok
44 Correct 21 ms 1048 KB Ok
45 Correct 35 ms 944 KB Ok
46 Correct 19 ms 1040 KB Ok
47 Correct 34 ms 956 KB Ok
48 Correct 19 ms 1080 KB Ok
49 Correct 18 ms 1068 KB Ok
50 Correct 20 ms 976 KB Ok
51 Correct 17 ms 848 KB Ok
52 Correct 19 ms 1156 KB Ok
53 Correct 19 ms 964 KB Ok
54 Correct 249 ms 13216 KB Ok
55 Correct 358 ms 13484 KB Ok
56 Correct 308 ms 12996 KB Ok
57 Correct 193 ms 10740 KB Ok
58 Correct 274 ms 12884 KB Ok
59 Correct 247 ms 11736 KB Ok
60 Correct 200 ms 10628 KB Ok
61 Correct 217 ms 11012 KB Ok
62 Correct 360 ms 12896 KB Ok
63 Correct 231 ms 12160 KB Ok
64 Correct 342 ms 14576 KB Ok
65 Correct 306 ms 12000 KB Ok
66 Correct 239 ms 11288 KB Ok
67 Correct 193 ms 12340 KB Ok
68 Correct 271 ms 13584 KB Ok
69 Correct 950 ms 18900 KB Ok
70 Correct 974 ms 16416 KB Ok
71 Correct 911 ms 17684 KB Ok
72 Correct 942 ms 17732 KB Ok
73 Correct 914 ms 17856 KB Ok
74 Correct 827 ms 18832 KB Ok
75 Correct 832 ms 19232 KB Ok
76 Correct 927 ms 17340 KB Ok
77 Correct 854 ms 17584 KB Ok
78 Correct 1004 ms 18488 KB Ok
79 Correct 893 ms 18008 KB Ok
80 Correct 842 ms 17208 KB Ok
81 Correct 913 ms 18328 KB Ok
82 Correct 880 ms 18388 KB Ok
83 Correct 894 ms 17220 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Ok
2 Correct 1 ms 336 KB Ok
3 Correct 1 ms 336 KB Ok
4 Correct 1 ms 336 KB Ok
5 Correct 1 ms 420 KB Ok
6 Correct 1 ms 336 KB Ok
7 Correct 1 ms 336 KB Ok
8 Correct 1 ms 336 KB Ok
9 Correct 1 ms 336 KB Ok
10 Correct 1 ms 336 KB Ok
11 Correct 1 ms 336 KB Ok
12 Correct 1 ms 336 KB Ok
13 Correct 1 ms 336 KB Ok
14 Correct 1 ms 336 KB Ok
15 Correct 1 ms 336 KB Ok
16 Correct 1 ms 336 KB Ok
17 Correct 1 ms 336 KB Ok
18 Correct 6 ms 592 KB Ok
19 Correct 55 ms 1620 KB Ok
20 Correct 24 ms 936 KB Ok
21 Correct 38 ms 1940 KB Ok
22 Correct 19 ms 1120 KB Ok
23 Correct 1 ms 336 KB Ok
24 Correct 1 ms 336 KB Ok
25 Correct 1 ms 336 KB Ok
26 Correct 1 ms 336 KB Ok
27 Correct 1 ms 336 KB Ok
28 Correct 1 ms 336 KB Ok
29 Correct 1 ms 336 KB Ok
30 Correct 1 ms 336 KB Ok
31 Correct 1 ms 336 KB Ok
32 Correct 1 ms 336 KB Ok
33 Correct 1 ms 336 KB Ok
34 Correct 1 ms 336 KB Ok
35 Correct 1 ms 336 KB Ok
36 Correct 1 ms 336 KB Ok
37 Correct 1 ms 336 KB Ok
38 Correct 1 ms 336 KB Ok
39 Correct 685 ms 20164 KB Ok
40 Correct 603 ms 23076 KB Ok
41 Correct 1270 ms 26932 KB Ok
42 Correct 929 ms 29304 KB Ok
43 Correct 532 ms 17096 KB Ok
44 Correct 891 ms 25484 KB Ok
45 Correct 4 ms 592 KB Ok
46 Correct 5 ms 788 KB Ok
47 Correct 5 ms 780 KB Ok
48 Correct 5 ms 704 KB Ok
49 Correct 4 ms 716 KB Ok
50 Correct 3 ms 592 KB Ok
51 Correct 3 ms 592 KB Ok
52 Correct 10 ms 752 KB Ok
53 Correct 6 ms 808 KB Ok
54 Correct 6 ms 760 KB Ok
55 Correct 21 ms 1048 KB Ok
56 Correct 35 ms 944 KB Ok
57 Correct 19 ms 1040 KB Ok
58 Correct 34 ms 956 KB Ok
59 Correct 19 ms 1080 KB Ok
60 Correct 18 ms 1068 KB Ok
61 Correct 20 ms 976 KB Ok
62 Correct 17 ms 848 KB Ok
63 Correct 19 ms 1156 KB Ok
64 Correct 19 ms 964 KB Ok
65 Correct 249 ms 13216 KB Ok
66 Correct 358 ms 13484 KB Ok
67 Correct 308 ms 12996 KB Ok
68 Correct 193 ms 10740 KB Ok
69 Correct 274 ms 12884 KB Ok
70 Correct 247 ms 11736 KB Ok
71 Correct 200 ms 10628 KB Ok
72 Correct 217 ms 11012 KB Ok
73 Correct 360 ms 12896 KB Ok
74 Correct 231 ms 12160 KB Ok
75 Correct 342 ms 14576 KB Ok
76 Correct 306 ms 12000 KB Ok
77 Correct 239 ms 11288 KB Ok
78 Correct 193 ms 12340 KB Ok
79 Correct 271 ms 13584 KB Ok
80 Correct 950 ms 18900 KB Ok
81 Correct 974 ms 16416 KB Ok
82 Correct 911 ms 17684 KB Ok
83 Correct 942 ms 17732 KB Ok
84 Correct 914 ms 17856 KB Ok
85 Correct 827 ms 18832 KB Ok
86 Correct 832 ms 19232 KB Ok
87 Correct 927 ms 17340 KB Ok
88 Correct 854 ms 17584 KB Ok
89 Correct 1004 ms 18488 KB Ok
90 Correct 893 ms 18008 KB Ok
91 Correct 842 ms 17208 KB Ok
92 Correct 913 ms 18328 KB Ok
93 Correct 880 ms 18388 KB Ok
94 Correct 894 ms 17220 KB Ok
95 Correct 482 ms 31208 KB Ok
96 Correct 1052 ms 44020 KB Ok
97 Correct 1008 ms 37476 KB Ok
98 Correct 513 ms 30648 KB Ok
99 Correct 729 ms 38248 KB Ok
100 Correct 1186 ms 35360 KB Ok
101 Correct 913 ms 42356 KB Ok
102 Correct 842 ms 39756 KB Ok
103 Correct 951 ms 44528 KB Ok
104 Correct 1198 ms 43076 KB Ok
105 Correct 1125 ms 49684 KB Ok
106 Correct 740 ms 42740 KB Ok
107 Correct 977 ms 47428 KB Ok
108 Correct 1119 ms 56472 KB Ok
109 Correct 901 ms 42436 KB Ok
110 Execution timed out 2062 ms 63916 KB Time limit exceeded
111 Halted 0 ms 0 KB -