답안 #966458

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

Anna

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

using ull = unsigned long long;

#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<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 = 91;

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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	792 KB	Output is correct
5	Correct	0 ms	780 KB	Output is correct
6	Correct	0 ms	788 KB	Output is correct
7	Correct	0 ms	776 KB	Output is correct
8	Correct	1 ms	976 KB	Output is correct
9	Correct	0 ms	780 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	41 ms	7696 KB	Partially correct
2	Partially correct	38 ms	7732 KB	Partially correct
3	Partially correct	38 ms	7820 KB	Partially correct
4	Partially correct	40 ms	7808 KB	Partially correct
5	Partially correct	37 ms	7824 KB	Partially correct
6	Partially correct	41 ms	7948 KB	Partially correct
7	Partially correct	40 ms	7608 KB	Partially correct
8	Partially correct	37 ms	7748 KB	Partially correct
9	Partially correct	38 ms	7708 KB	Partially correct
10	Partially correct	38 ms	7724 KB	Partially correct
11	Partially correct	36 ms	7648 KB	Partially correct
12	Partially correct	39 ms	7712 KB	Partially correct
13	Partially correct	42 ms	7820 KB	Partially correct
14	Partially correct	44 ms	7776 KB	Partially correct
15	Partially correct	44 ms	7780 KB	Partially correct
16	Partially correct	47 ms	7972 KB	Partially correct
17	Partially correct	48 ms	7756 KB	Partially correct
18	Partially correct	41 ms	7636 KB	Partially correct
19	Partially correct	41 ms	7764 KB	Partially correct
20	Partially correct	37 ms	7756 KB	Partially correct
21	Partially correct	40 ms	7764 KB	Partially correct
22	Partially correct	45 ms	7948 KB	Partially correct
23	Partially correct	36 ms	7752 KB	Partially correct
24	Partially correct	36 ms	7776 KB	Partially correct
25	Partially correct	41 ms	7728 KB	Partially correct
26	Partially correct	42 ms	8248 KB	Partially correct
27	Partially correct	40 ms	7788 KB	Partially correct
28	Partially correct	43 ms	7764 KB	Partially correct
29	Partially correct	46 ms	7704 KB	Partially correct
30	Partially correct	42 ms	7780 KB	Partially correct
31	Partially correct	41 ms	7688 KB	Partially correct
32	Partially correct	40 ms	7736 KB	Partially correct
33	Partially correct	39 ms	7740 KB	Partially correct