Submission #1073167

#TimeUsernameProblemLanguageResultExecution timeMemory
1073167sleepntsheepAncient Machine (JOI21_ancient_machine)C++17
0 / 100
119 ms9004 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) { 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 = 0; i < N; ++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++]) 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 (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;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...