oj.uz

Submission #1073188

# Submission time Handle Problem Language Result Execution time Memory
1073188 2024-08-24T10:09:28 Z sleepntsheep Ancient Machine (JOI21_ancient_machine) C++17
100 / 100
 78 ms 9340 KB 
#include "Anna.h"
#include <cassert>
#include <vector>
#include <cstring>

using namespace std;

namespace A {
	constexpr int Ba = 1e8, Sz = 40, K = 500, KP = 349;
	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 < KP; ++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 = 500, KP = 349;
	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 += KP) {
		int fib[K];
		INT x = {0}, p2 = {0};
		p2[0] = 1;
		for (int j = 0; j < KP; ++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;

  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:64:6: warning: unused variable 'top' [-Wunused-variable]
   64 |  int top = 0;
      |      ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8872 KB Output is correct
2 Correct 78 ms 8760 KB Output is correct
3 Correct 51 ms 8752 KB Output is correct
4 Correct 56 ms 8708 KB Output is correct
5 Correct 59 ms 8956 KB Output is correct
6 Correct 70 ms 8748 KB Output is correct
7 Correct 53 ms 8800 KB Output is correct
8 Correct 67 ms 8880 KB Output is correct
9 Correct 50 ms 8848 KB Output is correct
10 Correct 59 ms 8768 KB Output is correct
11 Correct 68 ms 8772 KB Output is correct
12 Correct 60 ms 9120 KB Output is correct
13 Correct 53 ms 9144 KB Output is correct
14 Correct 64 ms 9028 KB Output is correct
15 Correct 57 ms 8880 KB Output is correct
16 Correct 72 ms 8764 KB Output is correct
17 Correct 68 ms 8760 KB Output is correct
18 Correct 62 ms 8980 KB Output is correct
19 Correct 60 ms 9040 KB Output is correct
20 Correct 60 ms 9340 KB Output is correct
21 Correct 59 ms 9308 KB Output is correct
22 Correct 52 ms 9136 KB Output is correct
23 Correct 56 ms 8788 KB Output is correct
24 Correct 64 ms 9036 KB Output is correct
25 Correct 59 ms 9020 KB Output is correct
26 Correct 53 ms 8912 KB Output is correct
27 Correct 56 ms 9120 KB Output is correct
28 Correct 61 ms 8804 KB Output is correct
29 Correct 60 ms 8872 KB Output is correct
30 Correct 68 ms 9112 KB Output is correct
31 Correct 60 ms 8920 KB Output is correct
32 Correct 53 ms 8944 KB Output is correct
33 Correct 69 ms 8824 KB Output is correct