Submission #758979

#	Time	Username	Problem	Language	Result	Execution time	Memory
758979		siewjh	Stray Cat (JOI20_stray)	C++17	20 / 100	35 ms	16968 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
	const int MAXN = 20005;
	vector<pair<int, int>> adj[MAXN];
	vector<int> marking;
	int cyc[6] = {0, 0, 1, 0, 1, 1};
	
	void dfs(int x, int par, int cind){
		if (par != -1 && adj[x].size() >= 3){
			int prv = cyc[(cind + 5) % 6];
			if (prv == 0) cind = 5;
			else cind = 0;
		}
		for (auto nxt : adj[x]){
			int nn = nxt.first, edge = nxt.second;
			if (nn == par) continue;
			marking[edge] = cyc[cind];
			dfs(nn, x, (cind + 1) % 6);
		}
	}
}

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
	for (int i = 0; i < M; i++){
		adj[U[i]].push_back({V[i], i});
		adj[V[i]].push_back({U[i], i});
	}
	marking.resize(M);
	if (A >= 3){
		vector<int> dist(N, -1);
		dist[0] = 0;
		queue<int> q;
		q.push(0);
		while (!q.empty()){
			int x = q.front(); q.pop();
			for (auto nxt : adj[x]){
				int nn = nxt.first, edge = nxt.second;
				if (dist[nn] != -1){
					if (dist[nn] == dist[x] - 1) continue; // already marked
					else marking[edge] = dist[x] % 3;
				}
				else{
					marking[edge] = dist[x] % 3;
					dist[nn] = dist[x] + 1;
					q.push(nn);
				}
			}
		}
	}
	else{
		dfs(0, -1, 0);
	}
	return marking;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
	int A, B;
	int steps = 0; // 0 to 3 -> first steps, -1 -> straight up
	int prv = -1; // previous edge
	int seq = 0; // 5 digit sequence
	set<int> ok;
}

void Init(int A, int B) {
	::A = A;
	::B = B;
	// up: 11010, 10100, 01001, 10011, 00110, 01101
	ok = {26, 20, 9, 19, 6, 13};
}

int Move(vector<int> y){
	if (A >= 3){
		int types = 0;
		for (int i = 0; i < 3; i++)
			if (y[i])
				types++;
		if (types == 1){
			for (int i = 0; i < 3; i++)
				if (y[i])
					return i;
		}
		else{ // types == 2
			for (int i = 0; i < 3; i++)
				if (!y[i])
					return (i + 1) % 3;
		}
		return -1; // will never happen
	}
	else{
		if (y[0] == 0 && y[1] == 0){ // dead end
			steps = -1; // prv unchanged
			return -1;
		}
		else if (y[0] + y[1] + (prv != -1) >= 3){ // deg >= 3
			steps = -1;
			int y0 = y[0] + (prv == 0), y1 = y[1] + (prv == 1);
			if (y0 == 1){
				int ret = ((prv == 0) ? -1 : 0);
				prv = 0;
				return ret;
			}
			else{
				int ret = ((prv == 1) ? -1 : 1);
				prv = 1;
				return ret;
			}
		}
		else if (steps == -1){ // go up
			if (y[0]) return prv = 0;
			else return prv = 1;
		}
		else if (steps == 0){
			int go, other;
			if (y[0]){
				go = 0;
				if (y[1]) other = 1; else other = 0;
			}
			else go = other = 1;
			prv = go;
			seq = (other << 1) + go;
			return go;
		}
		else if (steps < 3){
			int go;
			if (y[0]) go = 0; else go = 1;
			prv = go;
			seq = (seq << 1) + go;
			return go;
		}
		else{ // see if we are going correct direction
			int nxt;
			if (y[0]) nxt = 0; else nxt = 1;
			seq = (seq << 1) + nxt;
			steps = -1;
			if (ok.count(seq)){ // continue
				return prv = nxt;
			}
			else return -1;
		}
	}
}

Compilation message (stderr)

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:45:32: warning: unused variable 'y1' [-Wunused-variable]
   45 |    int y0 = y[0] + (prv == 0), y1 = y[1] + (prv == 1);
      |                                ^~

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