oj.uz

Submission #798890

# Submission time Handle Problem Language Result Execution time Memory
798890 2023-07-31T06:29:17 Z ymm Ancient Machine (JOI21_ancient_machine) C++17
100 / 100
 299 ms 8580 KB 
#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');
}

#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 572 KB Output is correct
2 Correct 1 ms 524 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 0 ms 520 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 0 ms 612 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 8476 KB Output is correct
2 Correct 244 ms 8320 KB Output is correct
3 Correct 244 ms 8428 KB Output is correct
4 Correct 256 ms 8576 KB Output is correct
5 Correct 243 ms 8440 KB Output is correct
6 Correct 247 ms 8444 KB Output is correct
7 Correct 244 ms 8548 KB Output is correct
8 Correct 250 ms 8324 KB Output is correct
9 Correct 253 ms 8468 KB Output is correct
10 Correct 243 ms 8448 KB Output is correct
11 Correct 248 ms 8580 KB Output is correct
12 Correct 257 ms 8472 KB Output is correct
13 Correct 225 ms 8304 KB Output is correct
14 Correct 299 ms 8440 KB Output is correct
15 Correct 257 ms 8552 KB Output is correct
16 Correct 281 ms 8544 KB Output is correct
17 Correct 218 ms 7384 KB Output is correct
18 Correct 33 ms 6760 KB Output is correct
19 Correct 32 ms 6740 KB Output is correct
20 Correct 251 ms 8552 KB Output is correct
21 Correct 250 ms 8524 KB Output is correct
22 Correct 225 ms 8440 KB Output is correct
23 Correct 249 ms 8424 KB Output is correct
24 Correct 247 ms 8468 KB Output is correct
25 Correct 32 ms 6832 KB Output is correct
26 Correct 214 ms 7372 KB Output is correct
27 Correct 33 ms 6748 KB Output is correct
28 Correct 215 ms 7404 KB Output is correct
29 Correct 33 ms 6780 KB Output is correct
30 Correct 32 ms 6756 KB Output is correct
31 Correct 32 ms 6748 KB Output is correct
32 Correct 246 ms 8552 KB Output is correct
33 Correct 240 ms 8472 KB Output is correct