답안 #966465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
966465	2024-04-19T23:45:45 Z	pavement	Ancient Machine (JOI21_ancient_machine)	C++17	99 / 100	48 ms	7912 KB

Anna

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

using i128 = __int128;

#define pb push_back

const int BLK_SZ = 181;

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 = 181;

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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	780 KB	Output is correct
2	Correct	0 ms	780 KB	Output is correct
3	Correct	0 ms	1284 KB	Output is correct
4	Correct	0 ms	796 KB	Output is correct
5	Correct	0 ms	792 KB	Output is correct
6	Correct	0 ms	788 KB	Output is correct
7	Correct	1 ms	792 KB	Output is correct
8	Correct	1 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

94.0 / 95.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	38 ms	7632 KB	Partially correct
2	Partially correct	38 ms	7844 KB	Partially correct
3	Partially correct	41 ms	7776 KB	Partially correct
4	Partially correct	38 ms	7716 KB	Partially correct
5	Partially correct	43 ms	7760 KB	Partially correct
6	Partially correct	38 ms	7828 KB	Partially correct
7	Partially correct	38 ms	7820 KB	Partially correct
8	Partially correct	38 ms	7724 KB	Partially correct
9	Partially correct	39 ms	7672 KB	Partially correct
10	Partially correct	38 ms	7808 KB	Partially correct
11	Partially correct	38 ms	7764 KB	Partially correct
12	Partially correct	38 ms	7676 KB	Partially correct
13	Partially correct	43 ms	7732 KB	Partially correct
14	Partially correct	43 ms	7704 KB	Partially correct
15	Partially correct	35 ms	7636 KB	Partially correct
16	Partially correct	36 ms	7816 KB	Partially correct
17	Partially correct	44 ms	7864 KB	Partially correct
18	Partially correct	42 ms	7652 KB	Partially correct
19	Partially correct	42 ms	7800 KB	Partially correct
20	Partially correct	37 ms	7612 KB	Partially correct
21	Partially correct	36 ms	7816 KB	Partially correct
22	Partially correct	48 ms	7836 KB	Partially correct
23	Partially correct	37 ms	7856 KB	Partially correct
24	Partially correct	36 ms	7736 KB	Partially correct
25	Partially correct	43 ms	7596 KB	Partially correct
26	Partially correct	45 ms	7856 KB	Partially correct
27	Partially correct	43 ms	7724 KB	Partially correct
28	Partially correct	42 ms	7832 KB	Partially correct
29	Partially correct	42 ms	7812 KB	Partially correct
30	Partially correct	43 ms	7708 KB	Partially correct
31	Partially correct	46 ms	7912 KB	Partially correct
32	Partially correct	38 ms	7812 KB	Partially correct
33	Partially correct	43 ms	7720 KB	Partially correct