oj.uz

Submission #1073182

# Submission time Handle Problem Language Result Execution time Memory
1073182 2024-08-24T10:04:57 Z sleepntsheep Ancient Machine (JOI21_ancient_machine) C++17
99 / 100
 68 ms 9000 KB 
#include "Anna.h"
#include <cassert>
#include <vector>
#include <cstring>

using namespace std;

namespace A {
	constexpr int Ba = 1e8, Sz = 40, K = 200;
	using INT = int[Sz];
	INT fib[K + 1];

	void Add(INT a, INT b) {
		for (int carry = 0, i = 0; i < Sz; ++i)
			carry = (a[i] += b[i] + carry) / Ba, a[i] %= Ba;
	}

	void A_init() {
		memset(fib, 0, sizeof fib);
		fib[0][0] = fib[1][0] = 1;
		for (int i = 2; i <= K; ++i)
			memcpy(fib[i], fib[i - 2], sizeof fib[0]), Add(fib[i], fib[i - 1]);
	}

	void order(int *a, INT out) {
		memset(out, 0, sizeof *out * Sz);
		for (int i = 0; i < K; ++i)
			if (a[i])
				Add(out, fib[i + 1]);
	}
	void Half(INT a) {
    int carry = 0, j;
    for (j = Sz - 1; j >= 0; --j) {
      a[j] += carry * Ba;
      carry = a[j] & 1;
      a[j] /= 2;
    }
	}
}

void Anna(int N, std::vector<char> S) {
	using namespace A;
	A_init();
	vector<int> T(100000);
	int sum = 0;
  int last_z = -2;
  int nxt = 0;

  for (int i = N - 1; i >= 0; --i) {
    if (S[i] == 'Z' and last_z == i + 1) S[i] = '$';
    if (S[i] == 'Z') last_z = i;
  }

	for (int i = 0; i < N; sum += T[i++])
    T[i] = ((S[i] == 'X' and not sum) or (S[i] == 'Z' and sum));

	for (int i = 0; i < N - 1; ++i) if (T[i] == 1) {
    nxt = T[i + 1];
    T[i + 1] = 0;
		break;
	}

	for (int i = 0; i < 100000; i += K) {
		static INT x;
		order(T.data() + i, x);
		for (int j = 0; j < 140; ++j)
			Send(x[0] & 1), Half(x);
	}
  Send(nxt);
}


#include "Bruno.h"
#include <cassert>
#include <cstring>
#include <vector>
using namespace std;

namespace B {
	constexpr int Ba = 1e8, Sz = 40, K = 200;
	using INT = int[Sz];

	INT fib[K + 1];
	void Add(INT a, INT b) {
		for (int carry = 0, i = 0; i < Sz; ++i) {
			carry = (a[i] += b[i] + carry) / Ba, a[i] %= Ba;
    }
	}
	void Sub(INT a, INT b) {
		for (int i = 0; i < Sz; ++i)
			if ((a[i] -= b[i]) < 0) a[i] += Ba, a[i + 1]--;
	}
	int Le(INT a, INT b) {
		for (int i = Sz - 1; i >= 0; --i) if (a[i] != b[i]) return a[i] < b[i] ? -1 : 1;
		return 0;
	}

	void B_init() {
		memset(fib, 0, sizeof fib);
		fib[0][0] = fib[1][0] = 1;
		for (int i = 2; i <= K; ++i) memcpy(fib[i], fib[i - 2], sizeof fib[0]), Add(fib[i], fib[i - 1]);
	}

	void lexicographic_order_to_fib(INT ord, int out[K]) {
		for (int i = K; i >= 1; --i) {
			if (-1 != Le(ord, fib[i]))
				out[i - 1] = 1, Sub(ord, fib[i]);
			else
				out[i - 1] = 0;
		}
	}
}

