oj.uz

Submission #217558

# Submission time Handle Problem Language Result Execution time Memory
217558 2020-03-30T09:05:22 Z Toadologist Stray Cat (JOI20_stray) C++14
0 / 100
 55 ms 15692 KB 
#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) i = 0; else i = 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;
}
#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[1]) ch = 0;
		else if(y[1] && y[2]) ch = 1;
		else if(y[2] && y[0]) 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() != 0) 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);
		} 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 15692 KB Output is correct
2 Runtime error 10 ms 1032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 15692 KB Output is correct
2 Runtime error 10 ms 1032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13268 KB Output is correct
2 Runtime error 10 ms 1032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13268 KB Output is correct
2 Runtime error 10 ms 1032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1096 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 11444 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 11472 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -