//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;
int Declare() {
return 181;
}
pair<vector<int>, vector<int>> Anna(ll n) {
vector<int> u;
for (; n; n /= 2) {
u.push_back(n & 1);
}
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) < Declare()) {
s.push_back(s.back() ^ 1);
}
vector<int> t = {1};
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;
return {s, t};
}
vector<pair<int, int>> path;
#define TRY(x) do { if (x) { return true; }} while (false);
int clen;
bool recover(const vector<int> &a, int i, int tlen, int cnt) {
if (i == clen) {
return 2 * tlen <= sz(a) && !cnt;
}
if (2 * tlen > sz(a)) {
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) {
// for (int x : a) {
// cout << x << " ";
// }
// cout << endl;
clen = sz(a);
bool found = false;
for (; clen; --clen) {
path.clear();
if (!recover(a, 1, 0, 0)) {
path.push_back({1, -1});
if (recover(a, 0, 0, 1)) {
path.erase(path.begin());
found = true;
break;
}
} else {
found = true;
break;
}
}
assert(found);
// for (auto [_, x] : path) {
// cout << x << " ";
// }
// cout << endl;
ll n = 0;
for (int i = 0; i < sz(path); ++i) {
n |= path[i].y * (1ll << i);
}
return n;
}
//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;
int Declare() {
return 181;
}
pair<vector<int>, vector<int>> Anna(ll n) {
vector<int> u;
for (; n; n /= 2) {
u.push_back(n & 1);
}
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) < Declare()) {
s.push_back(s.back() ^ 1);
}
vector<int> t = {1};
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;
return {s, t};
}
vector<pair<int, int>> path;
#define TRY(x) do { if (x) { return true; }} while (false);
int clen;
bool recover(const vector<int> &a, int i, int tlen, int cnt) {
if (i == clen) {
return 2 * tlen <= sz(a) && !cnt;
}
if (2 * tlen > sz(a)) {
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) {
// for (int x : a) {
// cout << x << " ";
// }
// cout << endl;
clen = sz(a);
bool found = false;
for (; clen; --clen) {
path.clear();
if (!recover(a, 1, 0, 0)) {
path.push_back({1, -1});
if (recover(a, 0, 0, 1)) {
path.erase(path.begin());
found = true;
break;
}
} else {
found = true;
break;
}
}
assert(found);
// for (auto [_, x] : path) {
// cout << x << " ";
// }
// cout << endl;
ll n = 0;
for (int i = 0; i < sz(path); ++i) {
n |= path[i].y * (1ll << i);
}
return n;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2078 ms |
512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2078 ms |
512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2078 ms |
512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2078 ms |
512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2078 ms |
512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2005 ms |
3480 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
