답안 #910983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
910983	2024-01-18T10:36:23 Z	gawr_gura	길고양이 (JOI20_stray)	C++17	20 / 100	43 ms	16844 KB

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

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

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;
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) {
                                                good = 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:145:1: warning: control reaches end of non-void function [-Wreturn-type]
  145 | }
      | ^

Subtask #1

2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	15940 KB	Output is correct
2	Correct	1 ms	780 KB	Output is correct
3	Correct	26 ms	15068 KB	Output is correct
4	Correct	43 ms	16664 KB	Output is correct
5	Correct	39 ms	16844 KB	Output is correct
6	Correct	32 ms	15616 KB	Output is correct
7	Correct	31 ms	15684 KB	Output is correct
8	Correct	36 ms	16192 KB	Output is correct
9	Correct	37 ms	16256 KB	Output is correct

Subtask #2

2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	15940 KB	Output is correct
2	Correct	1 ms	780 KB	Output is correct
3	Correct	26 ms	15068 KB	Output is correct
4	Correct	43 ms	16664 KB	Output is correct
5	Correct	39 ms	16844 KB	Output is correct
6	Correct	32 ms	15616 KB	Output is correct
7	Correct	31 ms	15684 KB	Output is correct
8	Correct	36 ms	16192 KB	Output is correct
9	Correct	37 ms	16256 KB	Output is correct
10	Correct	27 ms	13660 KB	Output is correct
11	Correct	30 ms	13756 KB	Output is correct
12	Correct	27 ms	13644 KB	Output is correct
13	Correct	28 ms	13340 KB	Output is correct
14	Correct	40 ms	13904 KB	Output is correct
15	Correct	36 ms	14112 KB	Output is correct
16	Correct	36 ms	16164 KB	Output is correct

Subtask #3

2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	13364 KB	Output is correct
2	Correct	1 ms	796 KB	Output is correct
3	Correct	26 ms	12856 KB	Output is correct
4	Correct	40 ms	14640 KB	Output is correct
5	Correct	37 ms	14528 KB	Output is correct
6	Correct	28 ms	13364 KB	Output is correct
7	Correct	28 ms	13400 KB	Output is correct
8	Correct	35 ms	13956 KB	Output is correct
9	Correct	35 ms	14416 KB	Output is correct
10	Correct	32 ms	13696 KB	Output is correct
11	Correct	33 ms	13604 KB	Output is correct
12	Correct	33 ms	13504 KB	Output is correct
13	Correct	38 ms	13592 KB	Output is correct
14	Correct	36 ms	13924 KB	Output is correct
15	Correct	36 ms	13996 KB	Output is correct

Subtask #4

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	13364 KB	Output is correct
2	Correct	1 ms	796 KB	Output is correct
3	Correct	26 ms	12856 KB	Output is correct
4	Correct	40 ms	14640 KB	Output is correct
5	Correct	37 ms	14528 KB	Output is correct
6	Correct	28 ms	13364 KB	Output is correct
7	Correct	28 ms	13400 KB	Output is correct
8	Correct	35 ms	13956 KB	Output is correct
9	Correct	35 ms	14416 KB	Output is correct
10	Correct	32 ms	13696 KB	Output is correct
11	Correct	33 ms	13604 KB	Output is correct
12	Correct	33 ms	13504 KB	Output is correct
13	Correct	38 ms	13592 KB	Output is correct
14	Correct	36 ms	13924 KB	Output is correct
15	Correct	36 ms	13996 KB	Output is correct
16	Correct	26 ms	11700 KB	Output is correct
17	Correct	30 ms	11676 KB	Output is correct
18	Correct	31 ms	11564 KB	Output is correct
19	Correct	27 ms	11672 KB	Output is correct
20	Correct	31 ms	12292 KB	Output is correct
21	Correct	28 ms	12124 KB	Output is correct
22	Correct	31 ms	14192 KB	Output is correct
23	Correct	27 ms	11872 KB	Output is correct
24	Correct	32 ms	11768 KB	Output is correct

