Submission #564729

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
564729	2022-05-19T14:12:29 Z	DanShaders	Broken Device 2 (JOI22_device2)	C++17	100 / 100	216 ms	2988 KB

Anna
Bruno

//bs:sanitizers,flags:grader.cpp
#include "Anna.h"
#include "Bruno.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int LEN = 140, N = LEN + 1;

bool inited = false;
ll dp[N], tot[N];

int Declare() {
	if (inited) {
		return LEN;
	}
	inited = true;
	
	dp[1] = 1;
	for (int i = 3; i < N; ++i) {
		dp[i] = dp[i - 2] + dp[i - 3];
	}
	for (int i = 0; i < N; ++i) {
		tot[i] = accumulate(dp, dp + i + 1, 0ll);
	}
	return LEN;
}

pair<vector<int>, vector<int>> Anna(ll n) {
	bool parity = n & 1;
	n /= 2;

	int len2 = 0;
	while (n >= tot[len2]) {
		n -= tot[len2];
		++len2;
	}

	int len = 0;
	while (n >= dp[len]) {
		n -= dp[len];
		++len;
	}
	vector<int> u;
	while (len > 1) {
		if (n >= dp[len - 2]) {
			u.push_back(1);
			n -= dp[len - 2];
			len -= 3;
		} else {
			u.push_back(0);
			len -= 2;
		}
	}

	vector<int> s = {1};
	for (int i : u) {
		if (i) {
			s.push_back(s.back() ^ 1);
		}
		s.push_back(s.back());
		s.push_back(s.back());
	}

	while (sz(s) < len2) {
		s.push_back(s.back() ^ 1);
	}

	vector<int> t = {!parity};
	while (sz(t) != sz(s)) {
		t.push_back(t.back() ^ 1);
	}

	if (parity) {
		for (int &x : s) {
			x ^= 1;
		}
	}
	return {s, t};
}

vector<pair<int, int>> path;

#define TRY(x) do { if (x) { return true; }} while (false);

int n;
char d[2][N][N];

bool recover(const vector<int> &a, int i, int tlen, int cnt) {
	{
		int trem = n - tlen;
		int srem = n - i + tlen;
		if (trem < 0 || srem < 0) {
			return false;
		}
		int prv = sz(path) ? path.back().x : 1;
		if (!cnt && d[prv ^ (srem & 1)][trem][srem]) {
			return true;
		}
	}
	if (i > sz(a) || tlen > n) {
		return false;
	}

	if (a[i] != (tlen & 1)) {
		TRY(recover(a, i + 1, tlen + 1, cnt));
	}
	if (cnt) {
		if (path.back().x != a[i]) {
			return false;
		}
		TRY(recover(a, i + 1, tlen, cnt - 1));
	} else {
		int prv = 1;
		if (sz(path)) {
			prv = path.back().x;
		}
		path.push_back({a[i], a[i] != prv});
		TRY(recover(a, i + 1, tlen, a[i] == prv ? 1 : 2));
		path.pop_back();
	}
	return false;
}

ll Bruno(vector<int> a) {
	int parity = !a[0];
	if (parity) {
		for (int &x : a) {
			x ^= 1;
		}
	}
	Declare();
	n = sz(a) / 2;
	path.clear();
	
	fill_n(d[0][0], 2 * N * N, 0);
	d[0][0][0] = d[1][0][0] = 1;
	
	int o1 = n & 1;
	for (int o2 = 0; o2 < 2; ++o2) {
		for (int i = 0; i <= n; ++i) {
			for (int j = 0; j <= n; ++j) {
				if (i && ((i & 1) ^ o1) != a[sz(a) - i - j]) {
					d[o2][i][j] = d[o2][i - 1][j];
				}
				if (j && ((j & 1) ^ o2) != a[sz(a) - i - j]) {
					d[o2][i][j] |= d[o2][i][j - 1];
				}
			}
		}
	}
	if (!recover(a, 1, 0, 0)) {
		path.push_back({1, -1});
		assert(recover(a, 0, 0, 1));
		path.erase(path.begin());
	}

	int rlen = 1;
	for (auto u : path) {
		rlen += u.y + 2;
	}
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		ans += tot[i];
	}
	for (int i = 0; i < rlen; ++i) {
		ans += dp[i];
	}
	for (int i = 0; rlen > 1; ++i) {
		if (path[i].y) {
			ans += dp[rlen - 2];
			rlen -= 3;
		} else {
			rlen -= 2;
		}
	}
	return ans * 2 + parity;
}

