Submission #966466

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
966466	2024-04-19T23:46:21 Z	pavement	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	47 ms	8212 KB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;

using i128 = __int128;

#define pb push_back

const int BLK_SZ = 182;

void Anna(int N, vector<char> S) {
	int first_X = -1;
	vector<bool> positions(N);
	vector<i128> fib(BLK_SZ + 1);
	fib[0] = fib[1] = 1;
	for (int i = 2; i <= BLK_SZ; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}
	for (int i = 0; i < N; i++) {
		if (S[i] == 'X' && first_X == -1) {
			first_X = i;
		} else if (first_X == -1) {
			continue;
		} else if (S[i] == 'Z') {
			assert(i);
			if (positions[i - 1] == 1) {
				positions[i - 1] = 0;
			}
			positions[i] = 1;
		}
	}
	for (int i = 0; i < N; i += BLK_SZ) {
		int r = min(N, i + BLK_SZ);
		// [i, r)
		i128 cur = 0;
		for (int j = i; j < r; j++) {
			if (positions[j]) {
				cur += fib[r - j];
			}
		}
		for (int j = 0; j < 127; j++) {
			Send(!!(cur & ((i128)1 << j)));
		}
	}
	for (int j = 0; j < 17; j++) {
		Send(!!((first_X + 1) & ((i128)1 << j)));
	}
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;

using i128 = __int128;

#define pb push_back

const int BLK_SZ = 182;

void Bruno(int N, int L, vector<int> A) {
	int first_X = 0;
	vector<bool> positions(N);
	vector<i128> fib(BLK_SZ + 1);
	fib[0] = fib[1] = 1;
	for (int i = 2; i <= BLK_SZ; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}
	for (int j = L - 17; j < L; j++) {
		if (A[j]) {
			first_X |= (1 << (j - (L - 17)));
		}
	}
	first_X--;
	if (first_X == -1) {
		for (int i = 0; i < N; i++) {
			Remove(i);
		}
		return;
	}
	for (int i = 0, l = 0; i < L - 17; i += 127, l += BLK_SZ) {
		int r = min(N, l + BLK_SZ);
		i128 cur = 0;
		for (int j = i; j < min(L, i + 127); j++) {
			if (A[j]) {
				cur |= ((i128)1 << (j - i));
			}
		}
		// [l, r)
		for (int j = l; j < r; j++) {
			if (fib[r - j] > cur) {
				positions[j] = 0;
			} else {
				positions[j] = 1;
				cur -= fib[r - j];
				j++;
			}
		}
	}
	for (int i = 0; i < first_X; i++) {
		Remove(i);
	}
	vector<int> buf;
	for (int i = first_X + 1; i < N; i++) {
		if (positions[i]) {
			while (!buf.empty()) {
				Remove(buf.back());
				buf.pop_back();
			}
			Remove(i);
		} else {
			buf.pb(i);
		}
	}
	buf.pb(first_X);
	while (!buf.empty()) {
		Remove(buf.back());
		buf.pop_back();
	}
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	792 KB	Output is correct
2	Correct	0 ms	792 KB	Output is correct
3	Correct	0 ms	792 KB	Output is correct
4	Correct	0 ms	780 KB	Output is correct
5	Correct	0 ms	780 KB	Output is correct
6	Correct	1 ms	788 KB	Output is correct
7	Correct	1 ms	792 KB	Output is correct
8	Correct	1 ms	780 KB	Output is correct
9	Correct	0 ms	780 KB	Output is correct
10	Correct	0 ms	792 KB	Output is correct
11	Correct	0 ms	788 KB	Output is correct

Subtask #2

95.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	7648 KB	Output is correct
2	Correct	37 ms	7820 KB	Output is correct
3	Correct	42 ms	8076 KB	Output is correct
4	Correct	37 ms	7796 KB	Output is correct
5	Correct	40 ms	7804 KB	Output is correct
6	Correct	42 ms	7720 KB	Output is correct
7	Correct	38 ms	7804 KB	Output is correct
8	Correct	38 ms	7736 KB	Output is correct
9	Correct	38 ms	7804 KB	Output is correct
10	Correct	41 ms	7600 KB	Output is correct
11	Correct	37 ms	7736 KB	Output is correct
12	Correct	38 ms	7820 KB	Output is correct
13	Correct	47 ms	8088 KB	Output is correct
14	Correct	43 ms	7568 KB	Output is correct
15	Correct	43 ms	7668 KB	Output is correct
16	Correct	39 ms	7736 KB	Output is correct
17	Correct	42 ms	7848 KB	Output is correct
18	Correct	45 ms	8212 KB	Output is correct
19	Correct	42 ms	7744 KB	Output is correct
20	Correct	41 ms	7708 KB	Output is correct
21	Correct	40 ms	7768 KB	Output is correct
22	Correct	45 ms	8088 KB	Output is correct
23	Correct	37 ms	7712 KB	Output is correct
24	Correct	36 ms	7812 KB	Output is correct
25	Correct	44 ms	7756 KB	Output is correct
26	Correct	41 ms	7948 KB	Output is correct
27	Correct	43 ms	7736 KB	Output is correct
28	Correct	46 ms	7780 KB	Output is correct
29	Correct	42 ms	7912 KB	Output is correct
30	Correct	43 ms	7820 KB	Output is correct
31	Correct	42 ms	7612 KB	Output is correct
32	Correct	37 ms	7608 KB	Output is correct
33	Correct	37 ms	7724 KB	Output is correct