oj.uz

Submission #445222

# Submission time Handle Problem Language Result Execution time Memory
445222 2021-07-16T23:19:01 Z flappybird Stray Cat (JOI20_stray) C++14
96 / 100
 63 ms 21012 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define MAX 101010

namespace {
	vector<ll> adj[MAX], num[MAX], depth, deg, arr;
	vector<ll> ret;
	ll asdf[6] = { 1, 1, 0, 1, 0, 0 };
	void dfs(ll x = 0, ll p = -1, ll d = 1, ll str = 0, ll chk = 0) {
		depth[x] = d;
		ll i;
		for (i = 0; i < (int)adj[x].size(); i++) {
			if (adj[x][i] == p) continue;
			if (deg[adj[x][i]] == 2) {
				if (!chk) {
					while (d != asdf[str % 6]) str++;
				}
				ret[num[x][i]] = asdf[str % 6];
				dfs(adj[x][i], x, !asdf[str % 6], str + 1, 1);
			}
			else {
				ret[num[x][i]] = d;
				dfs(adj[x][i], x, !d);
			}
		}
	}
	void bfs() {
		queue<pair<ll, ll>> q;
		q.push({ 0, 0 });
		while (!q.empty()) {
			pair<ll, ll> t;
			t = q.front();
			q.pop();
			ll v = t.first;
			if (arr[v] != -1) continue;
			arr[v] = t.second;
			for (auto x : adj[v]) {
				q.push({ x, (t.second + 1) % 3 });
			}
		}
	}
}  // namespace

std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
	if (A == 3) {
		ll i;
		for (i = 0; i < M; i++) adj[U[i]].push_back(V[i]);
		for (i = 0; i < M; i++) num[U[i]].push_back(i);
		for (i = 0; i < M; i++) adj[V[i]].push_back(U[i]);
		for (i = 0; i < M; i++) num[V[i]].push_back(i);
		ret.resize(M);
		arr.resize(N);
		for (i = 0; i < M; i++) ret[i] = -1;
		for (i = 0; i < N; i++) arr[i] = -1;
		bfs();
		for (i = 0; i < M; i++) {
			if (arr[U[i]] == arr[V[i]]) ret[i] = arr[U[i]];
			else {
				ll u, v;
				u = min(arr[U[i]], arr[V[i]]);
				v = max(arr[U[i]], arr[V[i]]);
				if (u == 0 && v == 1) ret[i] = 0;
				if (u == 1 && v == 2) ret[i] = 1;
				if (u == 0 && v == 2) ret[i] = 2;
			}
		}
		return ret;
	}
	ret.resize(M);
	deg.resize(N);
	ll i;
	for (i = 0; i < M; i++) adj[U[i]].push_back(V[i]);
	for (i = 0; i < M; i++) num[U[i]].push_back(i);
	for (i = 0; i < M; i++) adj[V[i]].push_back(U[i]);
	for (i = 0; i < M; i++) num[V[i]].push_back(i);
	for (i = 0; i < M; i++) deg[U[i]]++, deg[V[i]]++;
	depth.resize(N);
	dfs();
	return ret;
}

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

namespace {

int A, B;
int variable_example = 0;
ll pv;
ll str;
ll last;
string up[6], down[6];

bool chk(string s) {
	for (ll i = 0; i < 6; i++) {
		if (s == up[i]) return true;
	}
	return false;
}

string s;

}  // namespace

void Init(int A, int B) {
	::A = A;
	::B = B;
	pv = -1;
	str = 0;
	last = 0;
	up[0] = "00101";
	up[1] = "01011";
	up[2] = "10110";
	up[3] = "01100";
	up[4] = "11001";
	up[5] = "10010";
}

