Submission #223874

#	Time	Username	Problem	Language	Result	Execution time	Memory
223874		super_j6	Stray Cat (JOI20_stray)	C++14	100 / 100	106 ms	16796 KiB

Anthony

#include "Anthony.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
#define vi vector<int>

const int maxn = 20000, k = 6;
int d[maxn];
vi graph[maxn];
queue<int> q;
int s[k] = {0, 0, 1, 0, 1, 1};
vi ans;

vi Mark(int n, int m, int a, int b, vi u, vi v){
	ans.resize(m);
	for(int i = 0; i < m; i++){
		graph[u[i]].push_back(i);
		graph[v[i]].push_back(i);
	}
	d[0] = 1;
	if(a > 2){
		q.push(0);
		while(!q.empty()){
			int c = q.front();
			q.pop();
			for(int i : graph[c]){
				int j = u[i] ^ v[i] ^ c; 
				if(!d[j]){
					d[j] = d[c] + 1;
					q.push(j);
				}
				if(d[j] == d[c] || d[j] == d[c] + 1){
					ans[i] = d[c] % 3;
				}
			}
		}
	}else{
		function<void(int, int)> dfs = [&](int c, int p){
			for(int i : graph[c]){
				int j = u[i] ^ v[i] ^ c;
				if(j != p){
					ans[i] = s[d[c]];
					d[j] = graph[j].size() > 2 ? (ans[i] ^ 1) << 1 : (d[c] + 1) % k;
					dfs(j, c);
				}
			}
		};
		dfs(0, -1);
	}
	return ans;
}

Catherine

#include "Catherine.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define f first
#define s second
#define vi vector<int>

const int k = 6;
int a, b;
int prv = -1;
bool f = 0;
int s[k] = {0, 0, 1, 0, 1, 1};
vi t;

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

int Move(vi v){
	if(a > 2){
		if(~prv) v[prv]++;
		for(int i = 0; i < 3; i++){
			if(v[i] && v[(i + 1) % 3]) return prv = i;
		}
		for(int i = 0; i < 3; i++){
			if(v[i]) return prv = i;
		}
	}else{
		if(f){
			if(v[0] + v[1] > 1) v[prv]++;
			return prv = (v[0] == 1) ^ 1;
		}
		if(!~prv){
			if(v[0] + v[1] != 2){
				f = 1;
				return prv = (v[0] == 1) ^ 1; 
			}
			prv = (v[0] > 0) ^ 1;
			t.push_back((v[0] > 1) ^ 1);
			t.push_back(prv);
			return prv;
		}
		if(v[0] + v[1] == 0){
			f = 1;
			return -1;
		}
		if(v[0] + v[1] > 1){
			f = 1;
			return !v[prv] ? -1 : prv ^= 1;
		}
		t.push_back((v[0] == 1) ^ 1);
		if(t.size() == k - 1){
			for(int i = 0; i < k; i++){
				f = 1;
				for(int j = 0; j < k - 1; j++) f &= s[(i + j) % k] == t[j];
				if(f) return -1;
			}
			f = 1;
		}
		return prv = (v[0] == 1) ^ 1;
	}
	return -2;
}

• 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