Submission #798890

#	Time	Username	Problem	Language	Result	Execution time	Memory
798890		ymm	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	299 ms	8580 KiB

Anna

#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' && (i+1 == N || S[i+1] != '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');
}

Bruno

#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);
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95