oj.uz

Submission #910970

# Submission time Handle Problem Language Result Execution time Memory
910970 2024-01-18T10:22:30 Z gawr_gura Stray Cat (JOI20_stray) C++17
20 / 100
 60 ms 16820 KB 
#include "Anthony.h"

#include <bits/stdc++.h>
using namespace std;

namespace std {

template <int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
        static_assert(D >= 1, "Dimension must be positive");
        template <typename... Args>
        Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};

template <typename T>
struct Vec<1, T> : public vector<T> {
        Vec(int n = 0, T val = T()) : std::vector<T>(n, val) {}
};

/* Example
        Vec<4, int64_t> f(n, k, 2, 2); // = f[n][k][2][2];
        Vec<2, int> adj(n); // graph
*/

template <class Fun>
class y_combinator_result {
        Fun fun_;

       public:
        template <class T>
        explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

        template <class... Args>
        decltype(auto) operator()(Args &&...args) {
                return fun_(std::ref(*this), std::forward<Args>(args)...);
        }
};

template <class Fun>
decltype(auto) y_combinator(Fun &&fun) {
        return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

/* Example
        auto fun = y_combinator([&](auto self, int x) -> void {
                self(x + 1);
        });
*/

}  // namespace std

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
        vector<vector<pair<int, int>>> adj(N);
        for (int i = 0; i < M; i++) adj[U[i]].emplace_back(V[i], i);
        for (int i = 0; i < M; i++) adj[V[i]].emplace_back(U[i], i);
        vector<int> depth(M, -1);
        vector<int> d(N, -1);
        if (A == 4) A = 3;
        if (A == 3) {
                queue<int> q;
                q.emplace(0);
                d[0] = 0;
                while (q.size()) {
                        int u = q.front();
                        q.pop();
                        for (auto &&[v, i] : adj[u]) {
                                if (d[v] == -1) {
                                        d[v] = d[u] + 1;
                                        depth[i] = d[u];
                                        q.emplace(v);
                                }
                        }
                }

                vector<int> ans(M);
                for (int i = 0; i < M; i++) {
                        if (depth[i] == -1) {
                                if (d[U[i]] == d[V[i]]) {
                                        ans[i] = d[U[i]] % 3;
                                } else {
                                        ans[i] = min(d[U[i]], d[V[i]]) % 3;
                                }
                        } else {
                                ans[i] = depth[i] % 3;
                        }
                }

                return ans;
        } else {
                vector<int> base({0, 1, 1, 0, 0, 1});
                vector<int> deg(N);
                for (int i = 0; i < M; i++) deg[U[i]]++, deg[V[i]]++;
                queue<int> q;
                q.emplace(0);
                d[0] = 0;
                vector<int> par(N);
                vector<int> ans(M);
                while (q.size()) {
                        int u = q.front();
                        q.pop();
                        for (auto &&[v, i] : adj[u]) {
                                if (d[v] == -1) {
                                        d[v] = d[u] + 1;
                                        if (u == 0 || deg[u] == 2) {
                                                ans[i] = (666666 - d[u]) % 6;
                                        } else {
                                                ans[i] = par[u] ^ 1;
                                        }
                                        par[v] = ans[i];
                                        q.emplace(v);
                                }
                        }
                }

                for (int i = 0; i < M; i++) ans[i] = base[ans[i]];

                return ans;
        }
}
#include "Catherine.h"

#include <bits/stdc++.h>
using namespace std;

namespace std {

template <int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
        static_assert(D >= 1, "Dimension must be positive");
        template <typename... Args>
        Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};

template <typename T>
struct Vec<1, T> : public vector<T> {
        Vec(int n = 0, T val = T()) : std::vector<T>(n, val) {}
};

/* Example
        Vec<4, int64_t> f(n, k, 2, 2); // = f[n][k][2][2];
        Vec<2, int> adj(n); // graph
*/

template <class Fun>
class y_combinator_result {
        Fun fun_;

       public:
        template <class T>
        explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

        template <class... Args>
        decltype(auto) operator()(Args &&...args) {
                return fun_(std::ref(*this), std::forward<Args>(args)...);
        }
};

template <class Fun>
decltype(auto) y_combinator(Fun &&fun) {
        return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

/* Example
        auto fun = y_combinator([&](auto self, int x) -> void {
                self(x + 1);
        });
*/

}  // namespace std

namespace {

int A, B;
stack<int> st;
int last = -1;
vector<int> base({0, 1, 1, 0, 0, 1});
vector<int> possible;
bool good = 0;

}  // namespace

void Init(int A, int B) {
        ::A = A;
        ::A = min(::A, 3);
        ::B = B;
        possible.resize(6);
        iota(possible.begin(), possible.end(), 0);
}

