oj.uz

Submission #1114173

# Submission time Handle Problem Language Result Execution time Memory
1114173 2024-11-18T09:14:03 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 63104 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;
        std::vector<int> pre, ans, ein;
        auto check = [&](int n, bool save) -> std::pair<bool, std::vector<int>> {
            adj.assign(n + 1, {});
            pre.assign(n + 1, 0);
            ans.assign(n, 0);
            ein.assign(n + 1, 0);
            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];
            }
            if (!save) {
                return {true, {}};
            }

            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, false).first) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        print(swapped, check(lo, true).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 336 KB Ok
6 Correct 1 ms 508 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 504 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 684 KB Ok
7 Correct 37 ms 1768 KB Ok
8 Correct 14 ms 932 KB Ok
9 Correct 41 ms 1932 KB Ok
10 Correct 20 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 508 KB Ok
10 Correct 1 ms 336 KB Ok
11 Correct 1 ms 532 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 657 ms 20404 KB Ok
7 Correct 596 ms 22924 KB Ok
8 Correct 1201 ms 27252 KB Ok
9 Correct 839 ms 31356 KB Ok
10 Correct 499 ms 17124 KB Ok
11 Correct 827 ms 25600 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 336 KB Ok
6 Correct 1 ms 508 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 504 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 508 KB Ok
22 Correct 1 ms 336 KB Ok
23 Correct 1 ms 532 KB Ok
24 Correct 4 ms 592 KB Ok
25 Correct 5 ms 972 KB Ok
26 Correct 5 ms 592 KB Ok
27 Correct 5 ms 716 KB Ok
28 Correct 5 ms 592 KB Ok
29 Correct 3 ms 592 KB Ok
30 Correct 4 ms 592 KB Ok
31 Correct 6 ms 808 KB Ok
32 Correct 6 ms 592 KB Ok
33 Correct 5 ms 948 KB Ok
34 Correct 28 ms 1064 KB Ok
35 Correct 21 ms 952 KB Ok
36 Correct 20 ms 1020 KB Ok
37 Correct 19 ms 1036 KB Ok
38 Correct 18 ms 1088 KB Ok
39 Correct 17 ms 988 KB Ok
40 Correct 24 ms 1148 KB Ok
41 Correct 19 ms 944 KB Ok
42 Correct 20 ms 976 KB Ok
43 Correct 20 ms 948 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 336 KB Ok
6 Correct 1 ms 508 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 504 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 684 KB Ok
19 Correct 37 ms 1768 KB Ok
20 Correct 14 ms 932 KB Ok
21 Correct 41 ms 1932 KB Ok
22 Correct 20 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 508 KB Ok
32 Correct 1 ms 336 KB Ok
33 Correct 1 ms 532 KB Ok
34 Correct 4 ms 592 KB Ok
35 Correct 5 ms 972 KB Ok
36 Correct 5 ms 592 KB Ok
37 Correct 5 ms 716 KB Ok
38 Correct 5 ms 592 KB Ok
39 Correct 3 ms 592 KB Ok
40 Correct 4 ms 592 KB Ok
41 Correct 6 ms 808 KB Ok
42 Correct 6 ms 592 KB Ok
43 Correct 5 ms 948 KB Ok
44 Correct 28 ms 1064 KB Ok
45 Correct 21 ms 952 KB Ok
46 Correct 20 ms 1020 KB Ok
47 Correct 19 ms 1036 KB Ok
48 Correct 18 ms 1088 KB Ok
49 Correct 17 ms 988 KB Ok
50 Correct 24 ms 1148 KB Ok
51 Correct 19 ms 944 KB Ok
52 Correct 20 ms 976 KB Ok
53 Correct 20 ms 948 KB Ok
54 Correct 284 ms 12788 KB Ok
55 Correct 388 ms 13504 KB Ok
56 Correct 363 ms 13620 KB Ok
57 Correct 229 ms 11640 KB Ok
58 Correct 311 ms 13176 KB Ok
59 Correct 280 ms 11328 KB Ok
60 Correct 213 ms 11500 KB Ok
61 Correct 235 ms 11876 KB Ok
62 Correct 378 ms 13168 KB Ok
63 Correct 264 ms 13748 KB Ok
64 Correct 371 ms 14296 KB Ok
65 Correct 312 ms 12384 KB Ok
66 Correct 263 ms 12200 KB Ok
67 Correct 218 ms 13132 KB Ok
68 Correct 304 ms 12960 KB Ok
69 Correct 913 ms 15452 KB Ok
70 Correct 957 ms 16576 KB Ok
71 Correct 881 ms 16512 KB Ok
72 Correct 978 ms 19312 KB Ok
73 Correct 965 ms 17836 KB Ok
74 Correct 979 ms 17104 KB Ok
75 Correct 946 ms 16544 KB Ok
76 Correct 1039 ms 17360 KB Ok
77 Correct 918 ms 19944 KB Ok
78 Correct 983 ms 19020 KB Ok
79 Correct 954 ms 17196 KB Ok
80 Correct 849 ms 17088 KB Ok
81 Correct 935 ms 20208 KB Ok
82 Correct 927 ms 15464 KB Ok
83 Correct 899 ms 17128 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 336 KB Ok
6 Correct 1 ms 508 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 504 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 684 KB Ok
19 Correct 37 ms 1768 KB Ok
20 Correct 14 ms 932 KB Ok
21 Correct 41 ms 1932 KB Ok
22 Correct 20 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 508 KB Ok
32 Correct 1 ms 336 KB Ok
33 Correct 1 ms 532 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 657 ms 20404 KB Ok
40 Correct 596 ms 22924 KB Ok
41 Correct 1201 ms 27252 KB Ok
42 Correct 839 ms 31356 KB Ok
43 Correct 499 ms 17124 KB Ok
44 Correct 827 ms 25600 KB Ok
45 Correct 4 ms 592 KB Ok
46 Correct 5 ms 972 KB Ok
47 Correct 5 ms 592 KB Ok
48 Correct 5 ms 716 KB Ok
49 Correct 5 ms 592 KB Ok
50 Correct 3 ms 592 KB Ok
51 Correct 4 ms 592 KB Ok
52 Correct 6 ms 808 KB Ok
53 Correct 6 ms 592 KB Ok
54 Correct 5 ms 948 KB Ok
55 Correct 28 ms 1064 KB Ok
56 Correct 21 ms 952 KB Ok
57 Correct 20 ms 1020 KB Ok
58 Correct 19 ms 1036 KB Ok
59 Correct 18 ms 1088 KB Ok
60 Correct 17 ms 988 KB Ok
61 Correct 24 ms 1148 KB Ok
62 Correct 19 ms 944 KB Ok
63 Correct 20 ms 976 KB Ok
64 Correct 20 ms 948 KB Ok
65 Correct 284 ms 12788 KB Ok
66 Correct 388 ms 13504 KB Ok
67 Correct 363 ms 13620 KB Ok
68 Correct 229 ms 11640 KB Ok
69 Correct 311 ms 13176 KB Ok
70 Correct 280 ms 11328 KB Ok
71 Correct 213 ms 11500 KB Ok
72 Correct 235 ms 11876 KB Ok
73 Correct 378 ms 13168 KB Ok
74 Correct 264 ms 13748 KB Ok
75 Correct 371 ms 14296 KB Ok
76 Correct 312 ms 12384 KB Ok
77 Correct 263 ms 12200 KB Ok
78 Correct 218 ms 13132 KB Ok
79 Correct 304 ms 12960 KB Ok
80 Correct 913 ms 15452 KB Ok
81 Correct 957 ms 16576 KB Ok
82 Correct 881 ms 16512 KB Ok
83 Correct 978 ms 19312 KB Ok
84 Correct 965 ms 17836 KB Ok
85 Correct 979 ms 17104 KB Ok
86 Correct 946 ms 16544 KB Ok
87 Correct 1039 ms 17360 KB Ok
88 Correct 918 ms 19944 KB Ok
89 Correct 983 ms 19020 KB Ok
90 Correct 954 ms 17196 KB Ok
91 Correct 849 ms 17088 KB Ok
92 Correct 935 ms 20208 KB Ok
93 Correct 927 ms 15464 KB Ok
94 Correct 899 ms 17128 KB Ok
95 Correct 501 ms 34996 KB Ok
96 Correct 1046 ms 46500 KB Ok
97 Correct 1164 ms 40300 KB Ok
98 Correct 590 ms 29368 KB Ok
99 Correct 846 ms 38124 KB Ok
100 Correct 1060 ms 39800 KB Ok
101 Correct 956 ms 41680 KB Ok
102 Correct 796 ms 48832 KB Ok
103 Correct 876 ms 38304 KB Ok
104 Correct 1213 ms 52184 KB Ok
105 Correct 1161 ms 48652 KB Ok
106 Correct 729 ms 42612 KB Ok
107 Correct 988 ms 45072 KB Ok
108 Correct 1187 ms 53556 KB Ok
109 Correct 963 ms 44284 KB Ok
110 Execution timed out 2062 ms 63104 KB Time limit exceeded
111 Halted 0 ms 0 KB -