//bs:sanitizers,flags:grader.cpp
#include "Anna.h"
#include "Bruno.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int LEN = 140, N = LEN + 1;

bool inited = false;
ll dp[N], tot[N];

int Declare() {
	if (inited) {
		return LEN;
	}
	inited = true;
	
	dp[1] = 1;
	for (int i = 3; i < N; ++i) {
		dp[i] = dp[i - 2] + dp[i - 3];
	}
	for (int i = 0; i < N; ++i) {
		tot[i] = accumulate(dp, dp + i + 1, 0ll);
	}
	return LEN;
}

pair<vector<int>, vector<int>> Anna(ll n) {
	bool parity = n & 1;
	n /= 2;

	int len2 = 0;
	while (n >= tot[len2]) {
		n -= tot[len2];
		++len2;
	}

	int len = 0;
	while (n >= dp[len]) {
		n -= dp[len];
		++len;
	}
	vector<int> u;
	while (len > 1) {
		if (n >= dp[len - 2]) {
			u.push_back(1);
			n -= dp[len - 2];
			len -= 3;
		} else {
			u.push_back(0);
			len -= 2;
		}
	}

	vector<int> s = {1};
	for (int i : u) {
		if (i) {
			s.push_back(s.back() ^ 1);
		}
		s.push_back(s.back());
		s.push_back(s.back());
	}

	while (sz(s) < len2) {
		s.push_back(s.back() ^ 1);
	}

	vector<int> t = {!parity};
	while (sz(t) != sz(s)) {
		t.push_back(t.back() ^ 1);
	}

	if (parity) {
		for (int &x : s) {
			x ^= 1;
		}
	}
	return {s, t};
}

vector<pair<int, int>> path;

#define TRY(x) do { if (x) { return true; }} while (false);

int n;
char d[2][N][N];

bool recover(const vector<int> &a, int i, int tlen, int cnt) {
	{
		int trem = n - tlen;
		int srem = n - i + tlen;
		if (trem < 0 || srem < 0) {
			return false;
		}
		int prv = sz(path) ? path.back().x : 1;
		if (!cnt && d[prv ^ (srem & 1)][trem][srem]) {
			return true;
		}
	}
	if (i > sz(a) || tlen > n) {
		return false;
	}

	if (a[i] != (tlen & 1)) {
		TRY(recover(a, i + 1, tlen + 1, cnt));
	}
	if (cnt) {
		if (path.back().x != a[i]) {
			return false;
		}
		TRY(recover(a, i + 1, tlen, cnt - 1));
	} else {
		int prv = 1;
		if (sz(path)) {
			prv = path.back().x;
		}
		path.push_back({a[i], a[i] != prv});
		TRY(recover(a, i + 1, tlen, a[i] == prv ? 1 : 2));
		path.pop_back();
	}
	return false;
}

