Submission #1073099

#TimeUsernameProblemLanguageResultExecution timeMemory
1073099sleepntsheepAncient Machine (JOI21_ancient_machine)C++17
0 / 100
101 ms5440 KiB
#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) { for (int carry = 0, j = Sz - 1; j >= 0; --j) carry = (a[j] += carry * Ba) & 1, a[j] /= 2; } } void Anna(int N, std::vector<char> S) { using namespace A; A_init(); vector<int> T(100000); int sum = 0; 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 < N - 1; ++i) if (T[i] == 1) { T[i + 1] = 0; break; } for(int i=0;i<100000;++i)T[i]=i&1; 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); } }
#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, 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); /* # 200-digit fib <= 2^140 */ for (int i = 0; i < L; 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); } lexicographic_order_to_fib(x, fib); for (int j = 0; j < 200; ++j) T.push_back(fib[j]); } int top = 0; assert(A.size() == 70000); assert(T.size() == 100000); 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 sum = 0, i = 0; i < 100000; sum += T[i++]) { if (T[i] == 1) { if (sum) { while (top and T[stk[top - 1]] == 0) REMOVE(stk[--top]); REMOVE(i); } } else if (sum) stk[top++] = i; } for (int i = 0; i < N; ++i) REMOVE(i); }

Compilation message (stderr)

Bruno.cpp: In function 'void B::Add(int*, int*)':
Bruno.cpp:17:26: warning: 'carry' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |    carry = (a[i] += b[i] + carry) / Ba, a[i] %= Ba;
      |                     ~~~~~^~~~~~~
Bruno.cpp: In function 'void B::B_init()':
Bruno.cpp:17:26: warning: 'carry' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |    carry = (a[i] += b[i] + carry) / Ba, a[i] %= Ba;
      |                     ~~~~~^~~~~~~
Bruno.cpp:16:12: note: 'carry' was declared here
   16 |   for (int carry, i = 0; i < Sz; ++i)
      |            ^~~~~
Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:17:26: warning: 'carry' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |    carry = (a[i] += b[i] + carry) / Ba, a[i] %= Ba;
      |                     ~~~~~^~~~~~~
Bruno.cpp:16:12: note: 'carry' was declared here
   16 |   for (int carry, i = 0; i < Sz; ++i)
      |            ^~~~~
Bruno.cpp:17:26: warning: 'carry' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |    carry = (a[i] += b[i] + carry) / Ba, a[i] %= Ba;
      |                     ~~~~~^~~~~~~
Bruno.cpp:16:12: note: 'carry' was declared here
   16 |   for (int carry, i = 0; i < Sz; ++i)
      |            ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...