Submission #966457

#	Time	Username	Problem	Language	Result	Execution time	Memory
966457		pavement	Ancient Machine (JOI21_ancient_machine)	C++17	97 / 100	48 ms	8288 KiB

Anna

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

using ull = unsigned long long;

#define pb push_back

const int BLK_SZ = 90;

void Anna(int N, vector<char> S) {
	int first_X = -1;
	vector<bool> positions(N);
	vector<ull> 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)
		ull cur = 0;
		for (int j = i; j < r; j++) {
			if (positions[j]) {
				cur += fib[r - j];
			}
		}
		for (int j = 0; j < 64; j++) {
			Send(!!(cur & (1ll << j)));
		}
	}
	for (int j = 0; j < 17; j++) {
		Send(!!((first_X + 1) & (1ll << j)));
	}
}

Bruno

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

using ull = unsigned long long;

#define pb push_back

const int BLK_SZ = 90;

void Bruno(int N, int L, vector<int> A) {
	int first_X = 0;
	vector<bool> positions(N);
	vector<ull> 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 += 64, l += BLK_SZ) {
		int r = min(N, l + BLK_SZ);
		ull cur = 0;
		for (int j = i; j < min(L, i + 64); j++) {
			if (A[j]) {
				cur |= (1ll << (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 / 5
• Subtask 2: 92 / 95