Subtask #5

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1056 KB	Output is correct
2	Correct	1 ms	780 KB	Output is correct
3	Correct	2 ms	1048 KB	Output is correct
4	Correct	2 ms	1052 KB	Output is correct
5	Correct	2 ms	1308 KB	Output is correct
6	Correct	2 ms	1040 KB	Output is correct
7	Correct	2 ms	1048 KB	Output is correct
8	Correct	2 ms	1056 KB	Output is correct
9	Correct	2 ms	1048 KB	Output is correct
10	Correct	2 ms	1040 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	1052 KB	Output is correct
15	Correct	2 ms	1052 KB	Output is correct
16	Correct	2 ms	1052 KB	Output is correct
17	Correct	2 ms	1052 KB	Output is correct
18	Correct	2 ms	1040 KB	Output is correct
19	Correct	2 ms	1296 KB	Output is correct
20	Correct	2 ms	1056 KB	Output is correct
21	Correct	2 ms	1056 KB	Output is correct
22	Correct	2 ms	1044 KB	Output is correct
23	Correct	2 ms	1056 KB	Output is correct
24	Correct	2 ms	1040 KB	Output is correct
25	Correct	2 ms	1056 KB	Output is correct
26	Correct	2 ms	1056 KB	Output is correct
27	Correct	2 ms	1072 KB	Output is correct
28	Correct	2 ms	1044 KB	Output is correct

Subtask #6

0 / 71.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	11560 KB	Output is correct
2	Correct	32 ms	11844 KB	Output is correct
3	Correct	1 ms	780 KB	Output is correct
4	Correct	24 ms	11564 KB	Output is correct
5	Correct	34 ms	13032 KB	Output is correct
6	Correct	34 ms	12788 KB	Output is correct
7	Correct	32 ms	11712 KB	Output is correct
8	Correct	32 ms	11768 KB	Output is correct
9	Correct	39 ms	12820 KB	Output is correct
10	Correct	36 ms	12852 KB	Output is correct
11	Correct	33 ms	12896 KB	Output is correct
12	Correct	41 ms	12804 KB	Output is correct
13	Correct	34 ms	12872 KB	Output is correct
14	Correct	39 ms	12676 KB	Output is correct
15	Correct	40 ms	13108 KB	Output is correct
16	Correct	33 ms	12888 KB	Output is correct
17	Correct	38 ms	12548 KB	Output is correct
18	Correct	30 ms	12612 KB	Output is correct
19	Correct	33 ms	12632 KB	Output is correct
20	Correct	33 ms	12724 KB	Output is correct
21	Correct	33 ms	12300 KB	Output is correct
22	Correct	35 ms	12572 KB	Output is correct
23	Correct	27 ms	11640 KB	Output is correct
24	Correct	26 ms	11640 KB	Output is correct
25	Correct	31 ms	11552 KB	Output is correct
26	Incorrect	27 ms	11640 KB	Wrong Answer [6]
27	Halted	0 ms	0 KB	-

Subtask #7

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	11648 KB	Output is correct
2	Correct	31 ms	11952 KB	Output is correct
3	Correct	1 ms	796 KB	Output is correct
4	Correct	25 ms	11524 KB	Output is correct
5	Correct	40 ms	12876 KB	Output is correct
6	Correct	33 ms	12772 KB	Output is correct
7	Correct	27 ms	11824 KB	Output is correct
8	Correct	28 ms	11852 KB	Output is correct
9	Correct	43 ms	12864 KB	Output is correct
10	Correct	35 ms	12892 KB	Output is correct
11	Correct	36 ms	12848 KB	Output is correct
12	Correct	43 ms	12788 KB	Output is correct
13	Correct	36 ms	12880 KB	Output is correct
14	Correct	36 ms	12824 KB	Output is correct
15	Incorrect	30 ms	12884 KB	Wrong Answer [6]
16	Halted	0 ms	0 KB	-