oj.uz

Submission #940046

# Submission time Handle Problem Language Result Execution time Memory
940046 2024-03-07T04:45:16 Z lamter Ancient Machine (JOI21_ancient_machine) C++17
0 / 100
 45 ms 8248 KB 
#include "Anna.h"
#include <bits/stdc++.h>

void Anna(int n, std::vector <char> a) {
	const int kFibonacci = 63;
	const int kLog = 44;
	std::vector <long long> dp(kFibonacci);
	dp[0] = 1;
	dp[1] = 2;
	for (int i = 2; i < kFibonacci; i += 1) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	std::vector <int> b(n);
	bool found = 0;
	for (int i = 0; i < n; i += 1) {
		int bit = 0;

		if (not found and a[i] == 'X') {
			bit = 1;
			found = true;
		}

		if (found and a[i] == 'Z' and (i + 1 == n or a[i + 1] != 'Z') and (b[i - 1] != 1)) {
			bit = 1;
		}

		b[i] = bit;
	}

	auto SendEncode = [&] (std::vector <int> z) -> void {
		long long x = 0;
		for (int i = 0; i < kFibonacci; i += 1) {
			x += z[i] ? dp[i] : 0;
		}
		for (int i = 0; i < kLog; i += 1) {
			Send((x >> i) & 1);
		}
	};

	while (b.size() % kFibonacci)
		b.push_back(0);
	for (int l = 0, r = kFibonacci; r <= n; l += kFibonacci, r += kFibonacci) {
		SendEncode(std::vector <int> (b.begin() + l, b.begin() + r));
	}
}

#include "Bruno.h"
#include <bits/stdc++.h>

void Bruno(int n, int, std::vector <int> a) {
	const int kFibonacci = 63;
	const int kLog = 44;
	std::vector <long long> dp(kFibonacci);
	dp[0] = 1;
	dp[1] = 2;
	for (int i = 2; i < kFibonacci; i += 1) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	std::vector <int> posOne;

	for (int l = 0, r = kLog; r <= (int) a.size(); l += kLog, r += kLog) {
		long long x = 0;
		for (int i = l; i < r; i += 1)
			x += (1LL * a[i]) << (i - l);
		for (int i = r - 1; i >= l; i -= 1) {
			if (x >= dp[i - l]) {
				x -= dp[i - l];
				posOne.push_back(i);
			}
		}
	}
	std::sort(posOne.begin(), posOne.end());

	if (posOne.size() < 2) {
		for (int i = 0; i < n; i += 1)
			Remove(i);
		return;
	}
	int x = posOne[0];
	for (int i = 0; i < x; i += 1) {
		Remove(i);
	}
	for (int i = 0; i + 1 < (int) posOne.size(); i += 1) {
		for (int j = posOne[i + 1] - 1; j > posOne[i]; j -= 1)
			Remove(j);
		Remove(posOne[i + 1]);
	}
	for (int j = posOne.back() + 1; j < n; j += 1) {
		Remove(j);
	}
	Remove(x);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 796 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 8248 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -