oj.uz

Submission #883795

# Submission time Handle Problem Language Result Execution time Memory
883795 2023-12-06T04:20:47 Z marvinthang Stray Cat (JOI20_stray) C++17
91 / 100
 37 ms 16296 KB 
/*************************************
*    author: marvinthang             *
*    created: 06.12.2023 09:33:05    *
*************************************/

#include "Anthony.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

namespace {

}

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
	vector <vector <int>> adj(N);
	REP(i, M) {
		adj[U[i]].push_back(i);
		adj[V[i]].push_back(i);
	}
	vector <int> res(M);
	if (A >= 3) {
		queue <int> q;
		q.push(0);
		vector <int> dist(N, -1);
		dist[0] = 0;
		while (!q.empty()){
			int u = q.front(); q.pop();
			for (int i: adj[u]) {
				int v = U[i] ^ V[i] ^ u;
				if (dist[v] == -1) {
					dist[v] = dist[u] + 1;
					q.push(v);
				}
				if (dist[v] == dist[u] + 1) res[i] = dist[v] % 3;
				else if (dist[v] == dist[u]) res[i] = (dist[u] + 1) % 3;
			}
		}
	} else {
		int pattern = 11; // 001011
		int pos_0 = __builtin_ctz(pattern + 1);
		int pos_1 = __builtin_ctz(pattern);
		function<void(int, int, int)> dfs = [&] (int u, int par, int t) {
			if (adj[u].size() >= 3) {
				if (t >= 0) {
					t = (t + 5) % 6;
					if (BIT(pattern, t)) t = -1;
					else t = -2;
				}
				if (t >= 0) t = -1;
				for (int i: adj[u]) {
					int v = U[i] ^ V[i] ^ u;
					if (v == par) {
						assert(res[i] == !(-1 - t));
						continue;
					}
					res[i] = -1 - t;
					dfs(v, u, -3 - t);
				}
			} else {
				if (t < 0) {
					if (t == -1) t = pos_0;
					else t = pos_1;
				}
				for (int i: adj[u]) {
					int v = U[i] ^ V[i] ^ u;
					if (v == par) continue;
					res[i] = BIT(pattern, t);
					dfs(v, u, (t + 1) % 6);
				}
			}
		};
		dfs(0, 0, 0);
	}
	return res;
}

