Submission #1332320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1332320		MisterReaper	Stray Cat (JOI20_stray)	C++20	100 / 100	175 ms	13936 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>

namespace {

}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
    std::vector<int> X(M, -1);
    if (A >= 3) {
        std::vector<std::vector<int>> adj(N);
        for (int i = 0; i < M; ++i) {
            adj[U[i]].emplace_back(V[i]);
            adj[V[i]].emplace_back(U[i]);
        }
        std::vector<int> dis(N, -1);
        std::queue<int> que;
        que.emplace(0);
        dis[0] = 0;
        while (!que.empty()) {
            auto v = que.front();
            que.pop();
            for (auto u : adj[v]) {
                if (dis[u] == -1) {
                    dis[u] = dis[v] + 1;
                    que.emplace(u);
                }
            }
        }
        for (int i = 0; i < M; ++i) {
            X[i] = std::min(dis[U[i]], dis[V[i]]) % 3;
        } 
    } else {
        std::vector<std::vector<int>> adj(N);
        for (int i = 0; i < M; ++i) {
            adj[U[i]].emplace_back(i);
            adj[V[i]].emplace_back(i);
        }
        std::vector<int> p = {0, 1, 0, 0, 1, 1};
        auto dfs = [&](auto&& self, int v, int lst) -> void {
            std::cerr << v << ' ' << lst << '\n';
            for (auto i : adj[v]) {
                int u = U[i] ^ V[i] ^ v;
                adj[u].erase(std::find(adj[u].begin(), adj[u].end(), i));
                if (lst >= 0) {
                    if (adj[u].size() == 1) {
                        if (lst == 0){ 
                            X[i] = p[1];
                            self(self, u, -3);
                        } else {
                            X[i] = p[0];
                            self(self, u, -2);
                        }
                    } else {
                        X[i] = !lst;
                        self(self, u, X[i]);
                    }
                } else {
                    X[i] = p[-lst - 1];
                    if (adj[u].size() == 1) {
                        self(self, u, lst % 6 - 1);
                    } else {
                        self(self, u, X[i]);
                    }
                }
            }
        };
        dfs(dfs, 0, 0);
    }
    for (int i = 0; i < M; ++i) {
        std::cerr << U[i] << ' ' << V[i] << ' ' << X[i] << '\n';
    }
    return X;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>

namespace {

int A;
int B;
int found = -1;
std::vector<int> stk;

}  // namespace

void Init(int A, int B) {
    ::A = A;
    ::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]) {
                    return i;
                }
            }
        } else {
            assert(cnt == 2);
            if (y[2] == 0) {
                return 0;
            }
            if (y[0] == 0) {
                return 1;
            }
            return 2;
        }
    } else {
        if (found != -1) {
            int cnt = 0;
            for (int i = 0; i < 2; ++i) {
                cnt += y[i];
            }
            if (cnt == 1) {
                assert((y[0] == 1) ^ (y[1] == 1));
                if (y[0] == 1) {
                    found = 0;
                } else {
                    found = 1;
                }
            } else {
                assert(!stk.empty());
                y[stk.back()] += 1;
                assert((y[0] == 1) ^ (y[1] == 1));
                if (y[0] == 1) {
                    found = 0;
                } else {
                    found = 1;
                }
            }
            assert(y[found] != 0);
            stk.emplace_back(found);
            return found;
        } else {
            int cnt = 0;
            for (int i = 0; i < 2; ++i) {
                cnt += y[i];
            }
            std::cerr << cnt << " :: " << !stk.empty() << '\n';
            if (cnt + !stk.empty() != 2) {
                std::cerr << "stk:";
                for (auto i : stk) {
                    std::cerr << ' ' << i;
                }
                std::cerr << '\n';
                if (!stk.empty()) {
                    y[stk.back()] += 1;
                }
                std::cerr << y[0] << ' ' << y[1] << '\n';
                if (y[0] == 1) {
                    found = 0;
                    stk.emplace_back(0);
                    if (stk.size() > 1 && stk.end()[-2] == 0) {
                        return -1;
                    } else {
                        return 0;
                    }
                } else {
                    found = 1;
                    stk.emplace_back(1);
                    if (stk.size() > 1 && stk.end()[-2] == 1) {
                        return -1;
                    } else {
                        return 1;
                    }
                }
            } else {
                if (stk.empty()) {
                    if (y[0] == 2 && y[1] == 0) {
                        stk.emplace_back(0);
                        stk.emplace_back(0);
                        return 0;
                    } else if (y[0] == 1 && y[1] == 1) {
                        stk.emplace_back(0);
                        stk.emplace_back(1);
                        return 1;
                    } else if (y[0] == 0 && y[1] == 2) {
                        stk.emplace_back(1);
                        stk.emplace_back(1);
                        return 1;
                    } else {
                        assert(false);
                    }
                } else {
                    assert((y[0] == 1) ^ (y[1] == 1));
                    if (y[0] == 1) {
                        stk.emplace_back(0);
                    } else {
                        stk.emplace_back(1);
                    }
                    if (stk.size() == 5) {
                        std::vector<int> v = {0, 1, 0, 0, 1, 1};
                        for (int i = 0; i < 6; ++i) {
                            bool good = true;
                            for (int j = 0; j < 5; ++j) {
                                good &= stk[j] == v[(i + j) % 6];
                            }
                            if (good) {
                                found = stk.end()[-2];
                                stk.emplace_back(found);
                                return -1;
                            }
                        }
                        found = stk.back();
                        return stk.back();
                    } else {
                        return stk.back();
                    }
                }
            }
        }
    }
    return -1;
}

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