oj.uz

Submission #1073175

# Submission time Handle Problem Language Result Execution time Memory
1073175 2024-08-24T09:59:52 Z sleepntsheep Ancient Machine (JOI21_ancient_machine) C++17
99 / 100
 61 ms 9060 KB 
#include "Anna.h"
#include <cassert>
#include <vector>
#include <cstring>

using namespace std;

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

	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 <= 200; ++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 < 200; ++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 += 200) {
		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;
	using INT = int[Sz];

	INT fib[201];
	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 <= 200; ++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[200]) {
		for (int i = 200; 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[200];
		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);
		}

    //cout << " : " <<x[0] << endl;
		lexicographic_order_to_fib(x, fib);
		for (int j = 0; j < 200; ++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);

//for(int i=0;i<20;++i)cout<<T[i]<<' ';cout<<endl; for(int i=0;i<100000;++i)assert((i&1)==T[i]);

  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:67:6: warning: unused variable 'top' [-Wunused-variable]
   67 |  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 20 ms 3752 KB Output is correct
3 Correct 20 ms 3736 KB Output is correct
4 Correct 20 ms 3732 KB Output is correct
5 Correct 20 ms 3736 KB Output is correct
6 Correct 20 ms 3748 KB Output is correct
7 Correct 20 ms 3752 KB Output is correct
8 Correct 20 ms 3748 KB Output is correct
9 Correct 28 ms 3688 KB Output is correct
10 Correct 19 ms 3744 KB Output is correct
11 Correct 20 ms 3740 KB Output is correct

Subtask #2
94.0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 53 ms 8992 KB Partially correct
2 Partially correct 53 ms 9028 KB Partially correct
3 Partially correct 49 ms 8824 KB Partially correct
4 Partially correct 54 ms 8876 KB Partially correct
5 Partially correct 53 ms 8784 KB Partially correct
6 Partially correct 52 ms 8812 KB Partially correct
7 Partially correct 53 ms 8728 KB Partially correct
8 Partially correct 56 ms 9060 KB Partially correct
9 Partially correct 53 ms 8820 KB Partially correct
10 Partially correct 52 ms 8784 KB Partially correct
11 Partially correct 49 ms 8852 KB Partially correct
12 Partially correct 51 ms 8776 KB Partially correct
13 Partially correct 51 ms 8760 KB Partially correct
14 Partially correct 61 ms 8780 KB Partially correct
15 Partially correct 57 ms 8900 KB Partially correct
16 Partially correct 57 ms 8756 KB Partially correct
17 Partially correct 52 ms 8848 KB Partially correct
18 Partially correct 56 ms 8724 KB Partially correct
19 Partially correct 51 ms 8688 KB Partially correct
20 Partially correct 49 ms 8896 KB Partially correct
21 Partially correct 50 ms 8760 KB Partially correct
22 Partially correct 55 ms 8808 KB Partially correct
23 Partially correct 52 ms 8772 KB Partially correct
24 Partially correct 55 ms 8848 KB Partially correct
25 Partially correct 51 ms 8768 KB Partially correct
26 Partially correct 52 ms 8820 KB Partially correct
27 Partially correct 49 ms 8808 KB Partially correct
28 Partially correct 50 ms 8684 KB Partially correct
29 Partially correct 49 ms 8680 KB Partially correct
30 Partially correct 49 ms 8768 KB Partially correct
31 Partially correct 55 ms 8704 KB Partially correct
32 Partially correct 49 ms 8868 KB Partially correct
33 Partially correct 49 ms 8876 KB Partially correct