#include "Anna.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
using namespace std;
namespace {
int constexpr M = 69632;
#define strM "69632"
bitset<M> _fib[2];
bitset<M> *fib[2] = {_fib+0, _fib+1};
bitset<M> ans;
__attribute__((naked, sysv_abi))
void add(bitset<M> *dst, bitset<M> *src) {
asm(R"(
.intel_syntax noprefix
push rbx
xor ecx, ecx
xor bl, bl
.Lmy_anna_0:
neg bl
mov rax, [rdi+rcx+0x00]
adc rax, [rsi+rcx+0x00]
mov [rdi+rcx+0x00], rax
mov rax, [rdi+rcx+0x08]
adc rax, [rsi+rcx+0x08]
mov [rdi+rcx+0x08], rax
mov rax, [rdi+rcx+0x10]
adc rax, [rsi+rcx+0x10]
mov [rdi+rcx+0x10], rax
mov rax, [rdi+rcx+0x18]
adc rax, [rsi+rcx+0x18]
mov [rdi+rcx+0x18], rax
setc bl
add rcx, 0x20
cmp rcx, )" strM R"(/8
jne .Lmy_anna_0
pop rbx
ret
.att_syntax
)");
}
}
void Anna(int N, std::vector<char> S) {
int p = 0;
while (p < N && S[p] != 'X')
++p;
if (p >= N-2)
return;
vector<int> vec;
Loop (i,0,p)
vec.push_back(0);
vec.push_back(1);
vec.push_back(0);
Loop (i,p+2,N)
vec.push_back(S[i] == 'Z');
(*fib[0])[0] = 1;
(*fib[1])[1] = 1;
Loop (i,0,N) {
if (vec[i])
add(&ans, fib[0]);
add(fib[0], fib[1]);
swap(fib[0], fib[1]);
}
int p2 = M-1;
while (!ans[p2])
--p2;
Loop (i,0,p2)
Send(ans[i]);
Send(S[p+1] == 'Z');
}
#include "Bruno.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
using namespace std;
namespace {
int constexpr M = 69632;
#define strM "69632"
bitset<M> _fib[2];
bitset<M> *fib[2] = {_fib+0, _fib+1};
bitset<M> bs;
__attribute__((naked, sysv_abi))
void add(bitset<M> *dst, bitset<M> *src) {
asm(R"(
.intel_syntax noprefix
push rbx
xor ecx, ecx
xor bl, bl
.Lmy_bruno_0:
neg bl
mov rax, [rdi+rcx+0x00]
adc rax, [rsi+rcx+0x00]
mov [rdi+rcx+0x00], rax
mov rax, [rdi+rcx+0x08]
adc rax, [rsi+rcx+0x08]
mov [rdi+rcx+0x08], rax
mov rax, [rdi+rcx+0x10]
adc rax, [rsi+rcx+0x10]
mov [rdi+rcx+0x10], rax
mov rax, [rdi+rcx+0x18]
adc rax, [rsi+rcx+0x18]
mov [rdi+rcx+0x18], rax
setc bl
add rcx, 0x20
cmp rcx, )" strM R"(/8
jne .Lmy_bruno_0
pop rbx
ret
.att_syntax
)");
}
__attribute__((naked, sysv_abi))
void sub(bitset<M> *dst, bitset<M> *src) {
asm(R"(
.intel_syntax noprefix
push rbx
xor ecx, ecx
xor bl, bl
.Lmy_bruno_1:
neg bl
mov rax, [rdi+rcx+0x00]
sbb rax, [rsi+rcx+0x00]
mov [rdi+rcx+0x00], rax
mov rax, [rdi+rcx+0x08]
sbb rax, [rsi+rcx+0x08]
mov [rdi+rcx+0x08], rax
mov rax, [rdi+rcx+0x10]
sbb rax, [rsi+rcx+0x10]
mov [rdi+rcx+0x10], rax
mov rax, [rdi+rcx+0x18]
sbb rax, [rsi+rcx+0x18]
mov [rdi+rcx+0x18], rax
setc bl
add rcx, 0x20
cmp rcx, )" strM R"(/8
jne .Lmy_bruno_1
pop rbx
ret
.att_syntax
)");
}
int cmp(bitset<M> *dst, bitset<M> *src) {
typedef uint64_t u64;
u64 *a = (u64 *)(void *)dst;
u64 *b = (u64 *)(void *)src;
LoopR (i,0,M/64) {
if (a[i] != b[i])
return a[i] < b[i]? -1: 1;
}
return 0;
}
} // namespace
void Bruno(int N, int L, std::vector<int> dard) {
if (!L) {
Loop (i,0,N)
Remove(i);
return;
}
--L;
Loop (i,0,L)
bs[i] = dard[i];
bs[L] = 1;
(*fib[0])[0] = 1;
(*fib[1])[1] = 1;
Loop (i,0,N) {
add(fib[0], fib[1]);
swap(fib[0], fib[1]);
}
vector<int> A(N);
LoopR (i,0,N) {
swap(fib[0], fib[1]);
sub(fib[0], fib[1]);
if (cmp(&bs, fib[0]) >= 0) {
sub(&bs, fib[0]);
A[i] = 1;
} else {
A[i] = 0;
}
}
int p = 0;
while (!A[p])
++p;
A[p+1] = dard[L];
int lst = p+1;
Loop (p2,p+1,N) {
if (!A[p2])
continue;
LoopR (j,lst,p2)
Remove(j);
Remove(p2);
lst = p2+1;
}
Loop (i,0,p+1)
Remove(i);
Loop (i,lst,N)
Remove(i);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
520 KB |
Output is correct |
| 2 |
Correct |
1 ms |
616 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
512 KB |
Wrong Answer [6] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
256 ms |
8436 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
