답안 #966460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
966460	2024-04-19T23:40:01 Z	pavement	Ancient Machine (JOI21_ancient_machine)	C++17	96 / 100	48 ms	8064 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 < 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 = 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 += 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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	792 KB	Output is correct
2	Correct	0 ms	792 KB	Output is correct
3	Correct	1 ms	792 KB	Output is correct
4	Correct	0 ms	792 KB	Output is correct
5	Correct	0 ms	792 KB	Output is correct
6	Correct	1 ms	780 KB	Output is correct
7	Correct	1 ms	1248 KB	Output is correct
8	Correct	0 ms	792 KB	Output is correct
9	Correct	0 ms	792 KB	Output is correct
10	Correct	0 ms	792 KB	Output is correct
11	Correct	0 ms	780 KB	Output is correct

Subtask #2

91.0 / 95.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	38 ms	7716 KB	Partially correct
2	Partially correct	43 ms	7740 KB	Partially correct
3	Partially correct	41 ms	7856 KB	Partially correct
4	Partially correct	38 ms	7824 KB	Partially correct
5	Partially correct	38 ms	7640 KB	Partially correct
6	Partially correct	38 ms	7728 KB	Partially correct
7	Partially correct	39 ms	7712 KB	Partially correct
8	Partially correct	38 ms	7712 KB	Partially correct
9	Partially correct	38 ms	8056 KB	Partially correct
10	Partially correct	38 ms	7640 KB	Partially correct
11	Partially correct	38 ms	8064 KB	Partially correct
12	Partially correct	41 ms	7588 KB	Partially correct
13	Partially correct	45 ms	7736 KB	Partially correct
14	Partially correct	45 ms	7736 KB	Partially correct
15	Partially correct	43 ms	7816 KB	Partially correct
16	Partially correct	43 ms	7728 KB	Partially correct
17	Partially correct	42 ms	7852 KB	Partially correct
18	Partially correct	42 ms	7732 KB	Partially correct
19	Partially correct	41 ms	7648 KB	Partially correct
20	Partially correct	39 ms	7796 KB	Partially correct
21	Partially correct	38 ms	7772 KB	Partially correct
22	Partially correct	43 ms	7872 KB	Partially correct
23	Partially correct	48 ms	7724 KB	Partially correct
24	Partially correct	37 ms	7736 KB	Partially correct
25	Partially correct	42 ms	7708 KB	Partially correct
26	Partially correct	44 ms	7828 KB	Partially correct
27	Partially correct	43 ms	7596 KB	Partially correct
28	Partially correct	42 ms	7820 KB	Partially correct
29	Partially correct	42 ms	7824 KB	Partially correct
30	Partially correct	43 ms	7724 KB	Partially correct
31	Partially correct	44 ms	7752 KB	Partially correct
32	Partially correct	39 ms	7732 KB	Partially correct
33	Partially correct	39 ms	7812 KB	Partially correct