int Move(std::vector<int> y) {
	if (A == 3) {
		if (y[0] && y[1]) return 0;
		if (y[1] && y[2]) return 1;
		if (y[2] && y[0]) return 2;
		if (y[0]) return 0;
		if (y[1]) return 1;
		if (y[2]) return 2;
	}
	if (pv != -1) {
		if ((y[0] + y[1] + 1) != 2) {
			str = 0;
			s.clear();
			last = 1;
			y[pv]++;
			if (y[0] == 1) {
				if (pv == 0) return -1;
				else return pv = 0;
			}
			else {
				if (pv == 1) return -1;
				else return pv = 1;
			}
		}
		else {
			if (!last) {
				str++;
				ll nxt;
				if (y[0]) nxt = 0;
				else nxt = 1;
				s.push_back(nxt + 48);
				if (str == 5) {
					if (chk(s)) {
						last = 1;
						str = 0;
						s.clear();
						return pv = nxt;
					}
					else {
						last = 1;
						str = 0;
						s.clear();
						return -1;
					}
				}
				else {
					return pv = nxt;
				}
			}
			else {
				if (!(y[0] + y[1])) return -1;
				if (y[0]) return pv = 0;
				else return pv = 1;
			}
		}
	}
	else {
		if ((y[0] + y[1]) != 2) {
			last = 1;
			if (!(y[0] + y[1])) return -1;
			if (y[0] == 1) return pv = 0;
			else return pv = 1;
		}
		else {
			if (y[0] == 2) {
				s.push_back('0');
				s.push_back('0');
				str += 2;
				return pv = 0;
			}
			else if (y[1] == 2) {
				s.push_back('1');
				s.push_back('1');
				str += 2;
				return pv = 1;
			}
			else {
				s.push_back('0');
				s.push_back('1');
				str += 2;
				return pv = 1;
			}
		}
	}
}

Compilation message

