Submission #910996

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
910996	2024-01-18T10:55:06 Z	gawr_gura	Stray Cat (JOI20_stray)	C++17	20 / 100	47 ms	16296 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 {
                                                for (int j = 0; j < 6; j++) {
                                                        if (((666666 - j) % 6) == (par[u] ^ 1) % 6) d[v] = j;
                                                }
                                                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) {
                                        last = nxt;
                                        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:148:1: warning: control reaches end of non-void function [-Wreturn-type]
  148 | }
      | ^

Subtask #1

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	15408 KB	Output is correct
2	Correct	0 ms	792 KB	Output is correct
3	Correct	26 ms	14720 KB	Output is correct
4	Correct	39 ms	16296 KB	Output is correct
5	Correct	36 ms	16292 KB	Output is correct
6	Correct	30 ms	15236 KB	Output is correct
7	Correct	28 ms	15228 KB	Output is correct
8	Correct	32 ms	16004 KB	Output is correct
9	Correct	34 ms	15996 KB	Output is correct

Subtask #2

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	15408 KB	Output is correct
2	Correct	0 ms	792 KB	Output is correct
3	Correct	26 ms	14720 KB	Output is correct
4	Correct	39 ms	16296 KB	Output is correct
5	Correct	36 ms	16292 KB	Output is correct
6	Correct	30 ms	15236 KB	Output is correct
7	Correct	28 ms	15228 KB	Output is correct
8	Correct	32 ms	16004 KB	Output is correct
9	Correct	34 ms	15996 KB	Output is correct
10	Correct	33 ms	13280 KB	Output is correct
11	Correct	28 ms	13284 KB	Output is correct
12	Correct	26 ms	13296 KB	Output is correct
13	Correct	31 ms	13260 KB	Output is correct
14	Correct	28 ms	13548 KB	Output is correct
15	Correct	28 ms	13800 KB	Output is correct
16	Correct	36 ms	15748 KB	Output is correct

Subtask #3

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	13016 KB	Output is correct
2	Correct	1 ms	780 KB	Output is correct
3	Correct	26 ms	12424 KB	Output is correct
4	Correct	38 ms	13980 KB	Output is correct
5	Correct	33 ms	14256 KB	Output is correct
6	Correct	27 ms	13004 KB	Output is correct
7	Correct	26 ms	12924 KB	Output is correct
8	Correct	32 ms	13688 KB	Output is correct
9	Correct	34 ms	13708 KB	Output is correct
10	Correct	31 ms	13432 KB	Output is correct
11	Correct	30 ms	13452 KB	Output is correct
12	Correct	28 ms	13440 KB	Output is correct
13	Correct	32 ms	13392 KB	Output is correct
14	Correct	32 ms	13780 KB	Output is correct
15	Correct	32 ms	13688 KB	Output is correct

Subtask #4

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	13016 KB	Output is correct
2	Correct	1 ms	780 KB	Output is correct
3	Correct	26 ms	12424 KB	Output is correct
4	Correct	38 ms	13980 KB	Output is correct
5	Correct	33 ms	14256 KB	Output is correct
6	Correct	27 ms	13004 KB	Output is correct
7	Correct	26 ms	12924 KB	Output is correct
8	Correct	32 ms	13688 KB	Output is correct
9	Correct	34 ms	13708 KB	Output is correct
10	Correct	31 ms	13432 KB	Output is correct
11	Correct	30 ms	13452 KB	Output is correct
12	Correct	28 ms	13440 KB	Output is correct
13	Correct	32 ms	13392 KB	Output is correct
14	Correct	32 ms	13780 KB	Output is correct
15	Correct	32 ms	13688 KB	Output is correct
16	Correct	24 ms	11384 KB	Output is correct
17	Correct	25 ms	11348 KB	Output is correct
18	Correct	26 ms	11180 KB	Output is correct
19	Correct	28 ms	11192 KB	Output is correct
20	Correct	30 ms	11808 KB	Output is correct
21	Correct	27 ms	11752 KB	Output is correct
22	Correct	36 ms	13884 KB	Output is correct
23	Correct	28 ms	11408 KB	Output is correct
24	Correct	26 ms	11512 KB	Output is correct