ll Bruno(vector<int> a) {
	int parity = !a[0];
	if (parity) {
		for (int &x : a) {
			x ^= 1;
		}
	}
	Declare();
	n = sz(a) / 2;
	path.clear();
	
	fill_n(d[0][0], 2 * N * N, 0);
	d[0][0][0] = d[1][0][0] = 1;
	
	int o1 = n & 1;
	for (int o2 = 0; o2 < 2; ++o2) {
		for (int i = 0; i <= n; ++i) {
			for (int j = 0; j <= n; ++j) {
				if (i && ((i & 1) ^ o1) != a[sz(a) - i - j]) {
					d[o2][i][j] = d[o2][i - 1][j];
				}
				if (j && ((j & 1) ^ o2) != a[sz(a) - i - j]) {
					d[o2][i][j] |= d[o2][i][j - 1];
				}
			}
		}
	}
	if (!recover(a, 1, 0, 0)) {
		path.push_back({1, -1});
		assert(recover(a, 0, 0, 1));
		path.erase(path.begin());
	}

	int rlen = 1;
	for (auto u : path) {
		rlen += u.y + 2;
	}
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		ans += tot[i];
	}
	for (int i = 0; i < rlen; ++i) {
		ans += dp[i];
	}
	for (int i = 0; rlen > 1; ++i) {
		if (path[i].y) {
			ans += dp[rlen - 2];
			rlen -= 3;
		} else {
			rlen -= 2;
		}
	}
	return ans * 2 + parity;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	644 KB	Output is correct
2	Correct	17 ms	948 KB	Output is correct
3	Correct	20 ms	964 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	644 KB	Output is correct
2	Correct	17 ms	948 KB	Output is correct
3	Correct	20 ms	964 KB	Output is correct
4	Correct	46 ms	1408 KB	Output is correct
5	Correct	45 ms	1468 KB	Output is correct
6	Correct	45 ms	1392 KB	Output is correct
7	Correct	49 ms	1420 KB	Output is correct
8	Correct	46 ms	1436 KB	Output is correct
9	Correct	48 ms	1444 KB	Output is correct
10	Correct	41 ms	1460 KB	Output is correct

Subtask #3
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	644 KB	Output is correct
2	Correct	17 ms	948 KB	Output is correct
3	Correct	20 ms	964 KB	Output is correct
4	Correct	46 ms	1408 KB	Output is correct
5	Correct	45 ms	1468 KB	Output is correct
6	Correct	45 ms	1392 KB	Output is correct
7	Correct	49 ms	1420 KB	Output is correct
8	Correct	46 ms	1436 KB	Output is correct
9	Correct	48 ms	1444 KB	Output is correct
10	Correct	41 ms	1460 KB	Output is correct
11	Correct	50 ms	1456 KB	Output is correct
12	Correct	50 ms	1500 KB	Output is correct
13	Correct	51 ms	1424 KB	Output is correct
14	Correct	50 ms	1336 KB	Output is correct
15	Correct	50 ms	1544 KB	Output is correct
16	Correct	52 ms	1500 KB	Output is correct
17	Correct	46 ms	1532 KB	Output is correct
18	Correct	42 ms	1320 KB	Output is correct
19	Correct	44 ms	1408 KB	Output is correct
20	Correct	42 ms	1308 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	644 KB	Output is correct
2	Correct	17 ms	948 KB	Output is correct
3	Correct	20 ms	964 KB	Output is correct
4	Correct	46 ms	1408 KB	Output is correct
5	Correct	45 ms	1468 KB	Output is correct
6	Correct	45 ms	1392 KB	Output is correct
7	Correct	49 ms	1420 KB	Output is correct
8	Correct	46 ms	1436 KB	Output is correct
9	Correct	48 ms	1444 KB	Output is correct
10	Correct	41 ms	1460 KB	Output is correct
11	Correct	50 ms	1456 KB	Output is correct
12	Correct	50 ms	1500 KB	Output is correct
13	Correct	51 ms	1424 KB	Output is correct
14	Correct	50 ms	1336 KB	Output is correct
15	Correct	50 ms	1544 KB	Output is correct
16	Correct	52 ms	1500 KB	Output is correct
17	Correct	46 ms	1532 KB	Output is correct
18	Correct	42 ms	1320 KB	Output is correct
19	Correct	44 ms	1408 KB	Output is correct
20	Correct	42 ms	1308 KB	Output is correct
21	Correct	61 ms	1628 KB	Output is correct
22	Correct	61 ms	1608 KB	Output is correct
23	Correct	63 ms	1592 KB	Output is correct
24	Correct	61 ms	1628 KB	Output is correct
25	Correct	60 ms	1608 KB	Output is correct
26	Correct	61 ms	1660 KB	Output is correct
27	Correct	53 ms	1688 KB	Output is correct
28	Correct	52 ms	1384 KB	Output is correct
29	Correct	53 ms	1432 KB	Output is correct
30	Correct	53 ms	1452 KB	Output is correct

