Submission #212220

#	Time	Username	Problem	Language	Result	Execution time	Memory
212220		dolphingarlic	Stray Cat (JOI20_stray)	C++14	76 / 100	3083 ms	15268 KiB

Anthony

#include "Anthony.h"

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

namespace {

int label[6]{1, 1, 0, 1, 0, 0};

vector<pair<int, int>> graph[20000];
vector<int> X;
bool visited[20000];

void bfs() {
    queue<tuple<int, int, int>> q;
    q.push({0, 0, 0});
    visited[0] = true;
    while (q.size()) {
        int curr, depth, par;
        tie(curr, depth, par) = q.front();
        q.pop();
        if (graph[curr].size() == 2) {
            for (pair<int, int> i : graph[curr])
                if (!visited[i.first]) {
                    visited[i.first] = true;
                    X[i.second] = label[depth];
                    q.push({i.first, (depth + 1) % 6, label[depth]});
                }
        } else {
            for (pair<int, int> i : graph[curr])
                if (!visited[i.first]) {
                    visited[i.first] = true;
                    X[i.second] = 1 - par;
                    q.push({i.first, (par == 1 ? 5 : 1), 1 - par});
                }
        }
    }
}

}  // namespace

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
    X.resize(M);
    FOR(i, 0, M) {
        graph[U[i]].push_back({V[i], i});
        graph[V[i]].push_back({U[i], i});
    }
    bfs();
    return X;
}

Catherine

#include "Catherine.h"

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

namespace {

int A, B, last_visited, ans;
bool going_up, init;
deque<int> seq, target = {0, 0, 1, 1, 0, 1};

}  // namespace

void Init(int A, int B) {
    ::A = A;
    ::B = B;
    going_up = false;
    init = true;
    last_visited = ans = -2;
}

int Move(vector<int> y) {
    int deg = accumulate(y.begin(), y.end(), 0), uniq = 0;
    for (int i : y)
        if (i) uniq++;

    if (going_up || (init && deg == 1)) {
        going_up = true;
        if (uniq == 1) {
            FOR(i, 0, 2) if (y[i]) ans = i;
        } else {
            if (ans == -1)
                y[last_visited]++;
            else
                y[ans]++;
            FOR(i, 0, 2) if (y[i] == 1) ans = i;
            if (ans == last_visited) ans = -1;
        }
    } else {
        if (init) {
            if (deg == 2) {
                FOR(i, 0, 2) if (y[i]) ans = i;
                seq.push_back(ans);
                B -= 2;
            } else {
                FOR(i, 0, 2) if (y[i] == 1) ans = i;
                going_up = true;
            }
        } else {
            if (deg == 1) {
                if (!B) {
                    while (seq[0] || seq[1]) {
                        seq.push_back(seq.front());
                        seq.pop_front();
                    }

                    going_up = true;

                    if (seq == target) {
                        last_visited = ans;
                        return ans = -1;
                    } else {
                        FOR(i, 0, 2) if (y[i]) ans = i;
                    }
                } else {
                    FOR(i, 0, 2) if (y[i]) ans = i;
                    seq.push_back(ans);
                    B -= 2;
                }
            } else {
                if (ans == -1)
                    y[last_visited]++;
                else
                    y[ans]++;

                FOR(i, 0, 2) if (y[i] == 1) ans = i;
                if (ans == last_visited) ans = -1;
                going_up = true;
            }
        }
    }
    init = false;
    return last_visited = ans;
}

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