oj.uz

Submission #1114164

# Submission time Handle Problem Language Result Execution time Memory
1114164 2024-11-18T09:07:00 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
15 / 100
 50 ms 1896 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];
                }
            }

            std::queue<int> que;
            for (int i = 0; i <= n; ++i) {
                if (ein[i] == 0) {
                    pre[i] = 1;
                    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 = 1, 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 336 KB Ok
6 Correct 1 ms 504 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 33 ms 1644 KB Ok
8 Correct 14 ms 1184 KB Ok
9 Correct 50 ms 1896 KB Ok
10 Correct 19 ms 1120 KB Ok

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Ok
2 Correct 1 ms 504 KB Ok
3 Correct 1 ms 504 KB Ok
4 Correct 1 ms 336 KB Ok
5 Incorrect 1 ms 336 KB All the numbers must be nonzero
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 508 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #5
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 504 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 504 KB Ok
15 Correct 1 ms 504 KB Ok
16 Correct 1 ms 336 KB Ok
17 Incorrect 1 ms 336 KB All the numbers must be nonzero
18 Halted 0 ms 0 KB -

Subtask #6
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 504 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 33 ms 1644 KB Ok
20 Correct 14 ms 1184 KB Ok
21 Correct 50 ms 1896 KB Ok
22 Correct 19 ms 1120 KB Ok
23 Correct 1 ms 336 KB Ok
24 Correct 1 ms 504 KB Ok
25 Correct 1 ms 504 KB Ok
26 Correct 1 ms 336 KB Ok
27 Incorrect 1 ms 336 KB All the numbers must be nonzero
28 Halted 0 ms 0 KB -

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 504 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 33 ms 1644 KB Ok
20 Correct 14 ms 1184 KB Ok
21 Correct 50 ms 1896 KB Ok
22 Correct 19 ms 1120 KB Ok
23 Correct 1 ms 336 KB Ok
24 Correct 1 ms 504 KB Ok
25 Correct 1 ms 504 KB Ok
26 Correct 1 ms 336 KB Ok
27 Incorrect 1 ms 336 KB All the numbers must be nonzero
28 Halted 0 ms 0 KB -