Submission #910906

#	Time	Username	Problem	Language	Result	Execution time	Memory
910906		gawr_gura	Stray Cat (JOI20_stray)	C++17	20 / 100	47 ms	16256 KiB

Anthony

#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

namespace {

int FunctionExample(int i, int A) {
        return i % A;
}

}  // namespace

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 {
                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++) {
                        ans[i] = depth[i] % A;
                }

                return ans;
        }
}

Catherine

#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;

}  // namespace

void Init(int A, int B) {
        ::A = A;
        ::A = min(::A, 3);
        ::B = B;
}

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 {
                int cnt = 0;
                for (int i = 0; i < A; i++) {
                        cnt += y[i] > 0;
                }
                if (cnt == 0) {
                        last = st.top();
                        st.pop();
                        return -1;
                } else if (cnt == 1) {
                        for (int i = 0; i < A; i++) {
                                if (y[i] > 0) {
                                        if (y[i] == 1) {
                                                return i;
                                                st.emplace(i);
                                        } else {
                                                last = st.top();
                                                st.pop();
                                                return -1;
                                        }
                                }
                        }
                } else {
                        cnt = 0;
                        for (int i = 0; i < A; i++) {
                                cnt += y[i] == 1;
                        }
                        assert(cnt > 0);
                        if (cnt == 1) {
                                for (int i = 0; i < A; i++) {
                                        if (y[i] == 1) {
                                                st.emplace(i);
                                                return i;
                                        }
                                }
                        } else {
                                if (last != -1) {
                                        st.emplace(last ^ 1);
                                        return last ^ 1;
                                } else {
                                        st.emplace(0);
                                        return 0;
                                }
                        }
                }
        }
}

Compilation message (stderr)

Anthony.cpp:54:5: warning: 'int {anonymous}::FunctionExample(int, int)' defined but not used [-Wunused-function]
   54 | int FunctionExample(int i, int A) {
      |     ^~~~~~~~~~~~~~~

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

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 0 / 71
• Subtask 7: 0 / 9