#include "Anna.h"
#include <algorithm>
#include <cassert>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
namespace A {
constexpr int Ba = 1e8, Sz = 150;
using INT = int[Sz];
INT fib[201];
void Add(INT a, INT b) {
for (int carry = 0, i = 0; i < Sz; ++i)
carry = (a[i] += b[i] + carry) / Ba, a[i] %= Ba;
}
void A_init() {
memset(fib, 0, sizeof fib);
fib[0][0] = fib[1][0] = 1;
for (int i = 2; i <= 200; ++i)
memcpy(fib[i], fib[i - 2], sizeof fib[0]), Add(fib[i], fib[i - 1]);
}
void order(int *a, INT out) {
memset(out, 0, sizeof *out * Sz);
for (int i = 0; i < 200; ++i)
if (a[i])
Add(out, fib[i + 1]);
}
void Half(INT a) {
int carry = 0, j;
for (j = Sz - 1; j >= 0; --j) {
a[j] += carry * Ba;
carry = a[j] & 1;
a[j] /= 2;
}
}
}
void Anna(int N, std::vector<char> S) {
using namespace A;
A_init();
vector<int> T(100000);
int sum = 0;
for (int i = 0; i < N; sum += T[i++]) {
if ((S[i] == 'X' and not sum) or (S[i] == 'Z' and sum))
T[i] = 1;
else
T[i] = 0;
}
int nxt;
for (int i = 0; i < N - 1; ++i) if (T[i] == 1) {
nxt = T[i + 1];
break;
}
// for(int i=0;i<100000;++i)T[i]=i&1;
for (int i = 0; i < 100000; i += 200) {
static INT x;
order(T.data() + i, x);
//cout << x[0] << endl;
for (int j = 0; j < 140; ++j)
Send(x[0] & 1), Half(x);
}
Send(nxt);
}
#include "Bruno.h"
#include <cassert>
#include <cstring>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
namespace B {
constexpr int Ba = 1e8, Sz = 150;
using INT = int[Sz];
INT fib[201];
void Add(INT a, INT b) {
for (int carry = 0, i = 0; i < Sz; ++i) {
carry = (a[i] += b[i] + carry) / Ba, a[i] %= Ba;
}
}
void Sub(INT a, INT b) {
for (int i = 0; i < Sz; ++i)
if ((a[i] -= b[i]) < 0) a[i] += Ba, a[i + 1]--;
}
int Le(INT a, INT b) {
for (int i = Sz - 1; i >= 0; --i) if (a[i] != b[i]) return a[i] < b[i] ? -1 : 1;
return 0;
}
void B_init() {
memset(fib, 0, sizeof fib);
fib[0][0] = fib[1][0] = 1;
for (int i = 2; i <= 200; ++i) memcpy(fib[i], fib[i - 2], sizeof fib[0]), Add(fib[i], fib[i - 1]);
}
void lexicographic_order_to_fib(INT ord, int out[200]) {
for (int i = 200; i >= 1; --i) {
if (-1 != Le(ord, fib[i]))
out[i - 1] = 1, Sub(ord, fib[i]);
else
out[i - 1] = 0;
}
}
}
void Bruno(int N, int L, vector<int> A) {
using namespace B;
B_init();
vector<int> T, stk(100000);
/* # 200-digit fib <= 2^140 */
for (int i = 0; i < L - 1; i += 140) {
int fib[200];
INT x = {0}, p2 = {0};
p2[0] = 1;
for (int j = 0; j < 140; ++j) {
if (A[i + j])
Add(x, p2);
Add(p2, p2);
}
//cout << " : " <<x[0] << endl;
lexicographic_order_to_fib(x, fib);
for (int j = 0; j < 200; ++j)
T.push_back(fib[j]);
}
int nxt = A.back();
for (int i = 0; i + 1 < 100000; ++i) if (T[i] == 1) { T[i + 1] = nxt; break; }
int top = 0;
assert(A.size() == 70001);
assert(T.size() == 100000);
//for(int i=0;i<20;++i)cout<<T[i]<<' ';cout<<endl; for(int i=0;i<100000;++i)assert((i&1)==T[i]);
vector<int> Dead(N);
auto REMOVE = [&](int i) { if (i < N and not Dead[i]) Dead[i] = 1, Remove(i); };
for (int lst = -1, fst = -1, i = 0; i < N; ++i) {
if (!~fst) {
if (T[i] == 1) fst = i, lst = i;
else REMOVE(i);
} else {
if (T[i] == 1) {
for (int j = i - 1; j > lst; --j) REMOVE(j);
REMOVE(i);
}
}
}
for (int i = 0; i < N; ++i) REMOVE(i);
}
Compilation message
Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:69:7: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
69 | Send(nxt);
| ~~~~^~~~~
Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:70:6: warning: unused variable 'top' [-Wunused-variable]
70 | int top = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
3680 KB |
Output is correct |
| 2 |
Correct |
57 ms |
3732 KB |
Output is correct |
| 3 |
Incorrect |
57 ms |
3804 KB |
Wrong Answer [6] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
893 ms |
9216 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
