Submission #966459

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
966459	2024-04-19T23:35:59 Z	pavement	Ancient Machine (JOI21_ancient_machine)	C++17	49 / 100	64 ms	9000 KB

Anna

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

using i128 = __int128;

#define pb push_back

const int BLK_SZ = 91;

void Anna(int N, vector<char> S) {
	int first_X = -1;
	vector<bool> positions(N);
	vector<i128> fib(BLK_SZ + 5);
	fib[0] = fib[1] = 1;
	for (int i = 2; i < BLK_SZ + 5; 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 < 128; 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 = 91;

void Bruno(int N, int L, vector<int> A) {
	int first_X = 0;
	vector<bool> positions(N);
	vector<i128> fib(BLK_SZ + 5);
	fib[0] = fib[1] = 1;
	for (int i = 2; i < BLK_SZ + 5; 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 += 128, l += BLK_SZ) {
		int r = min(N, l + BLK_SZ);
		i128 cur = 0;
		for (int j = i; j < min(L, i + 128); 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	1 ms	780 KB	Output is correct
2	Correct	0 ms	792 KB	Output is correct
3	Correct	1 ms	792 KB	Output is correct
4	Correct	1 ms	780 KB	Output is correct
5	Correct	0 ms	780 KB	Output is correct
6	Correct	1 ms	780 KB	Output is correct
7	Correct	0 ms	780 KB	Output is correct
8	Correct	0 ms	792 KB	Output is correct
9	Correct	0 ms	788 KB	Output is correct
10	Correct	0 ms	792 KB	Output is correct
11	Correct	0 ms	780 KB	Output is correct

Subtask #2

44.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	48 ms	8636 KB	Partially correct
2	Partially correct	53 ms	8464 KB	Partially correct
3	Partially correct	47 ms	8652 KB	Partially correct
4	Partially correct	54 ms	8708 KB	Partially correct
5	Partially correct	48 ms	8688 KB	Partially correct
6	Partially correct	50 ms	8692 KB	Partially correct
7	Partially correct	48 ms	8736 KB	Partially correct
8	Partially correct	47 ms	8648 KB	Partially correct
9	Partially correct	47 ms	8524 KB	Partially correct
10	Partially correct	46 ms	8764 KB	Partially correct
11	Partially correct	54 ms	8804 KB	Partially correct
12	Partially correct	52 ms	8500 KB	Partially correct
13	Partially correct	51 ms	8896 KB	Partially correct
14	Partially correct	52 ms	8712 KB	Partially correct
15	Partially correct	54 ms	8660 KB	Partially correct
16	Partially correct	51 ms	8520 KB	Partially correct
17	Partially correct	53 ms	8920 KB	Partially correct
18	Partially correct	51 ms	8608 KB	Partially correct
19	Partially correct	54 ms	8580 KB	Partially correct
20	Partially correct	47 ms	8708 KB	Partially correct
21	Partially correct	46 ms	8564 KB	Partially correct
22	Partially correct	52 ms	9000 KB	Partially correct
23	Partially correct	46 ms	8996 KB	Partially correct
24	Partially correct	47 ms	8640 KB	Partially correct
25	Partially correct	54 ms	8588 KB	Partially correct
26	Partially correct	51 ms	8872 KB	Partially correct
27	Partially correct	51 ms	8580 KB	Partially correct
28	Partially correct	64 ms	8812 KB	Partially correct
29	Partially correct	57 ms	8632 KB	Partially correct
30	Partially correct	52 ms	8548 KB	Partially correct
31	Partially correct	51 ms	8720 KB	Partially correct
32	Partially correct	49 ms	8672 KB	Partially correct
33	Partially correct	48 ms	8580 KB	Partially correct