#include "Catherine.h"
/*************************************
*    author: marvinthang             *
*    created: 06.12.2023 09:38:51    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

namespace {
	int A, cur_mask, len, last;
	set <int> exist[7];
}

void Init(int A, int B) {
	::A = A;
	vector <int> pattern {0, 0, 1, 0, 1, 1};
	pattern.insert(pattern.end(), ALL(pattern));
	exist[0].insert(0);
	REP(i, 6) {
		int mask = 0;
		REP(j, 6) {
			mask = mask << 1 | pattern[i + j];
			exist[j + 1].insert(mask);
		}
	}
	cur_mask = len = 0;
	last = -1;
}

int Move(vector<int> y) {
	if (A >= 3) {
		REP(i, 3) if (y[i] && !y[(i + 2) % 3]) return i;
	} else {
		if (y[0] + y[1] + (last >= 0) >= 3) {
			len = 6;
			if (!y[0] || !y[1]) return -1;
			if (last == -1) return last = y[1] == 1;
			return last = !last;
		}
		if (y[0] + y[1] + (last >= 0) == 1) {
			len = 6;
			return last >= 0 ? -1 : last = y[1] == 1;
		}
		REP(i, 2) if (y[i]) {
			cur_mask = cur_mask << 1 | i;
			if (len < 6 && !exist[++len].count(cur_mask)) {
				len = 6;
				return -1;
			}
			return last = i;
		}
	}
}

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
   90 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15944 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 24 ms 14720 KB Output is correct
4 Correct 35 ms 16252 KB Output is correct
5 Correct 35 ms 16296 KB Output is correct
6 Correct 27 ms 14944 KB Output is correct
7 Correct 27 ms 15016 KB Output is correct
8 Correct 32 ms 15564 KB Output is correct
9 Correct 33 ms 15740 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15944 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 24 ms 14720 KB Output is correct
4 Correct 35 ms 16252 KB Output is correct
5 Correct 35 ms 16296 KB Output is correct
6 Correct 27 ms 14944 KB Output is correct
7 Correct 27 ms 15016 KB Output is correct
8 Correct 32 ms 15564 KB Output is correct
9 Correct 33 ms 15740 KB Output is correct
10 Correct 28 ms 13224 KB Output is correct
11 Correct 25 ms 13176 KB Output is correct
12 Correct 27 ms 12984 KB Output is correct
13 Correct 26 ms 12996 KB Output is correct
14 Correct 26 ms 13288 KB Output is correct
15 Correct 30 ms 13500 KB Output is correct
16 Correct 32 ms 15744 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 12640 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 23 ms 12416 KB Output is correct
4 Correct 32 ms 13980 KB Output is correct
5 Correct 33 ms 14204 KB Output is correct
6 Correct 27 ms 12964 KB Output is correct
7 Correct 27 ms 12732 KB Output is correct
8 Correct 32 ms 13424 KB Output is correct
9 Correct 37 ms 13432 KB Output is correct
10 Correct 27 ms 13188 KB Output is correct
11 Correct 28 ms 13188 KB Output is correct
12 Correct 30 ms 13440 KB Output is correct
13 Correct 28 ms 13180 KB Output is correct
14 Correct 33 ms 13864 KB Output is correct
15 Correct 31 ms 13464 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 12640 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 23 ms 12416 KB Output is correct
4 Correct 32 ms 13980 KB Output is correct
5 Correct 33 ms 14204 KB Output is correct
6 Correct 27 ms 12964 KB Output is correct
7 Correct 27 ms 12732 KB Output is correct
8 Correct 32 ms 13424 KB Output is correct
9 Correct 37 ms 13432 KB Output is correct
10 Correct 27 ms 13188 KB Output is correct
11 Correct 28 ms 13188 KB Output is correct
12 Correct 30 ms 13440 KB Output is correct
13 Correct 28 ms 13180 KB Output is correct
14 Correct 33 ms 13864 KB Output is correct
15 Correct 31 ms 13464 KB Output is correct
16 Correct 23 ms 11128 KB Output is correct
17 Correct 23 ms 11136 KB Output is correct
18 Correct 25 ms 10988 KB Output is correct
19 Correct 25 ms 10996 KB Output is correct
20 Correct 26 ms 11652 KB Output is correct
21 Correct 27 ms 11504 KB Output is correct
22 Correct 30 ms 13688 KB Output is correct
23 Correct 25 ms 11248 KB Output is correct
24 Correct 25 ms 11236 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1056 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 1 ms 1052 KB Output is correct
4 Correct 2 ms 1036 KB Output is correct
5 Correct 2 ms 1052 KB Output is correct
6 Correct 2 ms 1052 KB Output is correct
7 Correct 2 ms 1052 KB Output is correct
8 Correct 1 ms 1044 KB Output is correct
9 Correct 2 ms 1052 KB Output is correct
10 Correct 2 ms 1052 KB Output is correct
11 Correct 0 ms 1052 KB Output is correct
12 Correct 2 ms 1052 KB Output is correct
13 Correct 2 ms 1044 KB Output is correct
14 Correct 2 ms 1044 KB Output is correct
15 Correct 2 ms 1044 KB Output is correct
16 Correct 1 ms 1044 KB Output is correct
17 Correct 2 ms 1044 KB Output is correct
18 Correct 1 ms 1052 KB Output is correct
19 Correct 1 ms 1048 KB Output is correct
20 Correct 2 ms 1052 KB Output is correct
21 Correct 1 ms 1036 KB Output is correct
22 Correct 1 ms 1048 KB Output is correct
23 Correct 0 ms 1052 KB Output is correct
24 Correct 1 ms 1052 KB Output is correct
25 Correct 0 ms 1052 KB Output is correct
26 Correct 0 ms 1052 KB Output is correct
27 Correct 1 ms 1048 KB Output is correct
28 Correct 2 ms 1052 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 10880 KB Output is correct
2 Correct 27 ms 12464 KB Output is correct
3 Correct 0 ms 792 KB Output is correct
4 Correct 22 ms 10628 KB Output is correct
5 Correct 32 ms 14248 KB Output is correct
6 Correct 32 ms 14264 KB Output is correct
7 Correct 27 ms 13240 KB Output is correct
8 Correct 27 ms 13220 KB Output is correct
9 Correct 35 ms 14260 KB Output is correct
10 Correct 33 ms 14240 KB Output is correct
11 Correct 31 ms 14252 KB Output is correct
12 Correct 32 ms 14164 KB Output is correct
13 Correct 31 ms 14100 KB Output is correct
14 Correct 31 ms 14248 KB Output is correct
15 Correct 32 ms 14160 KB Output is correct
16 Correct 31 ms 14132 KB Output is correct
17 Correct 30 ms 14000 KB Output is correct
18 Correct 30 ms 13996 KB Output is correct
19 Correct 30 ms 13984 KB Output is correct
20 Correct 31 ms 13980 KB Output is correct
21 Correct 30 ms 13956 KB Output is correct
22 Correct 30 ms 13812 KB Output is correct
23 Correct 24 ms 10876 KB Output is correct
24 Correct 25 ms 11348 KB Output is correct
25 Correct 26 ms 12168 KB Output is correct
26 Correct 26 ms 11896 KB Output is correct
27 Correct 28 ms 13140 KB Output is correct
28 Correct 28 ms 13096 KB Output is correct
29 Correct 27 ms 12952 KB Output is correct
30 Correct 27 ms 13104 KB Output is correct
31 Correct 25 ms 11460 KB Output is correct
32 Correct 25 ms 11356 KB Output is correct
33 Correct 25 ms 11916 KB Output is correct
34 Correct 26 ms 11912 KB Output is correct
35 Correct 27 ms 12636 KB Output is correct
36 Correct 28 ms 12752 KB Output is correct
37 Correct 28 ms 12680 KB Output is correct
38 Correct 31 ms 12672 KB Output is correct
39 Correct 27 ms 12712 KB Output is correct
40 Correct 27 ms 12604 KB Output is correct
41 Correct 28 ms 13564 KB Output is correct
42 Correct 35 ms 13920 KB Output is correct
43 Correct 30 ms 13792 KB Output is correct
44 Correct 30 ms 13612 KB Output is correct
45 Correct 28 ms 13668 KB Output is correct
46 Correct 28 ms 13652 KB Output is correct
47 Correct 27 ms 12596 KB Output is correct
48 Correct 30 ms 12892 KB Output is correct
49 Correct 27 ms 12376 KB Output is correct
50 Correct 33 ms 12792 KB Output is correct
51 Correct 26 ms 11844 KB Output is correct
52 Correct 26 ms 11604 KB Output is correct
53 Correct 26 ms 11860 KB Output is correct
54 Correct 25 ms 11868 KB Output is correct
55 Correct 27 ms 11868 KB Output is correct
56 Correct 26 ms 11844 KB Output is correct
57 Correct 26 ms 11848 KB Output is correct
58 Correct 25 ms 11764 KB Output is correct
59 Correct 26 ms 11676 KB Output is correct
60 Correct 26 ms 11600 KB Output is correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 10884 KB Output is correct
2 Correct 27 ms 12168 KB Output is correct
3 Correct 0 ms 776 KB Output is correct
4 Correct 22 ms 10620 KB Output is correct
5 Correct 32 ms 14208 KB Output is correct
6 Correct 32 ms 14228 KB Output is correct
7 Incorrect 26 ms 13232 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -