Submission #388840

#	Time	Username	Problem	Language	Result	Execution time	Memory
388840		rama_pang	Ancient Machine (JOI21_ancient_machine)	C++17	0 / 100	34 ms	4584 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
  const int B = 100;
  const int F = 70;

  __int128_t Fibonacci(int n) {
    static vector<__int128_t> dp = {1, 2};
    while (dp.size() <= n) dp.emplace_back(end(dp)[-2] + end(dp)[-1]);
    return dp[n];
  }

  vector<int> CompressB(vector<int> A) {
    assert(A.size() == B);

    __int128_t H = 0;
    while (!A.empty()) {
      if (A.back() == 0) {
        A.pop_back();
      } else {
        H += Fibonacci(int(A.size()) - 1);
        A.pop_back();
        if (!A.empty()) {
          assert(A.back() == 0);
          A.pop_back();
        }
      }
    }

    vector<int> C;
    for (int i = 0; i < F; i++) {
      C.emplace_back(H & 1);
      H /= 2;
    }

    reverse(begin(C), end(C));
    assert(H == 0);
    assert(C.size() == F);

    return C;
  }

  vector<int> UncompressB(vector<int> C) {
    assert(C.size() == F);

    __int128_t H = 0;
    for (auto c : C) {
      H = H * 2 + c;
    }

    vector<int> A;
    for (int len = B; len > 0; ) {
      if (H >= Fibonacci(len - 1)) {
        H -= Fibonacci(len - 1);
        A.emplace_back(1); len--;
        if (len > 0) {
          A.emplace_back(0); len--;
        }
      } else {
        A.emplace_back(0); len--;
      }
    }

    reverse(begin(A), end(A));
    assert(H == 0);
    assert(A.size() == B);

    return A;
  }

  vector<int> Compress(int N, vector<int> A) {
    while (A.size() % B != 0) A.emplace_back(0);
    assert(A.size() % B == 0);

    vector<int> C;
    vector<int> cur;

    for (auto a : A) {
      cur.emplace_back(a);
      if (cur.size() == B) {
        auto res = CompressB(cur); cur.clear();
        for (auto c : res) {
          C.emplace_back(c);
        }
      }
    }

    assert(C.size() == A.size() / B * F);
    return C;
  }

  vector<int> Uncompress(int N, vector<int> C) {
    assert(C.size() % F == 0);

    vector<int> A;
    vector<int> cur;

    for (auto c : C) {
      cur.emplace_back(c);
      if (cur.size() == F) {
        auto res = UncompressB(cur); cur.clear();
        for (auto a : res) {
          A.emplace_back(a);
        }
      }
    }

    assert(A.size() == C.size() / F * B);
    while (A.size() > N) A.pop_back();

    return A;
  }

}

