Submission #1215993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215993		Tob	Stray Cat (JOI20_stray)	C++20	15 / 100	34 ms	13896 KiB

Anthony

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

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

vector<int> Mark(int n, int m, int a, int b, vector<int> u, vector<int> v) {
	vector<int> res(m);
	vector <vector <int> > adj(n);
	for (int i = 0; i < m; i++) {
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	if (a >= 3) {
		queue <int> q;
		q.push(0);
		vector <int> d(n, -1);
		d[0] = 0;
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (int y : adj[x]) if (d[y] == -1) {
				q.push(y);
				d[y] = d[x]+1;
			}
		}
		for (int i = 0; i < m; i++) {
			if (d[u[i]] == d[v[i]]) res[i] = d[u[i]]%3;
			else res[i] = min(d[u[i]], d[v[i]])%3;
		}
	}
	else {
		vector <int> dub(n, 0), re(n, -1), c(n, 0);
		int pe[] = {0, 1, 0, 0, 1, 1};
		auto dfs = [&](auto&& self, int x, int p) -> void {
			if (x) {
				if (!p) re[x] = c[x] = 0;
				else if (adj[x].size() == 2) {
					if (adj[p].size() > 2) c[x] = 1-re[p];
					else c[x] = c[p]+1;
					re[x] = pe[c[x]%6];
				}
				else re[x] = 1-re[p];
			}
			for (int y : adj[x]) if (y != p) {
				dub[y] = dub[x]+1;
				self(self, y, x);
			}
		};
		dfs(dfs, 0, -1);
		for (int i = 0; i < m; i++) {
			int x = u[i], y = v[i];
			if (dub[x] < dub[y]) x = y;
			res[i] = re[x];
		}
	}
	return res;
}

Catherine

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

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;



int a, b, fo, cur;
vector <int> vis;

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

int Move(vector<int> y) {
	if (a >= 3) {
		vector <int> v;
		for (int i = 0; i < 3; i++) if (y[i]) v.pb(i);
		if (v.size() == 1) return v[0];
		if (!y[1]) return 2;
		return v[0];
	}
	if (!fo && vis.empty()) {
		if (y[0]+y[1] != 2) {
			fo = 1;
			return (cur = (y[1] > 0));
		}
		cur = (y[1] > 0);
		if (y[cur] == 1) vis.pb(cur^1);
		else vis.pb(cur);
		vis.pb(cur);
		return cur;
	}
	if (!fo && vis.size() <= 4) {
		if (y[0]+y[1] != 1) {
			if (min(y[0], y[1]) == 0) {
				fo = 1;
				return -1;
			}
			fo = 1;
			cur ^= 1;
			return cur;
		}
		else {
			if (vis.size() == 4) vis.pb(y[1] > 0);
			int ok1 = 0, ok2 = 0;
			int pe[] = {0, 1, 0, 0, 1, 1};
			for (int i = 0; i < 6; i++) {
				int o1 = 1, o2 = 1;
				for (int j = 0; j < vis.size(); j++) o1 &= (vis[j] == pe[(i+j)%6]);
				for (int j = 0; j < vis.size(); j++) o2 &= (vis[j] == pe[(i+6-j)%6]);
				ok1 |= o1;
				ok2 |= o2;
			}
			if (ok1 == ok2) {
				vis.pb(cur = (y[1] > 0));
				return cur;
			}
			fo = 1;
			if (ok1) return -1;
		}
	}
	
	if (y[0]+y[1] == 1) return (cur = (y[1] > 0));
	cur ^= 1;
	assert(y[cur]);
	return cur;
}

• 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