Submission #780074

#	Time	Username	Problem	Language	Result	Execution time	Memory
780074		ymm	Stray Cat (JOI20_stray)	C++17	15 / 100	51 ms	16988 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;

namespace {

	const int N = 20'010;
	vector<int> A[N];
	int dis[N];
	void bfs() {
		memset(dis, -1, sizeof(dis));
		vector<int> q = {0};
		dis[0] = 0;
		Loop (i,0,q.size()) {
			int v = q[i];
			for (int u : A[v]) {
				if (dis[u] == -1) {
					dis[u] = dis[v]+1;
					q.push_back(u);
				}
			}
		}
	}
	int height[N];
	int val[N];
	const int pat[] = {0, 0, 1, 0, 1, 1};
	const int pats = sizeof(pat)/sizeof(*pat);
	void dfs(int v, int p, int x, int h) {
		height[v] = h;
		val[v] = pat[x%pats];
		for (int u : A[v]) {
			if (u == p)
				continue;
			if (A[v].size() == 2)
				dfs(u, v, x+1, h+1);
			else
				dfs(u, v, val[v]==0? 2: 0, h+1);
		}
	}

}  // namespace

std::vector<int> Mark(int N, int M, int a, int b,
                      std::vector<int> U, std::vector<int> V) {
	Loop (i,0,M) {
		int v = V[i], u = U[i];
		A[v].push_back(u);
		A[u].push_back(v);
	}
	vector<int> ans(M);
	if (a == 2) {
		dfs(0, -1, 0, 0);
		Loop (i,0,M) {
			int v = V[i], u = U[i];
			if (height[v] > height[u])
				swap(v, u);
			ans[i] = val[u];
		}
	} else {
		bfs();
		Loop (i,0,M) {
			int v = V[i], u = U[i];
			ans[i] = min(dis[v], dis[u]) % 3;
		}
	}
	return ans;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;

namespace {

	int (*move_ptr)(vector<int>);
	int lst = -1;

	int move3(vector<int> y) {
		if (y[0] && y[1])
			return 0;
		if (y[1] && y[2])
			return 1;
		if (y[2] && y[0])
			return 2;
		return !!y[1] + 2*!!y[2];
	}

	int move_up(vector<int> y) {
		if (!!y[0] + !!y[1] == 1)
			return !!y[1];
		if (y[0] + (lst == 0) == 1)
			return 0;
		else
			return 1;
	}

	const int pat[] = {0, 0, 1, 0, 1, 1};
	const int pats = sizeof(pat)/sizeof(*pat);
	vector<int> cur_pat;

	bool test() {
		vector<int> p(pat, pat+pats), q(cur_pat);
		Loop (_,0,pats) {
			int x = p.back();
			p.pop_back();
			if (p == q)
				return 1;
			p.insert(p.begin(), x);
		}
		return 0;
	}

	int move_test(vector<int> y) {
		if (y[0] + y[1] + (lst != -1) != 2)
			return (move_ptr = move_up)(y);
		if (cur_pat.size() == 0) {
			if (y[0] && y[1]) {
				cur_pat = {0, 1};
				return 1;
			}
			if (y[0]) {
				cur_pat = {0, 0};
				return 0;
			} else {
				cur_pat = {1, 1};
				return 1;
			}
		}
		cur_pat.push_back(!!y[1]);
		if (cur_pat.size() == 5) {
			move_ptr = move_up;
			if (test())
				return move_up(y);
			else
				return -1;
		}
		return !!y[1];
	}

}  // namespace

void Init(int A, int B) {
	move_ptr = A == 2? move_test: move3;
}

int Move(std::vector<int> y) {
	int x = move_ptr(y);
	lst = x;
	return x;
}

Compilation message (stderr)

Anthony.cpp: In function 'void {anonymous}::bfs()':
Anthony.cpp:3:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
      |                                          ^
Anthony.cpp:16:3: note: in expansion of macro 'Loop'
   16 |   Loop (i,0,q.size()) {
      |   ^~~~

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