Catherine.cpp:9:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    9 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 2.0

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

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 17848 KB Output is correct
2 Correct 3 ms 5244 KB Output is correct
3 Correct 39 ms 17576 KB Output is correct
4 Correct 56 ms 19248 KB Output is correct
5 Correct 60 ms 19200 KB Output is correct
6 Correct 45 ms 17908 KB Output is correct
7 Correct 45 ms 17944 KB Output is correct
8 Correct 54 ms 18620 KB Output is correct
9 Correct 53 ms 18480 KB Output is correct
10 Correct 49 ms 18388 KB Output is correct
11 Correct 48 ms 18176 KB Output is correct
12 Correct 51 ms 18352 KB Output is correct
13 Correct 49 ms 18228 KB Output is correct
14 Correct 54 ms 18600 KB Output is correct
15 Correct 52 ms 18452 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 17848 KB Output is correct
2 Correct 3 ms 5244 KB Output is correct
3 Correct 39 ms 17576 KB Output is correct
4 Correct 56 ms 19248 KB Output is correct
5 Correct 60 ms 19200 KB Output is correct
6 Correct 45 ms 17908 KB Output is correct
7 Correct 45 ms 17944 KB Output is correct
8 Correct 54 ms 18620 KB Output is correct
9 Correct 53 ms 18480 KB Output is correct
10 Correct 49 ms 18388 KB Output is correct
11 Correct 48 ms 18176 KB Output is correct
12 Correct 51 ms 18352 KB Output is correct
13 Correct 49 ms 18228 KB Output is correct
14 Correct 54 ms 18600 KB Output is correct
15 Correct 52 ms 18452 KB Output is correct
16 Correct 40 ms 16304 KB Output is correct
17 Correct 40 ms 16256 KB Output is correct
18 Correct 46 ms 16228 KB Output is correct
19 Correct 41 ms 16216 KB Output is correct
20 Correct 51 ms 16800 KB Output is correct
21 Correct 47 ms 16620 KB Output is correct
22 Correct 52 ms 18712 KB Output is correct
23 Correct 44 ms 16324 KB Output is correct
24 Correct 44 ms 16352 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5544 KB Output is correct
2 Correct 3 ms 5232 KB Output is correct
3 Correct 4 ms 5620 KB Output is correct
4 Correct 4 ms 5620 KB Output is correct
5 Correct 4 ms 5624 KB Output is correct
6 Correct 4 ms 5620 KB Output is correct
7 Correct 4 ms 5620 KB Output is correct
8 Correct 4 ms 5628 KB Output is correct
9 Correct 4 ms 5620 KB Output is correct
10 Correct 4 ms 5620 KB Output is correct
11 Correct 4 ms 5624 KB Output is correct
12 Correct 5 ms 5628 KB Output is correct
13 Correct 4 ms 5624 KB Output is correct
14 Correct 4 ms 5616 KB Output is correct
15 Correct 4 ms 5612 KB Output is correct
16 Correct 4 ms 5624 KB Output is correct
17 Correct 4 ms 5616 KB Output is correct
18 Correct 5 ms 5620 KB Output is correct
19 Correct 4 ms 5620 KB Output is correct
20 Correct 4 ms 5624 KB Output is correct
21 Correct 4 ms 5628 KB Output is correct
22 Correct 4 ms 5620 KB Output is correct
23 Correct 4 ms 5620 KB Output is correct
24 Correct 4 ms 5620 KB Output is correct
25 Correct 5 ms 5620 KB Output is correct
26 Correct 4 ms 5620 KB Output is correct
27 Correct 4 ms 5620 KB Output is correct
28 Correct 5 ms 5564 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16092 KB Output is correct
2 Correct 48 ms 17464 KB Output is correct
3 Correct 4 ms 5232 KB Output is correct
4 Correct 39 ms 16064 KB Output is correct
5 Correct 62 ms 18952 KB Output is correct
6 Correct 54 ms 18948 KB Output is correct
7 Correct 47 ms 17936 KB Output is correct
8 Correct 46 ms 17944 KB Output is correct
9 Correct 55 ms 18824 KB Output is correct
10 Correct 54 ms 18892 KB Output is correct
11 Correct 53 ms 18840 KB Output is correct
12 Correct 55 ms 18892 KB Output is correct
13 Correct 56 ms 18864 KB Output is correct
14 Correct 53 ms 18848 KB Output is correct
15 Correct 53 ms 18808 KB Output is correct
16 Correct 52 ms 18840 KB Output is correct
17 Correct 53 ms 18572 KB Output is correct
18 Correct 51 ms 18584 KB Output is correct
19 Correct 53 ms 18536 KB Output is correct
20 Correct 53 ms 18608 KB Output is correct
21 Correct 52 ms 18556 KB Output is correct
22 Correct 52 ms 18632 KB Output is correct
23 Correct 41 ms 16152 KB Output is correct
24 Correct 43 ms 16112 KB Output is correct
25 Correct 45 ms 16644 KB Output is correct
26 Correct 45 ms 16656 KB Output is correct
27 Correct 52 ms 17604 KB Output is correct
28 Correct 50 ms 17436 KB Output is correct
29 Correct 49 ms 17536 KB Output is correct
30 Correct 49 ms 17644 KB Output is correct
31 Correct 44 ms 16196 KB Output is correct
32 Correct 44 ms 16192 KB Output is correct
33 Correct 44 ms 16536 KB Output is correct
34 Correct 41 ms 16564 KB Output is correct
35 Correct 49 ms 17384 KB Output is correct
36 Correct 48 ms 17420 KB Output is correct
37 Correct 48 ms 17320 KB Output is correct
38 Correct 48 ms 17364 KB Output is correct
39 Correct 48 ms 17420 KB Output is correct
40 Correct 48 ms 17392 KB Output is correct
41 Correct 49 ms 17920 KB Output is correct
42 Correct 50 ms 17984 KB Output is correct
43 Correct 49 ms 18052 KB Output is correct
44 Correct 50 ms 17984 KB Output is correct
45 Correct 51 ms 18028 KB Output is correct
46 Correct 53 ms 17972 KB Output is correct
47 Correct 48 ms 17192 KB Output is correct
48 Correct 51 ms 17224 KB Output is correct
49 Correct 50 ms 17112 KB Output is correct
50 Correct 51 ms 17164 KB Output is correct
51 Correct 46 ms 16444 KB Output is correct
52 Correct 45 ms 16316 KB Output is correct
53 Correct 45 ms 16352 KB Output is correct
54 Correct 45 ms 16412 KB Output is correct
55 Correct 44 ms 16480 KB Output is correct
56 Correct 46 ms 16424 KB Output is correct
57 Correct 44 ms 16520 KB Output is correct
58 Correct 47 ms 16560 KB Output is correct
59 Correct 44 ms 16476 KB Output is correct
60 Correct 43 ms 16408 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16236 KB Output is correct
2 Correct 48 ms 17228 KB Output is correct
3 Correct 3 ms 5236 KB Output is correct
4 Correct 38 ms 16080 KB Output is correct
5 Correct 55 ms 18868 KB Output is correct
6 Correct 55 ms 18760 KB Output is correct
7 Correct 45 ms 17936 KB Output is correct
8 Correct 46 ms 17984 KB Output is correct
9 Correct 54 ms 18884 KB Output is correct
10 Correct 54 ms 18832 KB Output is correct
11 Correct 55 ms 18868 KB Output is correct
12 Correct 54 ms 18916 KB Output is correct
13 Correct 54 ms 18888 KB Output is correct
14 Correct 52 ms 18844 KB Output is correct
15 Correct 53 ms 18916 KB Output is correct
16 Correct 55 ms 18828 KB Output is correct
17 Correct 51 ms 18560 KB Output is correct
18 Correct 57 ms 18568 KB Output is correct
19 Correct 56 ms 18580 KB Output is correct
20 Correct 63 ms 18596 KB Output is correct
21 Correct 50 ms 18588 KB Output is correct
22 Correct 51 ms 18664 KB Output is correct
23 Correct 45 ms 16204 KB Output is correct
24 Correct 41 ms 16216 KB Output is correct
25 Correct 47 ms 16752 KB Output is correct
26 Correct 49 ms 16676 KB Output is correct
27 Correct 52 ms 17500 KB Output is correct
28 Correct 49 ms 17444 KB Output is correct
29 Correct 54 ms 17592 KB Output is correct
30 Correct 50 ms 17536 KB Output is correct
31 Correct 41 ms 16144 KB Output is correct
32 Correct 43 ms 16244 KB Output is correct
33 Correct 48 ms 16760 KB Output is correct
34 Correct 44 ms 16628 KB Output is correct
35 Correct 48 ms 17304 KB Output is correct
36 Correct 48 ms 17452 KB Output is correct
37 Correct 47 ms 17296 KB Output is correct
38 Correct 49 ms 17304 KB Output is correct
39 Correct 51 ms 17344 KB Output is correct
40 Correct 50 ms 17292 KB Output is correct
41 Correct 51 ms 18152 KB Output is correct
42 Correct 52 ms 17964 KB Output is correct
43 Correct 51 ms 17960 KB Output is correct
44 Correct 54 ms 17940 KB Output is correct
45 Correct 60 ms 18264 KB Output is correct
46 Correct 53 ms 18268 KB Output is correct
47 Correct 46 ms 17224 KB Output is correct
48 Correct 49 ms 17076 KB Output is correct
49 Correct 46 ms 17116 KB Output is correct
50 Correct 48 ms 17244 KB Output is correct
51 Correct 45 ms 16408 KB Output is correct
52 Correct 44 ms 16596 KB Output is correct
53 Correct 43 ms 16452 KB Output is correct
54 Correct 45 ms 16504 KB Output is correct
55 Correct 46 ms 16468 KB Output is correct
56 Correct 43 ms 16408 KB Output is correct
57 Correct 48 ms 16536 KB Output is correct
58 Correct 47 ms 16564 KB Output is correct
59 Correct 43 ms 16376 KB Output is correct
60 Correct 48 ms 16392 KB Output is correct