#include "Bruno.h"
#include <cassert>
#include <cstring>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
namespace B {
constexpr int Ba = 1e9, Sz = 150;
using INT = int[Sz];
INT fib[201];
void Add(INT a, INT b) {
for (int carry, i = 0; i < Sz; ++i)
carry = (a[i] += b[i]) / Ba, a[i] %= Ba;
}
void Sub(INT a, INT b) {
for (int carry, 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[201]) {
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; 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);
}
lexicographic_order_to_fib(x, fib);
for (int j = 0; j < 200; ++j)
T.push_back(fib[j]);
}
int top = 0;
assert(A.size() == 70000);
assert(T.size() == 100000);
auto REMOVE = [&](int i) { if (i < N) Remove(i); };
for (int sum = 0, i = 0; i < 100000; sum += T[i++]) {
if (T[i] == 1) {
if (sum) {
while (top and T[stk[top - 1]] == 0) REMOVE(stk[--top]);
REMOVE(i);
}
else
;
}
else
stk[top++] = i;
}
while (top) REMOVE(stk[--top]);
}
#include "Bruno.h"
#include <cassert>
#include <cstring>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
namespace B {
constexpr int Ba = 1e9, Sz = 150;
using INT = int[Sz];
INT fib[201];
void Add(INT a, INT b) {
for (int carry, i = 0; i < Sz; ++i)
carry = (a[i] += b[i]) / Ba, a[i] %= Ba;
}
void Sub(INT a, INT b) {
for (int carry, 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[201]) {
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; 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);
}
lexicographic_order_to_fib(x, fib);
for (int j = 0; j < 200; ++j)
T.push_back(fib[j]);
}
int top = 0;
assert(A.size() == 70000);
assert(T.size() == 100000);
auto REMOVE = [&](int i) { if (i < N) Remove(i); };
for (int sum = 0, i = 0; i < 100000; sum += T[i++]) {
if (T[i] == 1) {
if (sum) {
while (top and T[stk[top - 1]] == 0) REMOVE(stk[--top]);
REMOVE(i);
}
else
stk[top++] = i;
}
else
stk[top++] = i;
}
while (top) REMOVE(stk[--top]);
}
Compilation message
Anna.cpp: In function 'void B::Add(int*, int*)':
Anna.cpp:16:12: warning: variable 'carry' set but not used [-Wunused-but-set-variable]
16 | for (int carry, i = 0; i < Sz; ++i)
| ^~~~~
Anna.cpp: In function 'void B::Sub(int*, int*)':
Anna.cpp:20:12: warning: unused variable 'carry' [-Wunused-variable]
20 | for (int carry, i = 0; i < Sz; ++i)
| ^~~~~
/usr/bin/ld: /tmp/cccNsjFz.o: in function `Bruno(int, int, std::vector<int, std::allocator<int> >)':
Anna.cpp:(.text+0x521): undefined reference to `Remove(int)'
/usr/bin/ld: Anna.cpp:(.text+0x59d): undefined reference to `Remove(int)'
/usr/bin/ld: Anna.cpp:(.text+0x60c): undefined reference to `Remove(int)'
/usr/bin/ld: /tmp/ccDToqeA.o: in function `main':
grader_anna.cpp:(.text.startup+0x14c): undefined reference to `Anna(int, std::vector<char, std::allocator<char> >)'
collect2: error: ld returned 1 exit status
Bruno.cpp: In function 'void B::Add(int*, int*)':
Bruno.cpp:16:12: warning: variable 'carry' set but not used [-Wunused-but-set-variable]
16 | for (int carry, i = 0; i < Sz; ++i)
| ^~~~~
Bruno.cpp: In function 'void B::Sub(int*, int*)':
Bruno.cpp:20:12: warning: unused variable 'carry' [-Wunused-variable]
20 | for (int carry, i = 0; i < Sz; ++i)
| ^~~~~