Subtask #5

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1048 KB	Output is correct
2	Correct	0 ms	776 KB	Output is correct
3	Correct	2 ms	1056 KB	Output is correct
4	Correct	2 ms	1052 KB	Output is correct
5	Correct	2 ms	1044 KB	Output is correct
6	Correct	2 ms	1048 KB	Output is correct
7	Correct	2 ms	1044 KB	Output is correct
8	Correct	2 ms	1044 KB	Output is correct
9	Correct	2 ms	1044 KB	Output is correct
10	Correct	2 ms	1056 KB	Output is correct
11	Correct	2 ms	1048 KB	Output is correct
12	Correct	2 ms	1044 KB	Output is correct
13	Correct	2 ms	868 KB	Output is correct
14	Correct	2 ms	1304 KB	Output is correct
15	Correct	2 ms	1036 KB	Output is correct
16	Correct	2 ms	1052 KB	Output is correct
17	Correct	2 ms	1044 KB	Output is correct
18	Correct	2 ms	1044 KB	Output is correct
19	Correct	2 ms	1044 KB	Output is correct
20	Correct	1 ms	1052 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	1312 KB	Output is correct
24	Correct	2 ms	1060 KB	Output is correct
25	Correct	2 ms	1060 KB	Output is correct
26	Correct	2 ms	1048 KB	Output is correct
27	Correct	2 ms	1052 KB	Output is correct
28	Correct	2 ms	1444 KB	Output is correct

Subtask #6

0 / 71.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	11068 KB	Output is correct
2	Correct	28 ms	11440 KB	Output is correct
3	Correct	1 ms	780 KB	Output is correct
4	Correct	23 ms	11116 KB	Output is correct
5	Correct	34 ms	12424 KB	Output is correct
6	Correct	47 ms	12340 KB	Output is correct
7	Correct	27 ms	11388 KB	Output is correct
8	Correct	30 ms	11384 KB	Output is correct
9	Correct	32 ms	12436 KB	Output is correct
10	Correct	33 ms	12360 KB	Output is correct
11	Correct	33 ms	12416 KB	Output is correct
12	Correct	32 ms	12416 KB	Output is correct
13	Correct	33 ms	12412 KB	Output is correct
14	Correct	32 ms	12484 KB	Output is correct
15	Correct	32 ms	12420 KB	Output is correct
16	Correct	31 ms	12504 KB	Output is correct
17	Correct	28 ms	12172 KB	Output is correct
18	Correct	34 ms	12156 KB	Output is correct
19	Correct	34 ms	12176 KB	Output is correct
20	Correct	32 ms	12160 KB	Output is correct
21	Correct	30 ms	12016 KB	Output is correct
22	Correct	28 ms	12172 KB	Output is correct
23	Correct	27 ms	10920 KB	Output is correct
24	Incorrect	27 ms	10916 KB	Wrong Answer [6]
25	Halted	0 ms	0 KB	-

Subtask #7

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	11120 KB	Output is correct
2	Correct	27 ms	11160 KB	Output is correct
3	Correct	1 ms	784 KB	Output is correct
4	Correct	22 ms	11260 KB	Output is correct
5	Correct	33 ms	12240 KB	Output is correct
6	Correct	31 ms	12420 KB	Output is correct
7	Correct	27 ms	11396 KB	Output is correct
8	Correct	27 ms	11648 KB	Output is correct
9	Correct	32 ms	12376 KB	Output is correct
10	Correct	34 ms	12424 KB	Output is correct
11	Correct	34 ms	12380 KB	Output is correct
12	Correct	33 ms	12408 KB	Output is correct
13	Correct	33 ms	12288 KB	Output is correct
14	Correct	38 ms	12420 KB	Output is correct
15	Incorrect	30 ms	12420 KB	Wrong Answer [6]
16	Halted	0 ms	0 KB	-