oj.uz

Submission #910942

# Submission time Handle Problem Language Result Execution time Memory
910942 2024-01-18T09:58:04 Z gawr_gura Stray Cat (JOI20_stray) C++17
15 / 100
 43 ms 16800 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 {
                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> base({0, 1, 1, 0, 0, 1});

                vector<int> ans(M);
                for (int i = 0; i < M; i++) {
                        ans[i] = base[(1000000 - depth[i]) % 6];
                }

                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 32 ms 15956 KB Output is correct
2 Correct 1 ms 784 KB Output is correct
3 Correct 27 ms 15120 KB Output is correct
4 Correct 42 ms 16800 KB Output is correct
5 Correct 43 ms 16716 KB Output is correct
6 Correct 31 ms 15696 KB Output is correct
7 Correct 35 ms 15660 KB Output is correct
8 Correct 39 ms 16216 KB Output is correct
9 Correct 38 ms 16076 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 15956 KB Output is correct
2 Correct 1 ms 784 KB Output is correct
3 Correct 27 ms 15120 KB Output is correct
4 Correct 42 ms 16800 KB Output is correct
5 Correct 43 ms 16716 KB Output is correct
6 Correct 31 ms 15696 KB Output is correct
7 Correct 35 ms 15660 KB Output is correct
8 Correct 39 ms 16216 KB Output is correct
9 Correct 38 ms 16076 KB Output is correct
10 Correct 27 ms 13420 KB Output is correct
11 Correct 27 ms 13568 KB Output is correct
12 Correct 26 ms 13640 KB Output is correct
13 Correct 27 ms 13744 KB Output is correct
14 Correct 31 ms 13972 KB Output is correct
15 Correct 31 ms 14144 KB Output is correct
16 Correct 34 ms 16236 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13352 KB Output is correct
2 Correct 1 ms 780 KB Output is correct
3 Correct 25 ms 12864 KB Output is correct
4 Correct 38 ms 14680 KB Output is correct
5 Correct 38 ms 14724 KB Output is correct
6 Correct 28 ms 13388 KB Output is correct
7 Correct 30 ms 13252 KB Output is correct
8 Correct 36 ms 14184 KB Output is correct
9 Correct 37 ms 13864 KB Output is correct
10 Correct 31 ms 13764 KB Output is correct
11 Correct 32 ms 13604 KB Output is correct
12 Correct 31 ms 13668 KB Output is correct
13 Correct 31 ms 13536 KB Output is correct
14 Correct 33 ms 13856 KB Output is correct
15 Correct 33 ms 14048 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13352 KB Output is correct
2 Correct 1 ms 780 KB Output is correct
3 Correct 25 ms 12864 KB Output is correct
4 Correct 38 ms 14680 KB Output is correct
5 Correct 38 ms 14724 KB Output is correct
6 Correct 28 ms 13388 KB Output is correct
7 Correct 30 ms 13252 KB Output is correct
8 Correct 36 ms 14184 KB Output is correct
9 Correct 37 ms 13864 KB Output is correct
10 Correct 31 ms 13764 KB Output is correct
11 Correct 32 ms 13604 KB Output is correct
12 Correct 31 ms 13668 KB Output is correct
13 Correct 31 ms 13536 KB Output is correct
14 Correct 33 ms 13856 KB Output is correct
15 Correct 33 ms 14048 KB Output is correct
16 Correct 25 ms 11716 KB Output is correct
17 Correct 24 ms 11696 KB Output is correct
18 Correct 26 ms 11708 KB Output is correct
19 Correct 27 ms 11592 KB Output is correct
20 Correct 31 ms 12364 KB Output is correct
21 Correct 28 ms 12084 KB Output is correct
22 Correct 32 ms 14192 KB Output is correct
23 Correct 26 ms 11808 KB Output is correct
24 Correct 31 ms 11856 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1528 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 11200 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 11364 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -