Submission #1073182

#TimeUsernameProblemLanguageResultExecution timeMemory
1073182sleepntsheepAncient Machine (JOI21_ancient_machine)C++17
99 / 100
68 ms9000 KiB
#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 (stderr)

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;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...