Subtask #5
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	644 KB	Output is correct
2	Correct	17 ms	948 KB	Output is correct
3	Correct	20 ms	964 KB	Output is correct
4	Correct	46 ms	1408 KB	Output is correct
5	Correct	45 ms	1468 KB	Output is correct
6	Correct	45 ms	1392 KB	Output is correct
7	Correct	49 ms	1420 KB	Output is correct
8	Correct	46 ms	1436 KB	Output is correct
9	Correct	48 ms	1444 KB	Output is correct
10	Correct	41 ms	1460 KB	Output is correct
11	Correct	50 ms	1456 KB	Output is correct
12	Correct	50 ms	1500 KB	Output is correct
13	Correct	51 ms	1424 KB	Output is correct
14	Correct	50 ms	1336 KB	Output is correct
15	Correct	50 ms	1544 KB	Output is correct
16	Correct	52 ms	1500 KB	Output is correct
17	Correct	46 ms	1532 KB	Output is correct
18	Correct	42 ms	1320 KB	Output is correct
19	Correct	44 ms	1408 KB	Output is correct
20	Correct	42 ms	1308 KB	Output is correct
21	Correct	61 ms	1628 KB	Output is correct
22	Correct	61 ms	1608 KB	Output is correct
23	Correct	63 ms	1592 KB	Output is correct
24	Correct	61 ms	1628 KB	Output is correct
25	Correct	60 ms	1608 KB	Output is correct
26	Correct	61 ms	1660 KB	Output is correct
27	Correct	53 ms	1688 KB	Output is correct
28	Correct	52 ms	1384 KB	Output is correct
29	Correct	53 ms	1432 KB	Output is correct
30	Correct	53 ms	1452 KB	Output is correct
31	Correct	95 ms	1936 KB	Output is correct
32	Correct	97 ms	1980 KB	Output is correct
33	Correct	98 ms	2004 KB	Output is correct
34	Correct	98 ms	2024 KB	Output is correct
35	Correct	94 ms	1840 KB	Output is correct
36	Correct	92 ms	1948 KB	Output is correct
37	Correct	86 ms	2000 KB	Output is correct
38	Correct	82 ms	1884 KB	Output is correct
39	Correct	79 ms	1764 KB	Output is correct
40	Correct	81 ms	1800 KB	Output is correct

Subtask #6
60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	200 ms	2988 KB	Output is correct
2	Correct	216 ms	2936 KB	Output is correct
3	Correct	196 ms	2888 KB	Output is correct
4	Correct	201 ms	2864 KB	Output is correct
5	Correct	200 ms	2884 KB	Output is correct
6	Correct	198 ms	2872 KB	Output is correct
7	Correct	203 ms	2904 KB	Output is correct
8	Correct	202 ms	2904 KB	Output is correct
9	Correct	197 ms	2820 KB	Output is correct
10	Correct	202 ms	2868 KB	Output is correct
11	Correct	203 ms	2816 KB	Output is correct
12	Correct	202 ms	2776 KB	Output is correct
13	Correct	205 ms	2944 KB	Output is correct
14	Correct	192 ms	2944 KB	Output is correct
15	Correct	182 ms	2652 KB	Output is correct
16	Correct	176 ms	2708 KB	Output is correct
17	Correct	172 ms	2652 KB	Output is correct
18	Correct	176 ms	2624 KB	Output is correct
19	Correct	176 ms	2916 KB	Output is correct
20	Correct	171 ms	2628 KB	Output is correct

Submission #564729

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 3.0 / 3.0

Subtask #4 12.0 / 12.0

Subtask #5 15.0 / 15.0

Subtask #6 60.0 / 60.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
3.0 / 3.0

Subtask #4
12.0 / 12.0

Subtask #5
15.0 / 15.0

Subtask #6
60.0 / 60.0