#include <bits/stdc++.h>
using namespace std;
#ifndef hwe
#include "Anna.h"
#endif // hwe
namespace {
const int LIM = 92;
long long fib[LIM];
}
void Send(int a);
void mySend(long long num) {
vector<int> s;
while (num > 0) s.emplace_back(num & 1), num >>= 1;
while (s.size() < 64) s.emplace_back(0);
for (int i = s.size() - 1; i >= 0; --i) {
Send(s[i]);
// cout << s[i];
}
}
void Anna(int n, vector<char> S) {
fib[0] = 1, fib[1] = 1;
for (int i = 2; i < LIM; ++i)
fib[i] = fib[i - 1] + fib[i - 2];
int p = 0; vector<int> send(n);
while (p < n && S[p] != 'X') {
send[p] = 0; ++p;
}
while (p < n) {
send[p] = 1; ++p;
while (p < n && S[p] != 'Z') {
send[p] = 0, ++p;
}
while (p + 1 < n && S[p + 1] == 'Z') {
send[p] = 0, ++p;
}
}
for (int i = 0; i < n; ++i) {
if (send[i] == 1) {
send.insert(send.begin() + i + 1, 0);
break;
}
}
int last = -1;
for (int i = 0; i <= n; ++i) {
if (i - last == 90) {
long long num = 0;
for (int j = i; j > last; --j)
if (send[j] == 1) num += fib[j - last];
mySend(num);
last = i;
}
}
for (auto &x : send) cerr << x;
cerr << '\n';
if (last < n) {
long long num = 0;
for (int i = n; i > last; --i)
if (send[i] == 1) num += fib[i - last];
// cout << num << '\n';
mySend(num);
}
}
#include <bits/stdc++.h>
using namespace std;
#ifndef hwe
#include "Bruno.h"
#endif // hwe
#define MASK(n) (1ll << (n))
#define BIT(n, i) ((n) >> (i) & 1)
#define FLIP(n, i) ((n) ^ (1ll << (i)))
bool maximize(int &x, int y) {
if (x < y) {
x = y;
return true;
}
return false;
}
namespace {
const int lim = 95;
long long fib2[lim];
}
void Remove(int d);
void Bruno(int n, int L, vector<int> A) {
fib2[0] = 1, fib2[1] = 1;
for (int i = 2; i < lim; ++i)
fib2[i] = fib2[i - 1] + fib2[i - 2];
vector<int> decode;
for (int start = 0; start + 64 + 63 < A.size(); ++start) {
long long num = 0; vector<int> tmp;
for (int i = start; i <= start + 63; ++i)
num = num * 2 + A[i];
for (int i = 90; i > 0; --i) {
if (num >= fib2[i]) tmp.emplace_back(1), num -= fib2[i];
else tmp.emplace_back(0);
}
reverse(tmp.begin(), tmp.end());
for (auto &x : tmp) decode.emplace_back(x);
}
assert(A.size() >= 64);
long long num = 0; vector<int> tmp;
for (int i = A.size() - 64; i < A.size(); ++i)
num = num * 2 + A[i];
for (int i = 90; i > 0; --i) {
if (num >= fib2[i]) tmp.emplace_back(1), num -= fib2[i];
else tmp.emplace_back(0);
}
reverse(tmp.begin(), tmp.end());
while (decode.size() + tmp.size() > n + 1) tmp.pop_back();
for (auto &x : tmp) decode.emplace_back(x);
int sum = 0;
for (auto &x : decode) {
sum += x;
}
if (sum == 0) decode.pop_back();
for (auto &x : decode)
cerr << x;
cerr << '\n';
for (int i = 0; i < decode.size(); ++i) {
if (decode[i] == 1) {
decode.erase(decode.begin() + i + 1);
break;
}
}
int p = 0;
while (p < decode.size() && decode[p] == 0) {
Remove(p), ++p;
}
int start = p;
while (p < decode.size()) {
int cur = p; ++p;
while (p < decode.size() && decode[p] == 0) ++p;
for (int i = min(int(decode.size()), p) - 1; i > cur; --i) {
Remove(i);
}
if (p < decode.size()) Remove(p);
}
if (start < decode.size()) Remove(start);
}
Compilation message
Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:33:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int start = 0; start + 64 + 63 < A.size(); ++start) {
| ~~~~~~~~~~~~~~~~^~~~~~~~~~
Bruno.cpp:47:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i = A.size() - 64; i < A.size(); ++i)
| ~~^~~~~~~~~~
Bruno.cpp:55:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
55 | while (decode.size() + tmp.size() > n + 1) tmp.pop_back();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
Bruno.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i = 0; i < decode.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
Bruno.cpp:78:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | while (p < decode.size() && decode[p] == 0) {
| ~~^~~~~~~~~~~~~~~
Bruno.cpp:83:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | while (p < decode.size()) {
| ~~^~~~~~~~~~~~~~~
Bruno.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | while (p < decode.size() && decode[p] == 0) ++p;
| ~~^~~~~~~~~~~~~~~
Bruno.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | if (p < decode.size()) Remove(p);
| ~~^~~~~~~~~~~~~~~
Bruno.cpp:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if (start < decode.size()) Remove(start);
| ~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
780 KB |
Output is correct |
| 2 |
Correct |
0 ms |
792 KB |
Output is correct |
| 3 |
Correct |
0 ms |
780 KB |
Output is correct |
| 4 |
Correct |
0 ms |
780 KB |
Output is correct |
| 5 |
Correct |
0 ms |
780 KB |
Output is correct |
| 6 |
Correct |
0 ms |
788 KB |
Output is correct |
| 7 |
Correct |
0 ms |
780 KB |
Output is correct |
| 8 |
Correct |
2 ms |
792 KB |
Output is correct |
| 9 |
Correct |
0 ms |
780 KB |
Output is correct |
| 10 |
Correct |
0 ms |
792 KB |
Output is correct |
| 11 |
Correct |
0 ms |
796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
207 ms |
57212 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
