//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;
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;
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
636 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
636 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
636 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
636 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
636 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
192 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
