oj.uz

Submission #1073172

# Submission time Handle Problem Language Result Execution time Memory
1073172 2024-08-24T09:58:53 Z sleepntsheep Ancient Machine (JOI21_ancient_machine) C++17
99 / 100
 129 ms 9664 KB 
#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);
}


#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3636 KB Output is correct
2 Correct 57 ms 3740 KB Output is correct
3 Correct 55 ms 3644 KB Output is correct
4 Correct 60 ms 3740 KB Output is correct
5 Correct 57 ms 3588 KB Output is correct
6 Correct 57 ms 3776 KB Output is correct
7 Correct 64 ms 3756 KB Output is correct
8 Correct 55 ms 3724 KB Output is correct
9 Correct 56 ms 3652 KB Output is correct
10 Correct 56 ms 3668 KB Output is correct
11 Correct 54 ms 3668 KB Output is correct

Subtask #2
94.0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 126 ms 9136 KB Partially correct
2 Partially correct 128 ms 9316 KB Partially correct
3 Partially correct 112 ms 9204 KB Partially correct
4 Partially correct 124 ms 9492 KB Partially correct
5 Partially correct 111 ms 9612 KB Partially correct
6 Partially correct 122 ms 9456 KB Partially correct
7 Partially correct 124 ms 9480 KB Partially correct
8 Partially correct 115 ms 9580 KB Partially correct
9 Partially correct 110 ms 9200 KB Partially correct
10 Partially correct 111 ms 9236 KB Partially correct
11 Partially correct 111 ms 9204 KB Partially correct
12 Partially correct 110 ms 9328 KB Partially correct
13 Partially correct 88 ms 9208 KB Partially correct
14 Partially correct 129 ms 9196 KB Partially correct
15 Partially correct 121 ms 9204 KB Partially correct
16 Partially correct 126 ms 9400 KB Partially correct
17 Partially correct 87 ms 9212 KB Partially correct
18 Partially correct 89 ms 9196 KB Partially correct
19 Partially correct 87 ms 9256 KB Partially correct
20 Partially correct 110 ms 9300 KB Partially correct
21 Partially correct 108 ms 9516 KB Partially correct
22 Partially correct 88 ms 9196 KB Partially correct
23 Partially correct 112 ms 9228 KB Partially correct
24 Partially correct 110 ms 9500 KB Partially correct
25 Partially correct 88 ms 9532 KB Partially correct
26 Partially correct 94 ms 9428 KB Partially correct
27 Partially correct 89 ms 9296 KB Partially correct
28 Partially correct 90 ms 9496 KB Partially correct
29 Partially correct 89 ms 9224 KB Partially correct
30 Partially correct 88 ms 9308 KB Partially correct
31 Partially correct 90 ms 9396 KB Partially correct
32 Partially correct 110 ms 9664 KB Partially correct
33 Partially correct 111 ms 9200 KB Partially correct