int Move(std::vector<int> y) {
        if (A == 3) {
                int cnt = 0;
                for (int i = 0; i < A; i++) {
                        cnt += y[i] > 0;
                }
                if (cnt == 1) {
                        for (int i = 0; i < A; i++) {
                                if (y[i] > 0) return i;
                        }
                } else {
                        for (int i = 0; i < A; i++) {
                                if (y[i] > 0 && y[(i + 1) % A] > 0) return i;
                        }
                }
        } else {
                if (last != -1) y[last]++;
                int cnt = 0;
                int xam = 0;
                for (int i = 0; i < A; i++) {
                        xam = max(xam, y[i]);
                        cnt += y[i] > 0;
                }
                int nxt = -1;
                if (xam > 1 && cnt > 1) {
                        good = 1;
                        for (int i = 0; i < A; i++) {
                                if (y[i] == 1) {
                                        int ans = last == i ? -1 : i;
                                        last = i;
                                        return ans;
                                }
                        }
                } else {
                        if (cnt == 1) {
                                for (int i = 0; i < A; i++) {
                                        if (y[i] == 1) {
                                                int ans = last == i ? -1 : i;
                                                last = i;
                                                return ans;
                                        }
                                }
                                for (int i = 0; i < A; i++) {
                                        if (y[i] > 0) nxt = i;
                                }
                                if (good) return nxt;
                                goto check;
                        } else {
                                if (good) {
                                        last ^= 1;
                                        return last;
                                } else {
                                        goto check;
                                }
                        }
                }
        check:;
                if (nxt == -1) {
                        nxt = last == -1 ? 1 : (cnt == 1 ? last : (last ^ 1));
                }
                vector<int> npo;
                for (int i : possible) {
                        if (base[(i + 1) % 6] == nxt) npo.emplace_back((i + 1) % 6);
                }
                possible.swap(npo);
                if (possible.size() == 0) {
                        good = 1;
                        return -1;
                } else {
                        last = nxt;
                        return nxt;
                }
        }
}

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:144:1: warning: control reaches end of non-void function [-Wreturn-type]
  144 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15648 KB Output is correct
