답안 #883789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883789	2023-12-06T03:51:50 Z	marvinthang	길고양이 (JOI20_stray)	C++17	20 / 100	47 ms	16396 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
		function<void(int, int, int)> dfs = [&] (int u, int par, int t) {
			if (adj[u].size() >= 3) {
				if (t >= 0) t = -1;
				for (int i: adj[u]) {
					int v = U[i] ^ V[i] ^ u;
					if (v == par) {
						res[i] = 2 + t;
						continue;
					}
					res[i] = -1 - t;
					dfs(v, u, -3 - t);
				}
			} else {
				t = max(t, 0);
				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	15236 KB	Output is correct
2	Correct	1 ms	792 KB	Output is correct
3	Correct	27 ms	14632 KB	Output is correct
4	Correct	47 ms	16396 KB	Output is correct
5	Correct	37 ms	16256 KB	Output is correct
6	Correct	27 ms	15024 KB	Output is correct
7	Correct	27 ms	15016 KB	Output is correct
8	Correct	32 ms	15764 KB	Output is correct
9	Correct	32 ms	15756 KB	Output is correct

Subtask #2

2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	15236 KB	Output is correct
2	Correct	1 ms	792 KB	Output is correct
3	Correct	27 ms	14632 KB	Output is correct
4	Correct	47 ms	16396 KB	Output is correct
5	Correct	37 ms	16256 KB	Output is correct
6	Correct	27 ms	15024 KB	Output is correct
7	Correct	27 ms	15016 KB	Output is correct
8	Correct	32 ms	15764 KB	Output is correct
9	Correct	32 ms	15756 KB	Output is correct
10	Correct	26 ms	13172 KB	Output is correct
11	Correct	26 ms	13192 KB	Output is correct
12	Correct	26 ms	13008 KB	Output is correct
13	Correct	25 ms	12968 KB	Output is correct
14	Correct	26 ms	13168 KB	Output is correct
15	Correct	27 ms	13544 KB	Output is correct
16	Correct	31 ms	15736 KB	Output is correct

Subtask #3

2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	12668 KB	Output is correct
2	Correct	0 ms	792 KB	Output is correct
3	Correct	23 ms	12348 KB	Output is correct
4	Correct	32 ms	14220 KB	Output is correct
5	Correct	32 ms	14112 KB	Output is correct
6	Correct	26 ms	12696 KB	Output is correct
7	Correct	31 ms	12620 KB	Output is correct
8	Correct	28 ms	13404 KB	Output is correct
9	Correct	34 ms	13504 KB	Output is correct
10	Correct	28 ms	13112 KB	Output is correct
11	Correct	28 ms	13196 KB	Output is correct
12	Correct	28 ms	13196 KB	Output is correct
13	Correct	27 ms	13176 KB	Output is correct
14	Correct	33 ms	13360 KB	Output is correct
15	Correct	33 ms	13456 KB	Output is correct

Subtask #4

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	12668 KB	Output is correct
2	Correct	0 ms	792 KB	Output is correct
3	Correct	23 ms	12348 KB	Output is correct
4	Correct	32 ms	14220 KB	Output is correct
5	Correct	32 ms	14112 KB	Output is correct
6	Correct	26 ms	12696 KB	Output is correct
7	Correct	31 ms	12620 KB	Output is correct
8	Correct	28 ms	13404 KB	Output is correct
9	Correct	34 ms	13504 KB	Output is correct
10	Correct	28 ms	13112 KB	Output is correct
11	Correct	28 ms	13196 KB	Output is correct
12	Correct	28 ms	13196 KB	Output is correct
13	Correct	27 ms	13176 KB	Output is correct
14	Correct	33 ms	13360 KB	Output is correct
15	Correct	33 ms	13456 KB	Output is correct
16	Correct	28 ms	11132 KB	Output is correct
17	Correct	30 ms	11128 KB	Output is correct
18	Correct	30 ms	11352 KB	Output is correct
19	Correct	25 ms	10984 KB	Output is correct
20	Correct	28 ms	11752 KB	Output is correct
21	Correct	26 ms	11484 KB	Output is correct
22	Correct	28 ms	13704 KB	Output is correct
23	Correct	26 ms	11244 KB	Output is correct
24	Correct	27 ms	11192 KB	Output is correct

Subtask #5

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1036 KB	Output is correct
2	Correct	0 ms	780 KB	Output is correct
3	Correct	1 ms	1052 KB	Output is correct
4	Correct	2 ms	1052 KB	Output is correct
5	Correct	2 ms	1056 KB	Output is correct
6	Correct	2 ms	1048 KB	Output is correct
7	Correct	2 ms	1052 KB	Output is correct
8	Correct	1 ms	1048 KB	Output is correct
9	Correct	1 ms	1052 KB	Output is correct
10	Correct	1 ms	1052 KB	Output is correct
11	Correct	0 ms	1036 KB	Output is correct
12	Correct	1 ms	1044 KB	Output is correct
13	Correct	1 ms	1548 KB	Output is correct
14	Correct	1 ms	1052 KB	Output is correct
15	Correct	2 ms	1048 KB	Output is correct
16	Correct	1 ms	1044 KB	Output is correct
17	Correct	1 ms	1052 KB	Output is correct
18	Correct	1 ms	1048 KB	Output is correct
19	Correct	2 ms	1048 KB	Output is correct
20	Correct	1 ms	1052 KB	Output is correct
21	Correct	2 ms	1304 KB	Output is correct
22	Correct	1 ms	1048 KB	Output is correct
23	Correct	2 ms	1056 KB	Output is correct
24	Correct	2 ms	1052 KB	Output is correct
25	Correct	1 ms	1052 KB	Output is correct
26	Correct	2 ms	1056 KB	Output is correct
27	Correct	2 ms	1052 KB	Output is correct
28	Correct	2 ms	1048 KB	Output is correct

Subtask #6

0 / 71.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	11128 KB	Output is correct
2	Correct	28 ms	12576 KB	Output is correct
3	Correct	0 ms	776 KB	Output is correct
4	Correct	20 ms	11056 KB	Output is correct
5	Correct	31 ms	14548 KB	Output is correct
6	Correct	30 ms	14780 KB	Output is correct
7	Correct	28 ms	13648 KB	Output is correct
8	Correct	26 ms	13716 KB	Output is correct
9	Correct	31 ms	14692 KB	Output is correct
10	Correct	34 ms	14584 KB	Output is correct
11	Correct	31 ms	14732 KB	Output is correct
12	Correct	31 ms	15196 KB	Output is correct
13	Correct	33 ms	14636 KB	Output is correct
14	Correct	35 ms	14588 KB	Output is correct
15	Correct	33 ms	14692 KB	Output is correct
16	Correct	39 ms	14668 KB	Output is correct
17	Correct	33 ms	14376 KB	Output is correct
18	Correct	28 ms	14480 KB	Output is correct
19	Correct	30 ms	14440 KB	Output is correct
20	Correct	31 ms	14328 KB	Output is correct
21	Correct	41 ms	14424 KB	Output is correct
22	Correct	35 ms	14572 KB	Output is correct
23	Incorrect	23 ms	11352 KB	Wrong Answer [6]
24	Halted	0 ms	0 KB	-

Subtask #7

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	10876 KB	Output is correct
2	Correct	26 ms	12176 KB	Output is correct
3	Correct	0 ms	796 KB	Output is correct
4	Correct	20 ms	11056 KB	Output is correct
5	Correct	33 ms	14700 KB	Output is correct
6	Correct	32 ms	14692 KB	Output is correct
7	Incorrect	26 ms	13640 KB	Wrong Answer [6]
8	Halted	0 ms	0 KB	-