Submission #927543

#	Time	Username	Problem	Language	Result	Execution time	Memory
927543		CDuong	Stray Cat (JOI20_stray)	C++17	100 / 100	41 ms	16752 KiB

Anthony

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

using namespace std;

namespace {

int chain[] = {0, 1, 0, 0, 1, 1};

}

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
    vector<vector<int>> G(N);
    for (int i = 0; i < M; ++i) {
        G[U[i]].emplace_back(V[i]);
        G[V[i]].emplace_back(U[i]);
    }

    vector<int> dis(N, INT_MAX), color(N);
    queue<int> q;
    dis[0] = 0; q.emplace(0);
    while (not q.empty()) {
        int u = q.front(); q.pop();
        for (int v : G[u]) if (dis[v] > dis[u] + 1) {
            if (A == 2) {
                if (u == 0) color[v] = 0;
                else if ((int)G[u].size() >= 3) color[v] = !chain[color[u]];
                else color[v] = (color[u] + 1) % 6;
            }
            dis[v] = dis[u] + 1;
            q.emplace(v);
        }
    }

    vector<int> res(M);
    for (int i = 0; i < M; ++i) {
        int u, v;
        tie(u, v) = tie(U[i], V[i]);
        if (dis[u] > dis[v]) swap(u, v);
        if (A == 2) res[i] = chain[color[v]];
        else res[i] = dis[u] % 3;
    }

    // for (int val : res) cout << val << " ";
    // cout << endl;

    return res;
}

Catherine

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

using namespace std;

namespace {

int A, B;
int last = -1;
bool flag = false;
vector<int> vec;
vector<int> chain = {0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1};

}  // namespace

void Init(int A, int B) {
	::A = A;
	::B = B;
}

int Move(vector<int> cnt) {
	if (A != 2) {
		if (last != -1) ++cnt[last];
		int ap = 0;
		for (int val : cnt) ap += !!val;
		if (ap == 1) for (int i = 0; i < 3; ++i) if (cnt[i]) return last = i;
		if (cnt[0] == 0) return last = 1;
		if (cnt[1] == 0) return last = 2;
		if (cnt[2] == 0) return last = 0;
	}

	int deg = (last != -1);
	for (int i = 0; i < 2; ++i) deg += cnt[i];
	if (deg == 2) {
		if (flag) {
			for (int i = 0; i < 2; ++i) if (cnt[i] == 1) return last = i;
		}
		for (int i = 0; i < 2; ++i) {
			for (int _ = 0; _ < cnt[i]; ++_) vec.emplace_back(i);
		}
		if ((int)vec.size() == 5) {
			flag = true;
			bool way = false;
			for (int i = 0; i <= (int)chain.size() - (int)vec.size(); ++i) {
				int ccnt = 0;
				for (int j = 0; j < (int)vec.size(); ++j) ccnt += vec[j] == chain[i + j];
				way |= ccnt == (int)vec.size();
			}
			if (way) return -1;
			for (int i = 0; i < 2; ++i) if (cnt[i] == 1) return last = i;
		}
		else return last = vec.back();
	}
	else {
		flag = true;
		if (last != -1) ++cnt[last];
		for (int i = 0; i < 2; ++i) if (cnt[i] == 1) {
			if (last == i) return -1;
			else return last = i;
		}
	}
}

Compilation message (stderr)

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
   62 | }
      | ^

• 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