Submission #217573

#	Time	Username	Problem	Language	Result	Execution time	Memory
217573		Toadologist	Stray Cat (JOI20_stray)	C++14	100 / 100	76 ms	16964 KiB

Anthony

#include "Anthony.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }
template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}

namespace {
}  // namespace

std::vector<int> Mark(int n, int m, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
	std::vector<int> X(m);
	vector< vector<pii> > G(n, vector<pii>());
	
	for(int i = 0; i < m; ++i)
		G[U[i]].emplace_back(V[i], i),
		G[V[i]].emplace_back(U[i], i);
	
	vector<int> d(n, n + 1);
	d[0] = 0;
	queue<int> Q;
	Q.push(0);
	while(Q.size()) {
		int u = Q.front(); Q.pop();
		for(auto p : G[u]) 
			if(chmin(d[p.first], d[u] + 1))
				Q.push(p.first);
	}
	
	if(A >= 3) {
		for(int i = 0; i < m; ++i) {
			X[i] = min(d[U[i]], d[V[i]]) % 3;
		}
	} else {
		assert(A == 2);
		assert(m == n - 1);
		
		string eigen = "001011";
		function<void(int, int, int, int)> color = [&](int u, int fa, int col, int i) {
			int des = G[u].size() - !!(fa != -1);
			
			int ncol = col, ni = i;
			if(des >= 2) {
				ncol = col ^ 1;
				if(ncol == 0) ni = 0; else ni = 2;
			} else {
				ni = (i + 1) % 6;
				ncol = eigen[ni] - '0';
			}
			
			for(auto p : G[u]) if(p.first != fa) {
				X[p.second] = ncol;
				color(p.first, u, ncol, ni);
			}
		};
		
		color(0, -1, 0, -1);
		
	}
	displayv(X);
	return X;
}

Catherine

#include "Catherine.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }
template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}

using bs = basic_string<int>;

namespace {

int A, B;
int step = 0;
bs p;

int stable = 0;
string s;
string far = "001011001011";
string near = "110100110100";

}  // namespace

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

int Move(std::vector<int> y) {
	displayv(y);
	++step;
	if(A >= 3) {
		if(p.size()) y[p.back()]++;
		displayv(y);
		int ch = -1;
		
		if(y[0] && !y[2]) ch = 0;
		else if(y[1] && !y[0]) ch = 1;
		else if(y[2] && !y[1]) ch = 2;
		else assert(false);
		p.push_back(ch);
		return ch;
	} else {
		assert(A == 2);
		if(s.size()) y[s.back() - '0']++;
		
		int ch = -1;
		
		if(y[0] + y[1] == 1) {
			if(y[0]) ch = 0; else ch = 1;
			
			stable = true;
			s.push_back('0' + ch);
			if(s.size() > 1) ch = -1;
		} else if(y[0] + y[1] >= 3) {
			if(y[0] == 1) ch = 0;
			else if(y[1] == 1) ch = 1;
			else assert(false);
			
			stable = true;
			s.push_back('0' + ch);
			if(s.size() >= 2 && ch == s[s.size() - 2] - '0') ch = -1;
		} else { // on a chain
			if(s.size()) y[s.back() - '0']--;
			if(stable) {
				if(y[0]) ch = 0; else ch = 1;
				s.push_back('0' + ch);
			} else if(step == 1) {
				if(y[0]) ch = 0;
				else ch = 1;
				y[ch]--;
				if(y[0]) s.push_back('0');
				else s.push_back('1');
				s.push_back('0' + ch);
			} else {
				if(y[0]) ch = 0;
				else ch = 1;
				s.push_back('0' + ch);
				
				if(near.find(s) != string::npos && far.find(s) == string::npos)
					stable = true;
				else if(near.find(s) == string::npos && far.find(s) != string::npos) {
					eprintf("turn around\n");
					s.push_back(s[s.size() - 2]);
					ch = -1;
					stable = true;
				}
				
			}
		}
		display(ch);
		display(stable);
		return ch;
	}
}

• 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