Submission #564724

#	Time	Username	Problem	Language	Result	Execution time	Memory
564724		DanShaders	Broken Device 2 (JOI22_device2)	C++17	96 / 100	246 ms	3136 KiB

Anna

//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 = 145, N = LEN + 1;

bool inited = false;
ll dp[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];
	}

	return LEN;
}

pair<vector<int>, vector<int>> Anna(ll n) {
	bool parity = n & 1;
	n /= 2;
	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;
		}
	}

	// for (int x : u) {
	// 	cout << x << " ";
	// }
	// cout << endl;

	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());
	}

	// for (int x : s) {
	// 	cout << x;
	// }
	// cout << endl;
	

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

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

	// for (int x : s) {
	// 	cout << x;
	// }
	// cout << endl;
	// for (int x : t) {
	// 	cout << x << " ";
	// }
	// cout << endl;
	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;
		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];
				}
			}
		}
	}
	// for (int x : a) {
	// 	cout << x;
	// }
	// cout << endl;
	// cout << d[1][145][144] << endl;
	if (!recover(a, 1, 0, 0)) {
		path.push_back({1, -1});
		assert(recover(a, 0, 0, 1));
		path.erase(path.begin());
	}
	// for (auto u : path) {
	// 	cout << u.y << " ";
	// }
	// cout << endl;
	// for (auto [_, x] : path) {
	// 	cout << x << " ";
	// }
	// cout << endl;
	int rlen = 1;
	for (auto u : path) {
		rlen += u.y + 2;
	}
	ll ans = 0;
	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;
}

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 = 145, N = LEN + 1;

bool inited = false;
ll dp[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];
	}

	return LEN;
}

pair<vector<int>, vector<int>> Anna(ll n) {
	bool parity = n & 1;
	n /= 2;
	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;
		}
	}

	// for (int x : u) {
	// 	cout << x << " ";
	// }
	// cout << endl;

	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());
	}

	// for (int x : s) {
	// 	cout << x;
	// }
	// cout << endl;
	

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

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

	// for (int x : s) {
	// 	cout << x;
	// }
	// cout << endl;
	// for (int x : t) {
	// 	cout << x << " ";
	// }
	// cout << endl;
	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;
		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];
				}
			}
		}
	}
	// for (int x : a) {
	// 	cout << x;
	// }
	// cout << endl;
	// cout << d[1][145][144] << endl;
	if (!recover(a, 1, 0, 0)) {
		path.push_back({1, -1});
		assert(recover(a, 0, 0, 1));
		path.erase(path.begin());
	}
	// for (auto u : path) {
	// 	cout << u.y << " ";
	// }
	// cout << endl;
	// for (auto [_, x] : path) {
	// 	cout << x << " ";
	// }
	// cout << endl;
	int rlen = 1;
	for (auto u : path) {
		rlen += u.y + 2;
	}
	ll ans = 0;
	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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 56 / 60