oj.uz

Submission #445223

# Submission time Handle Problem Language Result Execution time Memory
445223 2021-07-16T23:20:45 Z flappybird Stray Cat (JOI20_stray) C++14
100 / 100
 65 ms 21772 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 != 2) {
		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 != 2) {
		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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 20240 KB Output is correct
2 Correct 3 ms 5244 KB Output is correct
3 Correct 44 ms 20296 KB Output is correct
4 Correct 60 ms 21772 KB Output is correct
5 Correct 60 ms 21756 KB Output is correct
6 Correct 48 ms 20460 KB Output is correct
7 Correct 47 ms 20532 KB Output is correct
8 Correct 54 ms 21208 KB Output is correct
9 Correct 54 ms 21228 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 20240 KB Output is correct
2 Correct 3 ms 5244 KB Output is correct
3 Correct 44 ms 20296 KB Output is correct
4 Correct 60 ms 21772 KB Output is correct
5 Correct 60 ms 21756 KB Output is correct
6 Correct 48 ms 20460 KB Output is correct
7 Correct 47 ms 20532 KB Output is correct
8 Correct 54 ms 21208 KB Output is correct
9 Correct 54 ms 21228 KB Output is correct
10 Correct 45 ms 18544 KB Output is correct
11 Correct 46 ms 18476 KB Output is correct
12 Correct 43 ms 18700 KB Output is correct
13 Correct 45 ms 18520 KB Output is correct
14 Correct 45 ms 18728 KB Output is correct
15 Correct 50 ms 18996 KB Output is correct
16 Correct 54 ms 21428 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 17828 KB Output is correct
2 Correct 3 ms 5224 KB Output is correct
3 Correct 39 ms 17576 KB Output is correct
4 Correct 62 ms 19264 KB Output is correct
5 Correct 61 ms 19176 KB Output is correct
6 Correct 50 ms 17964 KB Output is correct
7 Correct 45 ms 17964 KB Output is correct
8 Correct 54 ms 18524 KB Output is correct
9 Correct 55 ms 18496 KB Output is correct
10 Correct 49 ms 18208 KB Output is correct
11 Correct 52 ms 18360 KB Output is correct
12 Correct 51 ms 18236 KB Output is correct
13 Correct 50 ms 18264 KB Output is correct
14 Correct 53 ms 18584 KB Output is correct
15 Correct 54 ms 18572 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 17828 KB Output is correct
2 Correct 3 ms 5224 KB Output is correct
3 Correct 39 ms 17576 KB Output is correct
4 Correct 62 ms 19264 KB Output is correct
5 Correct 61 ms 19176 KB Output is correct
6 Correct 50 ms 17964 KB Output is correct
7 Correct 45 ms 17964 KB Output is correct
8 Correct 54 ms 18524 KB Output is correct
9 Correct 55 ms 18496 KB Output is correct
10 Correct 49 ms 18208 KB Output is correct
11 Correct 52 ms 18360 KB Output is correct
12 Correct 51 ms 18236 KB Output is correct
13 Correct 50 ms 18264 KB Output is correct
14 Correct 53 ms 18584 KB Output is correct
15 Correct 54 ms 18572 KB Output is correct
16 Correct 39 ms 16344 KB Output is correct
17 Correct 39 ms 16264 KB Output is correct
18 Correct 45 ms 16252 KB Output is correct
19 Correct 45 ms 16192 KB Output is correct
20 Correct 48 ms 16852 KB Output is correct
21 Correct 46 ms 16576 KB Output is correct
22 Correct 52 ms 18780 KB Output is correct
23 Correct 43 ms 16360 KB Output is correct
24 Correct 45 ms 16252 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5564 KB Output is correct
2 Correct 3 ms 5232 KB Output is correct
3 Correct 5 ms 5620 KB Output is correct
4 Correct 4 ms 5620 KB Output is correct
5 Correct 4 ms 5620 KB Output is correct
6 Correct 4 ms 5620 KB Output is correct
7 Correct 4 ms 5624 KB Output is correct
8 Correct 4 ms 5620 KB Output is correct
9 Correct 5 ms 5620 KB Output is correct
10 Correct 4 ms 5620 KB Output is correct
11 Correct 4 ms 5620 KB Output is correct
12 Correct 5 ms 5620 KB Output is correct
13 Correct 4 ms 5620 KB Output is correct
14 Correct 4 ms 5620 KB Output is correct
15 Correct 4 ms 5676 KB Output is correct
16 Correct 4 ms 5636 KB Output is correct
17 Correct 4 ms 5620 KB Output is correct
18 Correct 4 ms 5620 KB Output is correct
19 Correct 4 ms 5616 KB Output is correct
20 Correct 4 ms 5620 KB Output is correct
21 Correct 4 ms 5616 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 4 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 4 ms 5620 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16040 KB Output is correct
2 Correct 49 ms 17364 KB Output is correct
3 Correct 3 ms 5232 KB Output is correct
4 Correct 38 ms 16124 KB Output is correct
5 Correct 53 ms 18832 KB Output is correct
6 Correct 54 ms 18892 KB Output is correct
7 Correct 46 ms 17904 KB Output is correct
8 Correct 46 ms 18036 KB Output is correct
9 Correct 55 ms 18872 KB Output is correct
10 Correct 54 ms 18840 KB Output is correct
11 Correct 57 ms 18808 KB Output is correct
12 Correct 54 ms 18840 KB Output is correct
13 Correct 53 ms 18888 KB Output is correct
14 Correct 65 ms 18848 KB Output is correct
15 Correct 54 ms 18884 KB Output is correct
16 Correct 60 ms 18820 KB Output is correct
17 Correct 52 ms 18652 KB Output is correct
18 Correct 53 ms 18556 KB Output is correct
19 Correct 51 ms 18496 KB Output is correct
20 Correct 50 ms 18656 KB Output is correct
21 Correct 50 ms 18592 KB Output is correct
22 Correct 51 ms 18568 KB Output is correct
23 Correct 47 ms 16152 KB Output is correct
24 Correct 43 ms 16168 KB Output is correct
25 Correct 45 ms 16696 KB Output is correct
26 Correct 46 ms 16664 KB Output is correct
27 Correct 48 ms 17596 KB Output is correct
28 Correct 48 ms 17540 KB Output is correct
29 Correct 52 ms 17468 KB Output is correct
30 Correct 49 ms 17488 KB Output is correct
31 Correct 43 ms 16268 KB Output is correct
32 Correct 44 ms 16280 KB Output is correct
33 Correct 46 ms 16636 KB Output is correct
34 Correct 49 ms 16648 KB Output is correct
35 Correct 49 ms 17416 KB Output is correct
36 Correct 50 ms 17276 KB Output is correct
37 Correct 49 ms 17336 KB Output is correct
38 Correct 54 ms 17296 KB Output is correct
39 Correct 48 ms 17300 KB Output is correct
40 Correct 52 ms 17432 KB Output is correct
41 Correct 54 ms 17992 KB Output is correct
42 Correct 51 ms 17944 KB Output is correct
43 Correct 52 ms 18024 KB Output is correct
44 Correct 53 ms 17936 KB Output is correct
45 Correct 53 ms 17988 KB Output is correct
46 Correct 52 ms 18000 KB Output is correct
47 Correct 50 ms 17156 KB Output is correct
48 Correct 47 ms 17224 KB Output is correct
49 Correct 46 ms 17052 KB Output is correct
50 Correct 52 ms 17284 KB Output is correct
51 Correct 43 ms 16412 KB Output is correct
52 Correct 43 ms 16424 KB Output is correct
53 Correct 43 ms 16320 KB Output is correct
54 Correct 44 ms 16408 KB Output is correct
55 Correct 46 ms 16524 KB Output is correct
56 Correct 46 ms 16444 KB Output is correct
57 Correct 48 ms 16528 KB Output is correct
58 Correct 45 ms 16516 KB Output is correct
59 Correct 43 ms 16408 KB Output is correct
60 Correct 43 ms 16412 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16120 KB Output is correct
2 Correct 49 ms 17192 KB Output is correct
3 Correct 3 ms 5240 KB Output is correct
4 Correct 38 ms 16056 KB Output is correct
5 Correct 55 ms 18864 KB Output is correct
6 Correct 55 ms 18908 KB Output is correct
7 Correct 48 ms 18008 KB Output is correct
8 Correct 46 ms 17964 KB Output is correct
9 Correct 55 ms 18784 KB Output is correct
10 Correct 55 ms 18828 KB Output is correct
11 Correct 53 ms 18840 KB Output is correct
12 Correct 53 ms 18840 KB Output is correct
13 Correct 56 ms 18892 KB Output is correct
14 Correct 52 ms 18908 KB Output is correct
15 Correct 55 ms 18908 KB Output is correct
16 Correct 57 ms 18816 KB Output is correct
17 Correct 51 ms 18624 KB Output is correct
18 Correct 50 ms 18660 KB Output is correct
19 Correct 52 ms 18560 KB Output is correct
20 Correct 50 ms 18580 KB Output is correct
21 Correct 49 ms 18528 KB Output is correct
22 Correct 54 ms 18644 KB Output is correct
23 Correct 45 ms 16096 KB Output is correct
24 Correct 41 ms 16240 KB Output is correct
25 Correct 45 ms 16628 KB Output is correct
26 Correct 44 ms 16684 KB Output is correct
27 Correct 52 ms 17452 KB Output is correct
28 Correct 51 ms 17512 KB Output is correct
29 Correct 55 ms 17556 KB Output is correct
30 Correct 50 ms 17600 KB Output is correct
31 Correct 43 ms 16124 KB Output is correct
32 Correct 43 ms 16200 KB Output is correct
33 Correct 43 ms 16660 KB Output is correct
34 Correct 44 ms 16648 KB Output is correct
35 Correct 47 ms 17460 KB Output is correct
36 Correct 48 ms 17324 KB Output is correct
37 Correct 47 ms 17268 KB Output is correct
38 Correct 50 ms 17328 KB Output is correct
39 Correct 50 ms 17392 KB Output is correct
40 Correct 49 ms 17356 KB Output is correct
41 Correct 50 ms 17920 KB Output is correct
42 Correct 51 ms 18056 KB Output is correct
43 Correct 54 ms 18048 KB Output is correct
44 Correct 51 ms 17968 KB Output is correct
45 Correct 53 ms 18104 KB Output is correct
46 Correct 51 ms 17924 KB Output is correct
47 Correct 48 ms 17144 KB Output is correct
48 Correct 49 ms 17256 KB Output is correct
49 Correct 48 ms 17048 KB Output is correct
50 Correct 49 ms 17196 KB Output is correct
51 Correct 45 ms 16416 KB Output is correct
52 Correct 44 ms 16452 KB Output is correct
53 Correct 46 ms 16480 KB Output is correct
54 Correct 44 ms 16396 KB Output is correct
55 Correct 44 ms 16464 KB Output is correct
56 Correct 46 ms 16392 KB Output is correct
57 Correct 43 ms 16488 KB Output is correct
58 Correct 43 ms 16444 KB Output is correct
59 Correct 44 ms 16380 KB Output is correct
60 Correct 44 ms 16400 KB Output is correct