Submission #895554

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
895554	2023-12-30T08:58:29 Z	marvinthang	Navigation 2 (JOI21_navigation2)	C++17	85 / 100	536 ms	2704 KB

Anna
Bruno

/*************************************
*    author: marvinthang             *
*    created: 30.12.2023 10:47:39    *
*************************************/

#include "Anna.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 << '}'; }

// end of template

void Anna(int N, int K, vector <int> R, vector <int> C) {
	auto get_idx = [&] (int x, int y, int i) {
		x -= R[i]; y -= C[i];
		if (y < -1) return 2;
		if (y > +1) return 3;
		if (x < -1) return 4;
		if (x > +1) return 5;
		++x; ++y;
		return x * 3 + y + 6;
	};
	vector <vector <int>> board(N, vector<int>(N));
	auto check = [&] (int pos) {
		int px = pos / 3, py = pos % 3;
		REP(x, N) REP(y, N) {
			int id = (x + px) % 3 * 3 + (y + py) % 3;
			if (id < K) {
				board[x][y] = get_idx(x, y, id);
				if (board[x][y] == 14) return false;
			} else if (id == K) board[x][y] = -1;
			else board[x][y] = 1;
		}
		return true;
	};
	REP(pos, 9) if (check(pos)) {
		vector <bool> used(14);
		REP(i, N) REP(j, N) if (board[i][j] >= 0) used[board[i][j]] = true;
		int mi = find(1 + ALL(used), false) - used.begin();
		REP(i, N) REP(j, N) {
			if (board[i][j] == -1) board[i][j] = mi;
			else if (board[i][j] > mi) --board[i][j];
			SetFlag(i, j, board[i][j]);
		}
		return;
	}
}

/*************************************
*    author: marvinthang             *
*    created: 30.12.2023 11:08:47    *
*************************************/

#include "Bruno.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 << '}'; }

// end of template


vector <int> Bruno(int K, vector <int> value) {
	int pos = find(ALL(value), 1) - value.begin();
	int nxt = pos / 3 * 3 + (pos % 3 + 1) % 3;
	if (value[nxt] == 1) pos = nxt;
	int px = (pos / 3 + 1) % 3, py = (pos % 3 + 1) % 3;
	int mi = -1;
	REP(i, 9) {
		int x = (i / 3 - px + 3) % 3, y = (i % 3 - py + 3) % 3;
		int id = x * 3 + y;
		if (id == K) mi = value[i];
	}
	REP(i, 9) if (value[i] >= mi) ++value[i];
	vector <int> res(K);
	REP(i, 9) {
		int x = (i / 3 - px + 3) % 3, y = (i % 3 - py + 3) % 3;
		int id = x * 3 + y;
		if (id < K) {
			if (value[i] < 6) res[id] = value[i] - 2;
			else {
				x = value[i] / 3 - i / 3 - 2; y = value[i] % 3 - i % 3;
				if (y) res[id] = y > 0;
				else if (x) res[id] = 2 + (x > 0);
				else res[id] = 4;
			}
		}
	}
	return res;
}

