oj.uz

답안 #564729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
564729 2022-05-19T14:12:29 Z DanShaders Broken Device 2 (JOI22_device2) C++17
100 / 100
 216 ms 2988 KB 
//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

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

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

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

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

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

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