Submission #1073172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073172		sleepntsheep	Ancient Machine (JOI21_ancient_machine)	C++17	99 / 100	129 ms	9664 KiB

Anna

#include "Anna.h"
#include <algorithm>
#include <cassert>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>

using namespace std;

namespace A {
	constexpr int Ba = 1e8, Sz = 150;
	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;

  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;
    //cout<<S[i];
  }
  //cout<<endl;

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

  //for(int i=0;i<100000;++i)T[i]=i&1;

  int nxt = 0;
	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);
    //cout << x[0] << endl;
		for (int j = 0; j < 140; ++j)
			Send(x[0] & 1), Half(x);
	}
  Send(nxt);
}

Bruno

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

namespace B {
	constexpr int Ba = 1e8, Sz = 150;
	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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 94 / 95