#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int B = 100;
const int F = 70;
__int128_t Fibonacci(int n) {
static vector<__int128_t> dp = {1, 2};
while (dp.size() <= n) dp.emplace_back(end(dp)[-2] + end(dp)[-1]);
return dp[n];
}
vector<int> CompressB(vector<int> A) {
assert(A.size() == B);
__int128_t H = 0;
while (!A.empty()) {
if (A.back() == 0) {
A.pop_back();
} else {
H += Fibonacci(int(A.size()) - 1);
A.pop_back();
if (!A.empty()) {
assert(A.back() == 0);
A.pop_back();
}
}
}
vector<int> C;
for (int i = 0; i < F; i++) {
C.emplace_back(H & 1);
H /= 2;
}
reverse(begin(C), end(C));
assert(H == 0);
assert(C.size() == F);
return C;
}
vector<int> UncompressB(vector<int> C) {
assert(C.size() == F);
__int128_t H = 0;
for (auto c : C) {
H = H * 2 + c;
}
vector<int> A;
for (int len = B; len > 0; ) {
if (H >= Fibonacci(len - 1)) {
H -= Fibonacci(len - 1);
A.emplace_back(1); len--;
if (len > 0) {
A.emplace_back(0); len--;
}
} else {
A.emplace_back(0); len--;
}
}
reverse(begin(A), end(A));
assert(H == 0);
assert(A.size() == B);
return A;
}
vector<int> Compress(int N, vector<int> A) {
while (A.size() % B != 0) A.emplace_back(0);
assert(A.size() % B == 0);
vector<int> C;
vector<int> cur;
for (auto a : A) {
cur.emplace_back(a);
if (cur.size() == B) {
auto res = CompressB(cur); cur.clear();
for (auto c : res) {
C.emplace_back(c);
}
}
}
assert(C.size() == A.size() / B * F);
return C;
}
vector<int> Uncompress(int N, vector<int> C) {
assert(C.size() % F == 0);
vector<int> A;
vector<int> cur;
for (auto c : C) {
cur.emplace_back(c);
if (cur.size() == F) {
auto res = UncompressB(cur); cur.clear();
for (auto a : res) {
A.emplace_back(a);
}
}
}
assert(A.size() == C.size() / F * B);
while (A.size() > N) A.pop_back();
return A;
}
}
void Anna(int N, vector<char> S) {
// Consider the following greedy algorithm:
// First step:
// Set last = -1
// Identify the first character X, let it be i
// Delete all characters [last + 1, i - 1] in reverse order.
// Set last = i
//
// Second step:
// Identify the first character Z after index last, let it be i
// Delete all characters [last + 1, i - 1] in reverse order
// Delete i
// Set last = i
//
// It can be shown that this algorithm is optimal. Thus, we can
// send a bitstring of length N to denote the first X, and then
// consecutive Zs.
//
// To optimize, observe that if there is a string ZZ, we only need
// to care about the first Z. This way, each consecutive Z has a gap
// of 1. Thus, the number of sequences is F(N) = F(N - 2) + F(N - 1),
// the fibonacci number. This converges to around 0.694 * N. Instead of
// using big integers, we can use blocks of size B = 100 instead, for
// 70000 total bits when N = 100000.
bool X = 0;
vector<int> str;
for (int i = 0; i < N; i++) {
if (!X && S[i] == 'X') {
X = 1;
str.emplace_back(1);
} else if (X && S[i] == 'Z') {
str.emplace_back(1);
} else {
str.emplace_back(0);
}
}
for (int i = 1; i < N; i++) {
if (str[i - 1] == 1 && str[i] == 1) {
str[i] = 0;
}
}
assert(Uncompress(N, Compress(N, str)) == str);
for (auto s : Compress(N, str)) {
Send(s);
}
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int B = 100;
const int F = 70;
__int128_t Fibonacci(int n) {
static vector<__int128_t> dp = {1, 2};
while (dp.size() <= n) dp.emplace_back(end(dp)[-2] + end(dp)[-1]);
return dp[n];
}
vector<int> CompressB(vector<int> A) {
assert(A.size() == B);
__int128_t H = 0;
while (!A.empty()) {
if (A.back() == 0) {
A.pop_back();
} else {
H += Fibonacci(int(A.size()) - 1);
A.pop_back();
if (!A.empty()) {
assert(A.back() == 0);
A.pop_back();
}
}
}
vector<int> C;
for (int i = 0; i < F; i++) {
C.emplace_back(H & 1);
H /= 2;
}
reverse(begin(C), end(C));
assert(H == 0);
assert(C.size() == F);
return C;
}
vector<int> UncompressB(vector<int> C) {
assert(C.size() == F);
__int128_t H = 0;
for (auto c : C) {
H = H * 2 + c;
}
vector<int> A;
for (int len = B; len > 0; ) {
if (H >= Fibonacci(len - 1)) {
H -= Fibonacci(len - 1);
A.emplace_back(1); len--;
if (len > 0) {
A.emplace_back(0); len--;
}
} else {
A.emplace_back(0); len--;
}
}
reverse(begin(A), end(A));
assert(H == 0);
assert(A.size() == B);
return A;
}
vector<int> Compress(int N, vector<int> A) {
while (A.size() % B != 0) A.emplace_back(0);
assert(A.size() % B == 0);
vector<int> C;
vector<int> cur;
for (auto a : A) {
cur.emplace_back(a);
if (cur.size() == B) {
auto res = CompressB(cur); cur.clear();
for (auto c : res) {
C.emplace_back(c);
}
}
}
assert(C.size() == A.size() / B * F);
return C;
}
vector<int> Uncompress(int N, vector<int> C) {
assert(C.size() % F == 0);
vector<int> A;
vector<int> cur;
for (auto c : C) {
cur.emplace_back(c);
if (cur.size() == F) {
auto res = UncompressB(cur); cur.clear();
for (auto a : res) {
A.emplace_back(a);
}
}
}
assert(A.size() == C.size() / F * B);
while (A.size() > N) A.pop_back();
return A;
}
}
void Bruno(int N, int L, vector<int> A) {
vector<int> del(N);
auto str = Uncompress(N, A);
int firstX = N;
for (int i = 0; i < N; i++) {
if (str[i] == 1) {
firstX = i;
break;
}
}
for (int i = firstX - 1; i >= 0; i--) {
Remove(i);
del[i] = 1;
}
for (int i = firstX + 1, j = firstX; i < N; i++) {
if (str[i] == 1) {
for (int k = i - 1; k >= j + 1; k--) {
Remove(k);
del[k] = 1;
}
Remove(i);
del[i] = 1;
}
}
for (int i = 0; i < N; i++) {
if (!del[i]) {
Remove(i);
del[i] = 1;
}
}
}
Compilation message
Anna.cpp: In function '__int128 {anonymous}::Fibonacci(int)':
Anna.cpp:11:22: warning: comparison of integer expressions of different signedness: 'std::vector<__int128>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
11 | while (dp.size() <= n) dp.emplace_back(end(dp)[-2] + end(dp)[-1]);
| ~~~~~~~~~~^~~~
Anna.cpp: In function 'std::vector<int> {anonymous}::Uncompress(int, std::vector<int>)':
Anna.cpp:111:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
111 | while (A.size() > N) A.pop_back();
| ~~~~~~~~~^~~
Bruno.cpp: In function '__int128 {anonymous}::Fibonacci(int)':
Bruno.cpp:11:22: warning: comparison of integer expressions of different signedness: 'std::vector<__int128>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
11 | while (dp.size() <= n) dp.emplace_back(end(dp)[-2] + end(dp)[-1]);
| ~~~~~~~~~~^~~~
Bruno.cpp: In function 'std::vector<int> {anonymous}::Uncompress(int, std::vector<int>)':
Bruno.cpp:111:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
111 | while (A.size() > N) A.pop_back();
| ~~~~~~~~~^~~
Bruno.cpp: At global scope:
Bruno.cpp:73:15: warning: 'std::vector<int> {anonymous}::Compress(int, std::vector<int>)' defined but not used [-Wunused-function]
73 | vector<int> Compress(int N, vector<int> A) {
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
4584 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