void Bruno(int N, int L, vector<int> A) {
	using namespace B;
	B_init();
	vector<int> T, stk(100000);

  int nxt = A.back();
  A.pop_back();
	for (int i = 0; i < (int)A.size(); i += 140) {
		int fib[K];
		INT x = {0}, p2 = {0};
		p2[0] = 1;
		for (int j = 0; j < 140; ++j) {
			if (A[i + j])
				Add(x, p2);
			Add(p2, p2);
		}

		lexicographic_order_to_fib(x, fib);
		for (int j = 0; j < K; ++j)
			T.push_back(fib[j]);
	}

  for (int i = 0; i + 1 < 100000; ++i) if (T[i] == 1) { T[i + 1] = nxt; break; }

	int top = 0;
	assert(A.size() == 70000);
	assert(T.size() == 100000);

  vector<int> Dead(N);
	auto REMOVE = [&](int i) { if (i < N and not Dead[i]) Dead[i] = 1, Remove(i); };

  for (int lst = -1, fst = -1, i = 0; i < N; ++i) {
    if (!T[i])continue;
    if (!~fst) {
      fst = i, lst = i;
    } else {
      for (int j = i - 1; j > lst; --j) REMOVE(j);
      lst = i;
      REMOVE(i);
    }
  }

  for (int i = 0; i < N; ++i) REMOVE(i);
}

Compilation message

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:66:6: warning: unused variable 'top' [-Wunused-variable]
   66 |  int top = 0;
      |      ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3752 KB Output is correct
2 Correct 24 ms 3756 KB Output is correct
3 Correct 20 ms 3740 KB Output is correct
4 Correct 19 ms 3740 KB Output is correct
5 Correct 19 ms 3736 KB Output is correct
6 Correct 20 ms 3756 KB Output is correct
7 Correct 20 ms 3756 KB Output is correct
8 Correct 22 ms 3720 KB Output is correct
9 Correct 20 ms 3744 KB Output is correct
10 Correct 22 ms 3744 KB Output is correct
11 Correct 22 ms 3744 KB Output is correct

Subtask #2
94.0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 50 ms 8848 KB Partially correct
2 Partially correct 49 ms 8724 KB Partially correct
3 Partially correct 53 ms 8904 KB Partially correct
4 Partially correct 51 ms 8880 KB Partially correct
5 Partially correct 51 ms 8940 KB Partially correct
6 Partially correct 53 ms 8860 KB Partially correct
7 Partially correct 53 ms 9000 KB Partially correct
8 Partially correct 51 ms 8820 KB Partially correct
9 Partially correct 51 ms 8912 KB Partially correct
10 Partially correct 55 ms 8880 KB Partially correct
11 Partially correct 51 ms 8756 KB Partially correct
12 Partially correct 52 ms 8860 KB Partially correct
13 Partially correct 55 ms 8856 KB Partially correct
14 Partially correct 68 ms 8760 KB Partially correct
15 Partially correct 57 ms 8912 KB Partially correct
16 Partially correct 63 ms 8852 KB Partially correct
17 Partially correct 54 ms 8892 KB Partially correct
18 Partially correct 52 ms 8844 KB Partially correct
19 Partially correct 52 ms 8768 KB Partially correct
20 Partially correct 49 ms 8916 KB Partially correct
21 Partially correct 52 ms 8820 KB Partially correct
22 Partially correct 53 ms 8764 KB Partially correct
23 Partially correct 53 ms 8772 KB Partially correct
24 Partially correct 54 ms 8888 KB Partially correct
25 Partially correct 50 ms 8816 KB Partially correct
26 Partially correct 50 ms 8776 KB Partially correct
27 Partially correct 54 ms 8764 KB Partially correct
28 Partially correct 53 ms 8820 KB Partially correct
29 Partially correct 57 ms 8752 KB Partially correct
30 Partially correct 52 ms 8816 KB Partially correct
31 Partially correct 61 ms 8764 KB Partially correct
32 Partially correct 54 ms 8760 KB Partially correct
33 Partially correct 52 ms 8780 KB Partially correct