2 Correct 1 ms 784 KB Output is correct
3 Correct 30 ms 15176 KB Output is correct
4 Correct 60 ms 16672 KB Output is correct
5 Correct 40 ms 16820 KB Output is correct
6 Correct 32 ms 15704 KB Output is correct
7 Correct 34 ms 15936 KB Output is correct
8 Correct 44 ms 16216 KB Output is correct
9 Correct 51 ms 16228 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15648 KB Output is correct
2 Correct 1 ms 784 KB Output is correct
3 Correct 30 ms 15176 KB Output is correct
4 Correct 60 ms 16672 KB Output is correct
5 Correct 40 ms 16820 KB Output is correct
6 Correct 32 ms 15704 KB Output is correct
7 Correct 34 ms 15936 KB Output is correct
8 Correct 44 ms 16216 KB Output is correct
9 Correct 51 ms 16228 KB Output is correct
10 Correct 31 ms 13568 KB Output is correct
11 Correct 38 ms 13564 KB Output is correct
12 Correct 30 ms 13652 KB Output is correct
13 Correct 32 ms 13652 KB Output is correct
14 Correct 32 ms 13724 KB Output is correct
15 Correct 44 ms 14072 KB Output is correct
16 Correct 40 ms 16284 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 13304 KB Output is correct
2 Correct 2 ms 780 KB Output is correct
3 Correct 28 ms 12856 KB Output is correct
4 Correct 41 ms 14500 KB Output is correct
5 Correct 48 ms 14692 KB Output is correct
6 Correct 47 ms 13324 KB Output is correct
7 Correct 28 ms 13308 KB Output is correct
8 Correct 39 ms 13996 KB Output is correct
9 Correct 50 ms 14244 KB Output is correct
10 Correct 36 ms 13680 KB Output is correct
11 Correct 42 ms 13440 KB Output is correct
12 Correct 31 ms 13692 KB Output is correct
13 Correct 35 ms 13652 KB Output is correct
14 Correct 38 ms 14104 KB Output is correct
15 Correct 34 ms 13848 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 13304 KB Output is correct
2 Correct 2 ms 780 KB Output is correct
3 Correct 28 ms 12856 KB Output is correct
4 Correct 41 ms 14500 KB Output is correct
5 Correct 48 ms 14692 KB Output is correct
6 Correct 47 ms 13324 KB Output is correct
7 Correct 28 ms 13308 KB Output is correct
8 Correct 39 ms 13996 KB Output is correct
9 Correct 50 ms 14244 KB Output is correct
10 Correct 36 ms 13680 KB Output is correct
11 Correct 42 ms 13440 KB Output is correct
12 Correct 31 ms 13692 KB Output is correct
13 Correct 35 ms 13652 KB Output is correct
14 Correct 38 ms 14104 KB Output is correct
15 Correct 34 ms 13848 KB Output is correct
16 Correct 34 ms 11632 KB Output is correct
17 Correct 24 ms 11624 KB Output is correct
18 Correct 26 ms 11636 KB Output is correct
19 Correct 35 ms 11572 KB Output is correct
20 Correct 38 ms 12272 KB Output is correct
21 Correct 33 ms 12204 KB Output is correct
22 Correct 48 ms 14164 KB Output is correct
23 Correct 41 ms 11744 KB Output is correct
24 Correct 32 ms 11836 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1056 KB Output is correct
2 Correct 1 ms 796 KB Output is correct
3 Correct 2 ms 1212 KB Output is correct
4 Correct 3 ms 1048 KB Output is correct
5 Correct 2 ms 1052 KB Output is correct
6 Correct 2 ms 1040 KB Output is correct
7 Correct 2 ms 1052 KB Output is correct
8 Correct 2 ms 1048 KB Output is correct
9 Correct 2 ms 1056 KB Output is correct
10 Correct 2 ms 1048 KB Output is correct
11 Correct 2 ms 1056 KB Output is correct
12 Correct 2 ms 1052 KB Output is correct
13 Correct 2 ms 1048 KB Output is correct
14 Correct 2 ms 964 KB Output is correct
15 Correct 2 ms 1056 KB Output is correct
16 Correct 2 ms 1048 KB Output is correct
17 Correct 2 ms 1056 KB Output is correct
18 Correct 2 ms 1056 KB Output is correct
19 Correct 2 ms 1060 KB Output is correct
20 Correct 2 ms 1048 KB Output is correct
21 Correct 2 ms 1048 KB Output is correct
22 Correct 3 ms 1128 KB Output is correct
23 Correct 2 ms 1052 KB Output is correct
24 Correct 1 ms 1128 KB Output is correct
25 Correct 2 ms 1060 KB Output is correct
26 Correct 2 ms 1168 KB Output is correct
27 Correct 2 ms 1056 KB Output is correct
28 Correct 2 ms 1040 KB Output is correct

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 11640 KB Output is correct
2 Correct 36 ms 11840 KB Output is correct
3 Correct 1 ms 780 KB Output is correct
4 Correct 30 ms 11472 KB Output is correct
5 Correct 55 ms 12704 KB Output is correct
6 Correct 41 ms 12884 KB Output is correct
7 Correct 36 ms 11764 KB Output is correct
8 Correct 32 ms 11868 KB Output is correct
9 Correct 34 ms 12868 KB Output is correct
10 Correct 46 ms 12888 KB Output is correct
11 Correct 50 ms 12796 KB Output is correct
12 Correct 39 ms 12676 KB Output is correct
13 Correct 38 ms 12872 KB Output is correct
14 Correct 33 ms 12732 KB Output is correct
15 Correct 39 ms 12636 KB Output is correct
16 Correct 32 ms 12884 KB Output is correct
17 Correct 36 ms 12536 KB Output is correct
18 Correct 31 ms 12612 KB Output is correct
19 Correct 33 ms 12536 KB Output is correct
20 Correct 44 ms 12488 KB Output is correct
21 Correct 33 ms 12528 KB Output is correct
22 Correct 35 ms 12620 KB Output is correct
23 Correct 34 ms 11640 KB Output is correct
24 Correct 33 ms 11644 KB Output is correct
25 Correct 27 ms 11552 KB Output is correct
26 Incorrect 26 ms 11628 KB Wrong Answer [6]
27 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11748 KB Output is correct
2 Correct 34 ms 11632 KB Output is correct
3 Correct 2 ms 784 KB Output is correct
4 Correct 24 ms 11484 KB Output is correct
5 Correct 38 ms 12804 KB Output is correct
6 Correct 45 ms 12768 KB Output is correct
7 Correct 36 ms 11992 KB Output is correct
8 Correct 27 ms 11804 KB Output is correct
9 Correct 37 ms 12948 KB Output is correct
10 Correct 37 ms 12836 KB Output is correct
11 Correct 32 ms 13048 KB Output is correct
12 Correct 33 ms 12916 KB Output is correct
13 Correct 46 ms 12848 KB Output is correct
14 Incorrect 31 ms 12792 KB Wrong Answer [6]
15 Halted 0 ms 0 KB -