oj.uz

Submission #217562

# Submission time Handle Problem Language Result Execution time Memory
217562 2020-03-30T09:13:49 Z Toadologist Stray Cat (JOI20_stray) C++14
15 / 100
 66 ms 16860 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[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() != 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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 15740 KB Output is correct
2 Correct 9 ms 780 KB Output is correct
3 Correct 48 ms 15088 KB Output is correct
4 Correct 66 ms 16856 KB Output is correct
5 Correct 66 ms 16860 KB Output is correct
6 Correct 54 ms 15600 KB Output is correct
7 Correct 54 ms 15588 KB Output is correct
8 Correct 61 ms 16412 KB Output is correct
9 Correct 61 ms 16424 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 15740 KB Output is correct
2 Correct 9 ms 780 KB Output is correct
3 Correct 48 ms 15088 KB Output is correct
4 Correct 66 ms 16856 KB Output is correct
5 Correct 66 ms 16860 KB Output is correct
6 Correct 54 ms 15600 KB Output is correct
7 Correct 54 ms 15588 KB Output is correct
8 Correct 61 ms 16412 KB Output is correct
9 Correct 61 ms 16424 KB Output is correct
10 Correct 51 ms 13884 KB Output is correct
11 Correct 53 ms 13528 KB Output is correct
12 Correct 51 ms 13560 KB Output is correct
13 Correct 51 ms 13556 KB Output is correct
14 Correct 53 ms 13816 KB Output is correct
15 Correct 55 ms 14204 KB Output is correct
16 Correct 60 ms 16356 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13268 KB Output is correct
2 Correct 9 ms 904 KB Output is correct
3 Correct 45 ms 12956 KB Output is correct
4 Correct 63 ms 14692 KB Output is correct
5 Correct 64 ms 14668 KB Output is correct
6 Correct 52 ms 13292 KB Output is correct
7 Correct 53 ms 13532 KB Output is correct
8 Correct 66 ms 14232 KB Output is correct
9 Correct 59 ms 14108 KB Output is correct
10 Correct 62 ms 13780 KB Output is correct
11 Correct 57 ms 13792 KB Output is correct
12 Correct 55 ms 13856 KB Output is correct
13 Correct 56 ms 13824 KB Output is correct
14 Correct 61 ms 14100 KB Output is correct
15 Correct 62 ms 14156 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13268 KB Output is correct
2 Correct 9 ms 904 KB Output is correct
3 Correct 45 ms 12956 KB Output is correct
4 Correct 63 ms 14692 KB Output is correct
5 Correct 64 ms 14668 KB Output is correct
6 Correct 52 ms 13292 KB Output is correct
7 Correct 53 ms 13532 KB Output is correct
8 Correct 66 ms 14232 KB Output is correct
9 Correct 59 ms 14108 KB Output is correct
10 Correct 62 ms 13780 KB Output is correct
11 Correct 57 ms 13792 KB Output is correct
12 Correct 55 ms 13856 KB Output is correct
13 Correct 56 ms 13824 KB Output is correct
14 Correct 61 ms 14100 KB Output is correct
15 Correct 62 ms 14156 KB Output is correct
16 Correct 47 ms 11792 KB Output is correct
17 Correct 48 ms 11736 KB Output is correct
18 Correct 49 ms 11612 KB Output is correct
19 Correct 49 ms 11612 KB Output is correct
20 Correct 54 ms 12416 KB Output is correct
21 Correct 51 ms 12140 KB Output is correct
22 Correct 56 ms 14172 KB Output is correct
23 Correct 54 ms 11768 KB Output is correct
24 Correct 50 ms 11756 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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