void Anna(int N, vector<char> S) {
  // Consider the following greedy algorithm:
  // First step:
  // Set last = -1
  // Identify the first character X, let it be i
  // Delete all characters [last + 1, i - 1] in reverse order.
  // Set last = i
  //
  // Second step:
  // Identify the first character Z after index last, let it be i
  // Delete all characters [last + 1, i - 1] in reverse order
  // Delete i
  // Set last = i
  //
  // It can be shown that this algorithm is optimal. Thus, we can
  // send a bitstring of length N to denote the first X, and then
  // consecutive Zs.
  //
  // To optimize, observe that if there is a string ZZ, we only need
  // to care about the first Z. This way, each consecutive Z has a gap
  // of 1. Thus, the number of sequences is F(N) = F(N - 2) + F(N - 1),
  // the fibonacci number. This converges to around 0.694 * N. Instead of
  // using big integers, we can use blocks of size B = 100 instead, for
  // 70000 total bits when N = 100000.

  bool X = 0;
  vector<int> str;
  for (int i = 0; i < N; i++) {
    if (!X && S[i] == 'X') {
      X = 1;
      str.emplace_back(1);
    } else if (X && S[i] == 'Z') {
      str.emplace_back(1);
    } else {
      str.emplace_back(0);
    }
  }

  for (int i = 1; i < N; i++) {
    if (str[i - 1] == 1 && str[i] == 1) {
      str[i] = 0;
    }
  }

  assert(Uncompress(N, Compress(N, str)) == str);
  for (auto s : Compress(N, str)) {
    Send(s);
  }
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
  const int B = 100;
  const int F = 70;

  __int128_t Fibonacci(int n) {
    static vector<__int128_t> dp = {1, 2};
    while (dp.size() <= n) dp.emplace_back(end(dp)[-2] + end(dp)[-1]);
    return dp[n];
  }

  vector<int> CompressB(vector<int> A) {
    assert(A.size() == B);

    __int128_t H = 0;
    while (!A.empty()) {
      if (A.back() == 0) {
        A.pop_back();
      } else {
        H += Fibonacci(int(A.size()) - 1);
        A.pop_back();
        if (!A.empty()) {
          assert(A.back() == 0);
          A.pop_back();
        }
      }
    }

    vector<int> C;
    for (int i = 0; i < F; i++) {
      C.emplace_back(H & 1);
      H /= 2;
    }

    reverse(begin(C), end(C));
    assert(H == 0);
    assert(C.size() == F);

    return C;
  }

  vector<int> UncompressB(vector<int> C) {
    assert(C.size() == F);

    __int128_t H = 0;
    for (auto c : C) {
      H = H * 2 + c;
    }

    vector<int> A;
    for (int len = B; len > 0; ) {
      if (H >= Fibonacci(len - 1)) {
        H -= Fibonacci(len - 1);
        A.emplace_back(1); len--;
        if (len > 0) {
          A.emplace_back(0); len--;
        }
      } else {
        A.emplace_back(0); len--;
      }
    }

    reverse(begin(A), end(A));
    assert(H == 0);
    assert(A.size() == B);

    return A;
  }

  vector<int> Compress(int N, vector<int> A) {
    while (A.size() % B != 0) A.emplace_back(0);
    assert(A.size() % B == 0);

    vector<int> C;
    vector<int> cur;

    for (auto a : A) {
      cur.emplace_back(a);
      if (cur.size() == B) {
        auto res = CompressB(cur); cur.clear();
        for (auto c : res) {
          C.emplace_back(c);
        }
      }
    }

    assert(C.size() == A.size() / B * F);
    return C;
  }

  vector<int> Uncompress(int N, vector<int> C) {
    assert(C.size() % F == 0);

    vector<int> A;
    vector<int> cur;

    for (auto c : C) {
      cur.emplace_back(c);
      if (cur.size() == F) {
        auto res = UncompressB(cur); cur.clear();
        for (auto a : res) {
          A.emplace_back(a);
        }
      }
    }

    assert(A.size() == C.size() / F * B);
    while (A.size() > N) A.pop_back();

    return A;
  }

}

void Bruno(int N, int L, vector<int> A) {
  vector<int> del(N);
  auto str = Uncompress(N, A);

  int firstX = N;
  for (int i = 0; i < N; i++) {
    if (str[i] == 1) {
      firstX = i;
      break;
    }
  }
  for (int i = firstX - 1; i >= 0; i--) {
    Remove(i);
    del[i] = 1;
  }

  for (int i = firstX + 1, j = firstX; i < N; i++) {
    if (str[i] == 1) {
      for (int k = i - 1; k >= j + 1; k--) {
        Remove(k);
        del[k] = 1;
      }
      Remove(i);
      del[i] = 1;
    }
  }

  for (int i = 0; i < N; i++) {
    if (!del[i]) {
      Remove(i);
      del[i] = 1;
    }
  }
}

Compilation message (stderr)

Anna.cpp: In function '__int128 {anonymous}::Fibonacci(int)':
Anna.cpp:11:22: warning: comparison of integer expressions of different signedness: 'std::vector<__int128>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |     while (dp.size() <= n) dp.emplace_back(end(dp)[-2] + end(dp)[-1]);
      |            ~~~~~~~~~~^~~~
Anna.cpp: In function 'std::vector<int> {anonymous}::Uncompress(int, std::vector<int>)':
Anna.cpp:111:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |     while (A.size() > N) A.pop_back();
      |            ~~~~~~~~~^~~

Bruno.cpp: In function '__int128 {anonymous}::Fibonacci(int)':
Bruno.cpp:11:22: warning: comparison of integer expressions of different signedness: 'std::vector<__int128>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |     while (dp.size() <= n) dp.emplace_back(end(dp)[-2] + end(dp)[-1]);
      |            ~~~~~~~~~~^~~~
Bruno.cpp: In function 'std::vector<int> {anonymous}::Uncompress(int, std::vector<int>)':
Bruno.cpp:111:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |     while (A.size() > N) A.pop_back();
      |            ~~~~~~~~~^~~
Bruno.cpp: At global scope:
Bruno.cpp:73:15: warning: 'std::vector<int> {anonymous}::Compress(int, std::vector<int>)' defined but not used [-Wunused-function]
   73 |   vector<int> Compress(int N, vector<int> A) {
      |               ^~~~~~~~

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