답안 #966461

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

Anna

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

using i128 = __int128;

#define pb push_back

const int BLK_SZ = 179;

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

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 += 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	792 KB	Output is correct
2	Correct	0 ms	788 KB	Output is correct
3	Correct	0 ms	780 KB	Output is correct
4	Correct	0 ms	780 KB	Output is correct
5	Correct	0 ms	776 KB	Output is correct
6	Correct	0 ms	780 KB	Output is correct
7	Correct	1 ms	792 KB	Output is correct
8	Correct	0 ms	792 KB	Output is correct
9	Correct	0 ms	780 KB	Output is correct
10	Correct	0 ms	1176 KB	Output is correct
11	Correct	0 ms	792 KB	Output is correct

Subtask #2

93.0 / 95.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	38 ms	8024 KB	Partially correct
2	Partially correct	38 ms	7776 KB	Partially correct
3	Partially correct	39 ms	7588 KB	Partially correct
4	Partially correct	38 ms	7804 KB	Partially correct
5	Partially correct	38 ms	7564 KB	Partially correct
6	Partially correct	38 ms	7736 KB	Partially correct
7	Partially correct	37 ms	7796 KB	Partially correct
8	Partially correct	38 ms	7736 KB	Partially correct
9	Partially correct	39 ms	7740 KB	Partially correct
10	Partially correct	38 ms	7800 KB	Partially correct
11	Partially correct	38 ms	7592 KB	Partially correct
12	Partially correct	40 ms	7724 KB	Partially correct
13	Partially correct	43 ms	7784 KB	Partially correct
14	Partially correct	43 ms	7736 KB	Partially correct
15	Partially correct	42 ms	7724 KB	Partially correct
16	Partially correct	42 ms	7716 KB	Partially correct
17	Partially correct	45 ms	7800 KB	Partially correct
18	Partially correct	43 ms	7624 KB	Partially correct
19	Partially correct	44 ms	7744 KB	Partially correct
20	Partially correct	38 ms	7776 KB	Partially correct
21	Partially correct	37 ms	7804 KB	Partially correct
22	Partially correct	42 ms	7980 KB	Partially correct
23	Partially correct	38 ms	7724 KB	Partially correct
24	Partially correct	37 ms	7804 KB	Partially correct
25	Partially correct	42 ms	7724 KB	Partially correct
26	Partially correct	48 ms	8076 KB	Partially correct
27	Partially correct	43 ms	7708 KB	Partially correct
28	Partially correct	42 ms	7804 KB	Partially correct
29	Partially correct	43 ms	7760 KB	Partially correct
30	Partially correct	47 ms	7704 KB	Partially correct
31	Partially correct	42 ms	7816 KB	Partially correct
32	Partially correct	39 ms	7708 KB	Partially correct
33	Partially correct	38 ms	7628 KB	Partially correct