Subtask #1
85.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	8 ms	920 KB	Partially correct
2	Partially correct	6 ms	664 KB	Partially correct
3	Partially correct	8 ms	664 KB	Partially correct
4	Partially correct	8 ms	672 KB	Partially correct
5	Correct	8 ms	664 KB	Output is correct
6	Correct	9 ms	920 KB	Output is correct
7	Correct	9 ms	664 KB	Output is correct
8	Correct	9 ms	744 KB	Output is correct
9	Correct	8 ms	920 KB	Output is correct
10	Correct	7 ms	664 KB	Output is correct
11	Correct	8 ms	664 KB	Output is correct
12	Partially correct	9 ms	664 KB	Partially correct
13	Correct	8 ms	920 KB	Output is correct
14	Partially correct	9 ms	664 KB	Partially correct
15	Correct	9 ms	920 KB	Output is correct
16	Partially correct	7 ms	920 KB	Partially correct
17	Correct	7 ms	664 KB	Output is correct
18	Partially correct	9 ms	664 KB	Partially correct
19	Partially correct	7 ms	664 KB	Partially correct
20	Partially correct	7 ms	920 KB	Partially correct
21	Partially correct	9 ms	920 KB	Partially correct
22	Correct	9 ms	664 KB	Output is correct
23	Partially correct	8 ms	664 KB	Partially correct
24	Partially correct	7 ms	920 KB	Partially correct
25	Partially correct	8 ms	920 KB	Partially correct
26	Correct	9 ms	920 KB	Output is correct
27	Partially correct	9 ms	664 KB	Partially correct
28	Correct	8 ms	920 KB	Output is correct
29	Partially correct	9 ms	920 KB	Partially correct
30	Correct	9 ms	920 KB	Output is correct
31	Correct	9 ms	920 KB	Output is correct
32	Correct	7 ms	920 KB	Output is correct
33	Partially correct	8 ms	664 KB	Partially correct
34	Correct	7 ms	920 KB	Output is correct
35	Partially correct	9 ms	920 KB	Partially correct
36	Partially correct	11 ms	920 KB	Partially correct
37	Partially correct	8 ms	920 KB	Partially correct
38	Correct	9 ms	664 KB	Output is correct
39	Partially correct	8 ms	920 KB	Partially correct
40	Partially correct	8 ms	920 KB	Partially correct
41	Partially correct	7 ms	924 KB	Partially correct
42	Partially correct	8 ms	832 KB	Partially correct
43	Partially correct	10 ms	920 KB	Partially correct
44	Correct	7 ms	924 KB	Output is correct
45	Correct	8 ms	664 KB	Output is correct
46	Partially correct	10 ms	668 KB	Partially correct
47	Correct	8 ms	748 KB	Output is correct
48	Correct	10 ms	1176 KB	Output is correct
49	Correct	8 ms	920 KB	Output is correct
50	Correct	8 ms	920 KB	Output is correct
51	Correct	10 ms	664 KB	Output is correct
52	Correct	10 ms	920 KB	Output is correct
53	Partially correct	11 ms	664 KB	Partially correct
54	Partially correct	11 ms	920 KB	Partially correct
55	Correct	10 ms	664 KB	Output is correct
56	Partially correct	11 ms	664 KB	Partially correct
57	Partially correct	12 ms	664 KB	Partially correct
58	Partially correct	12 ms	1424 KB	Partially correct
59	Partially correct	12 ms	920 KB	Partially correct
60	Partially correct	12 ms	920 KB	Partially correct
61	Partially correct	11 ms	664 KB	Partially correct
62	Partially correct	9 ms	664 KB	Partially correct
63	Partially correct	11 ms	920 KB	Partially correct
64	Partially correct	9 ms	672 KB	Partially correct
65	Partially correct	10 ms	664 KB	Partially correct
66	Partially correct	11 ms	920 KB	Partially correct
67	Partially correct	10 ms	920 KB	Partially correct
68	Partially correct	12 ms	664 KB	Partially correct
69	Partially correct	9 ms	920 KB	Partially correct
70	Partially correct	12 ms	664 KB	Partially correct
71	Partially correct	13 ms	664 KB	Partially correct
72	Partially correct	11 ms	664 KB	Partially correct
73	Partially correct	11 ms	920 KB	Partially correct
74	Partially correct	12 ms	664 KB	Partially correct
75	Partially correct	14 ms	664 KB	Partially correct
76	Partially correct	10 ms	920 KB	Partially correct
77	Partially correct	11 ms	664 KB	Partially correct
78	Partially correct	11 ms	920 KB	Partially correct
79	Partially correct	12 ms	920 KB	Partially correct
80	Partially correct	13 ms	916 KB	Partially correct
81	Partially correct	10 ms	664 KB	Partially correct
82	Partially correct	11 ms	664 KB	Partially correct
83	Partially correct	10 ms	920 KB	Partially correct
84	Partially correct	10 ms	664 KB	Partially correct
85	Partially correct	11 ms	664 KB	Partially correct
86	Partially correct	12 ms	920 KB	Partially correct
87	Partially correct	11 ms	664 KB	Partially correct
88	Partially correct	11 ms	920 KB	Partially correct
89	Partially correct	10 ms	920 KB	Partially correct
90	Partially correct	10 ms	1088 KB	Partially correct
91	Partially correct	10 ms	920 KB	Partially correct
92	Partially correct	11 ms	920 KB	Partially correct
93	Partially correct	10 ms	920 KB	Partially correct
94	Partially correct	10 ms	920 KB	Partially correct
95	Partially correct	9 ms	744 KB	Partially correct
96	Partially correct	11 ms	916 KB	Partially correct
97	Partially correct	11 ms	920 KB	Partially correct
98	Partially correct	11 ms	664 KB	Partially correct
99	Partially correct	13 ms	920 KB	Partially correct
100	Partially correct	10 ms	664 KB	Partially correct
101	Partially correct	10 ms	664 KB	Partially correct
102	Partially correct	10 ms	664 KB	Partially correct
103	Partially correct	13 ms	920 KB	Partially correct
104	Partially correct	10 ms	920 KB	Partially correct
105	Partially correct	9 ms	920 KB	Partially correct
106	Partially correct	10 ms	920 KB	Partially correct
107	Partially correct	10 ms	920 KB	Partially correct
108	Partially correct	11 ms	664 KB	Partially correct
109	Partially correct	10 ms	664 KB	Partially correct
110	Partially correct	12 ms	920 KB	Partially correct
111	Partially correct	12 ms	920 KB	Partially correct
112	Partially correct	10 ms	920 KB	Partially correct
113	Partially correct	9 ms	664 KB	Partially correct
114	Partially correct	10 ms	664 KB	Partially correct
115	Partially correct	10 ms	920 KB	Partially correct
116	Partially correct	10 ms	920 KB	Partially correct
117	Partially correct	12 ms	920 KB	Partially correct
118	Partially correct	13 ms	920 KB	Partially correct
119	Partially correct	11 ms	924 KB	Partially correct
120	Partially correct	424 ms	1688 KB	Partially correct
121	Partially correct	436 ms	1792 KB	Partially correct
122	Partially correct	444 ms	1892 KB	Partially correct
123	Partially correct	519 ms	1756 KB	Partially correct
124	Partially correct	444 ms	2484 KB	Partially correct
125	Partially correct	476 ms	1632 KB	Partially correct
126	Partially correct	492 ms	1672 KB	Partially correct
127	Partially correct	437 ms	1640 KB	Partially correct
128	Partially correct	425 ms	1456 KB	Partially correct
129	Partially correct	462 ms	1152 KB	Partially correct
130	Partially correct	447 ms	1776 KB	Partially correct
131	Partially correct	464 ms	1760 KB	Partially correct
132	Partially correct	429 ms	1648 KB	Partially correct
133	Partially correct	454 ms	2060 KB	Partially correct
134	Partially correct	492 ms	2636 KB	Partially correct
135	Partially correct	473 ms	1936 KB	Partially correct
136	Partially correct	487 ms	1500 KB	Partially correct
137	Partially correct	469 ms	1228 KB	Partially correct
138	Partially correct	489 ms	1488 KB	Partially correct
139	Partially correct	502 ms	1728 KB	Partially correct
140	Partially correct	492 ms	1584 KB	Partially correct
141	Partially correct	486 ms	1800 KB	Partially correct
142	Partially correct	484 ms	1792 KB	Partially correct
143	Partially correct	501 ms	1452 KB	Partially correct
144	Partially correct	470 ms	1428 KB	Partially correct
145	Partially correct	504 ms	1904 KB	Partially correct
146	Partially correct	469 ms	1872 KB	Partially correct
147	Partially correct	450 ms	2052 KB	Partially correct
148	Partially correct	438 ms	1428 KB	Partially correct
149	Partially correct	491 ms	1768 KB	Partially correct
150	Partially correct	484 ms	1656 KB	Partially correct
151	Partially correct	447 ms	1520 KB	Partially correct
152	Partially correct	500 ms	1424 KB	Partially correct
153	Partially correct	449 ms	1916 KB	Partially correct
154	Partially correct	445 ms	2256 KB	Partially correct
155	Partially correct	457 ms	2704 KB	Partially correct
156	Partially correct	474 ms	1840 KB	Partially correct
157	Partially correct	451 ms	2004 KB	Partially correct
158	Partially correct	462 ms	2092 KB	Partially correct
159	Partially correct	436 ms	1908 KB	Partially correct
160	Partially correct	424 ms	2072 KB	Partially correct
161	Partially correct	460 ms	2112 KB	Partially correct
162	Partially correct	422 ms	1940 KB	Partially correct
163	Partially correct	468 ms	1536 KB	Partially correct
164	Partially correct	441 ms	1952 KB	Partially correct
165	Partially correct	489 ms	1916 KB	Partially correct
166	Partially correct	484 ms	2052 KB	Partially correct
167	Partially correct	440 ms	1928 KB	Partially correct
168	Partially correct	432 ms	1344 KB	Partially correct
169	Partially correct	456 ms	2216 KB	Partially correct
170	Partially correct	464 ms	1988 KB	Partially correct
171	Partially correct	467 ms	1656 KB	Partially correct
172	Partially correct	533 ms	1692 KB	Partially correct
173	Partially correct	469 ms	1560 KB	Partially correct
174	Partially correct	462 ms	1628 KB	Partially correct
175	Partially correct	480 ms	1704 KB	Partially correct
176	Partially correct	440 ms	1344 KB	Partially correct
177	Partially correct	434 ms	2184 KB	Partially correct
178	Partially correct	491 ms	2196 KB	Partially correct
179	Partially correct	491 ms	1328 KB	Partially correct
180	Partially correct	433 ms	1712 KB	Partially correct
181	Partially correct	430 ms	1960 KB	Partially correct
182	Partially correct	451 ms	1736 KB	Partially correct
183	Partially correct	503 ms	1696 KB	Partially correct
184	Partially correct	509 ms	1168 KB	Partially correct
185	Partially correct	483 ms	1524 KB	Partially correct
186	Partially correct	483 ms	1588 KB	Partially correct
187	Partially correct	468 ms	1620 KB	Partially correct
188	Partially correct	475 ms	1692 KB	Partially correct
189	Partially correct	458 ms	1604 KB	Partially correct
190	Partially correct	470 ms	2076 KB	Partially correct
191	Partially correct	497 ms	1768 KB	Partially correct
192	Partially correct	496 ms	1768 KB	Partially correct
193	Partially correct	468 ms	1904 KB	Partially correct
194	Partially correct	536 ms	1668 KB	Partially correct
195	Partially correct	459 ms	1776 KB	Partially correct
196	Partially correct	488 ms	1736 KB	Partially correct
197	Partially correct	455 ms	1612 KB	Partially correct
198	Partially correct	482 ms	1696 KB	Partially correct
199	Partially correct	489 ms	2004 KB	Partially correct
200	Partially correct	515 ms	1940 KB	Partially correct
201	Partially correct	485 ms	1536 KB	Partially correct
202	Partially correct	499 ms	1648 KB	Partially correct
203	Partially correct	513 ms	1536 KB	Partially correct
204	Partially correct	502 ms	1664 KB	Partially correct
205	Partially correct	502 ms	1668 KB	Partially correct
206	Partially correct	473 ms	1884 KB	Partially correct
207	Partially correct	506 ms	1440 KB	Partially correct
208	Partially correct	506 ms	1408 KB	Partially correct
209	Partially correct	500 ms	1372 KB	Partially correct
210	Partially correct	371 ms	1716 KB	Partially correct
211	Partially correct	353 ms	1552 KB	Partially correct
212	Partially correct	352 ms	1448 KB	Partially correct
213	Partially correct	390 ms	1624 KB	Partially correct
214	Partially correct	394 ms	2100 KB	Partially correct
215	Partially correct	388 ms	1652 KB	Partially correct
216	Partially correct	366 ms	2104 KB	Partially correct
217	Partially correct	413 ms	2020 KB	Partially correct
218	Partially correct	350 ms	1736 KB	Partially correct
219	Partially correct	385 ms	1876 KB	Partially correct
220	Partially correct	370 ms	1656 KB	Partially correct
221	Partially correct	350 ms	1832 KB	Partially correct
222	Partially correct	380 ms	1712 KB	Partially correct
223	Partially correct	378 ms	1796 KB	Partially correct
224	Partially correct	398 ms	1892 KB	Partially correct
225	Partially correct	376 ms	1768 KB	Partially correct
226	Partially correct	397 ms	2048 KB	Partially correct

Submission #895554

Compilation message

Subtask #1 85.0 / 100.0

Subtask #1
85.0 / 100.0