답안 #883795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883795	2023-12-06T04:20:47 Z	marvinthang	길고양이 (JOI20_stray)	C++17	91 / 100	37 ms	16296 KB

Anthony

/*************************************
*    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;
}

Catherine

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-