Submission #446227

#	Time	Username	Problem	Language	Result	Execution time	Memory
446227		ics0503	Stray Cat (JOI20_stray)	C++17	100 / 100	62 ms	16552 KiB

Anthony

#include "Anthony.h"
#include <vector>
#include<algorithm>
#include<deque>
using namespace std;

// pattern: 110100110100

vector<pair<int,int>>edge[21212];
vector<int> X;
int st;
int pattern[6] = { 1,1,0,1,0,0 };
void dfs(int w, int bef,int befState) {
	if (bef == -1) {
		for (auto ne : edge[w]) {
			int nxt = ne.first;
			X[ne.second] = pattern[0];
			dfs(nxt, w, 0);
		}
		return;
	}
	if (edge[w].size() == 2) {
		for (auto ne : edge[w]) {
			int nxt = ne.first;
			if (nxt == bef)continue;
			int state = (befState + 1) % 6;
			X[ne.second] = pattern[state];
			dfs(nxt, w, state);
		}
	}
	else {
		for (auto ne : edge[w]) {
			int nxt = ne.first;
			if (nxt == bef)continue;
			int state = 0;
			if (pattern[befState] == 0) state = 0;
			else state = 2;
			X[ne.second] = pattern[state];
			dfs(nxt, w, state);
		}
	}
}

int dist[21212];
void bfs(int n) {
	deque<int>Q;
	Q.push_back(0);
	int i, j;
	for (i = 0; i < n; i++) dist[i] = n + 1;
	dist[0] = 0;
	while (!Q.empty()) {
		int now = Q.front(); Q.pop_front();
		for (auto ne : edge[now]) {
			int nxt = ne.first;
			if (dist[nxt] > dist[now] + 1) {
				dist[nxt] = dist[now] + 1;
				Q.push_back(nxt);
			}
		}
	}
}

vector<int> Mark(int n, int m, int a, int b, vector<int> U, vector<int> V) {
	int i, j;
	for (i = 0; i < m; i++)X.push_back(0);
	for (i = 0; i < m; i++) {
		int s = U[i], e = V[i];
		edge[s].push_back({ e,i }); edge[e].push_back({ s,i });
	}
	if (a == 2) {
		dfs(0, -1, 0);
	}
	else {
		bfs(n);
		for (i = 0; i < m; i++) {
			X[i] = min(dist[U[i]], dist[V[i]]) % 3;
		}
	}
	return X;
}

Catherine

#include "Catherine.h"
#include <vector>
#include<deque>
using namespace std;
int a, b;

deque<int>state;
int flag = 0, befSelection;
void Init(int A, int B) {
	a = A, b = B;
	state.clear();
	befSelection = -1;
	flag = 0;
}
/*
11010
10100
01001
10011
00110
01101
*/
int turnNum = 0;
int a2move(vector<int>&y) {
	if (flag == 2) {
		if (turnNum > 0) {
			turnNum--;
			return state[turnNum + 1];
		}
		else {
			flag = 1;
			befSelection = state[1];
		}
	}
	if (flag == 1) {
		if (y[0] + y[1] == 1) {
			if (y[0])return befSelection = 0;
			if (y[1])return befSelection = 1;
		}
		if (befSelection == 0)return befSelection = 1;
		return befSelection = 0;
	}
	if (state.empty()) {
		if (y[0] + y[1] >= 3) {
			if (y[0] == 1) {
				flag = 1;
				return befSelection = 0;
			}
			else {
				flag = 1;
				return befSelection = 1;
			}
		}
		if (y[0] && y[1]) { state.push_back(1); state.push_back(0); return befSelection = 0; }
		else {
			if (y[0] == 0 && y[1] == 1) {
				flag = 1;
				return befSelection = 1;
			}
			if (y[0] == 1 && y[1] == 0) {
				flag = 1;
				return befSelection = 0;
			}
			if (y[0]) {
				if (y[0] >= 2)state.push_back(0);
				state.push_back(0);
				return befSelection = 0;
			}
			else {
				if (y[1] >= 2)state.push_back(1);
				state.push_back(1);
				return befSelection = 1;
			}
		}
	}
	else {
		if (y[0] + y[1] == 0) {
			flag = 2;
			turnNum = state.size() - 1;
			turnNum--;
			return -1;
		}
		if (y[0] + y[1] >= 2) {
			flag = 1;
			if (y[0] == 0 && befSelection == 0) {
				flag = 2;
				turnNum = state.size()-1;
				turnNum--;
				return -1;
			}
			if (y[1] == 0 && befSelection == 1) {
				flag = 2;
				turnNum = state.size() - 1;
				turnNum--;
				return -1;
			}
			if (befSelection == 0)return befSelection = 1;
			else return befSelection = 0;
		}
		if (flag == 0 && state.size() == 4) {
			if (y[0]) state.push_back(0);
			if (y[1]) state.push_back(1);
			int allST[6][5] = {
					{1,1,0,1,0},
					{1,0,1,0,0},
					{0,1,0,0,1},
					{1,0,0,1,1},
					{0,0,1,1,0},
					{0,1,1,0,1},
			};
			int i, j;
			for (i = 0; i < 6; i++) {
				int qq = 1;
				for (j = 0; j < 5; j++) {
					if (allST[i][4-j] != state[j])qq = 0;
				}
				if (qq) {
					flag = 1;
					return befSelection = state[4];
				}
			}
			flag = 2;
			turnNum = 3;
			turnNum--;
			return -1;
		}
		if (y[0]) {
			state.push_back(0);
			return befSelection = 0;
		}
		else {
			state.push_back(1);
			return befSelection = 1;
		}
	}
}

int a3move(vector<int>y) {
	if(befSelection!=-1)y[befSelection]++;
	if (y[0] && y[1])return befSelection = 0;
	if (y[1] && y[2])return befSelection = 1;
	if (y[2] && y[0])return befSelection = 2;
	if (y[0])return befSelection = 0;
	if (y[1])return befSelection = 1;
	if (y[2])return befSelection = 2;
}

int Move(vector<int> y) {
	if (a == 2) return a2move(y);
	else return a3move(y);
}

Compilation message (stderr)

Anthony.cpp: In function 'void bfs(int)':
Anthony.cpp:48:9: warning: unused variable 'j' [-Wunused-variable]
   48 |  int i, j;
      |         ^
Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:64:9: warning: unused variable 'j' [-Wunused-variable]
   64 |  int i, j;
      |         ^

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

• 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