Submission #1160779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160779		fryingduc	Ancient Machine (JOI21_ancient_machine)	C++20	100 / 100	41 ms	6372 KiB

Anna

#include "Anna.h"
#include "bits/stdc++.h"

using namespace std;

namespace {
  template<class T>
  ostream &operator << (ostream &os, vector<T> v) {
    int D = v.size();
    os << "{";
    for (int i = 0; i < D; ++i) {
      os << (i ? ", " : "") << v[i];
    }
    return os << "}";
  }
  
  void __print() {
      cerr << "] " << endl;
  }
  
  template<class T, class... V>
  void __print(T t, V... v) {
      cerr << t;
      if (sizeof...(v)) {
          cerr << ", ";
      }
      __print(v...);
  }
  
  #define debug(x...)  cerr << "[" << #x << "] = ["; __print(x);
}

void Anna(int N, vector<char> S) {
  vector<bool> s(N, 0);
  bool flag = 0;
  int cnt = 0;
  for (int i = 0; i < (int)S.size(); ++i) { 
    if (S[i] == 'X' and !flag) {
      flag = 1;
      s[i] = 1;
      int cur = 1;
      while (i + cur < (int)S.size() and S[i + cur]  == 'Z') ++cur;
      if (cur > 1) {
        i = i + cur - 1;
        cnt = cur - 1;
      }
    } else if (S[i] == 'Z' and flag) {
      int cur = i;
      while (cur < (int)S.size() and S[cur] == 'Z') {
        ++cur;
      }
      s[cur - 1] = 1;
      i = cur - 1;
    }
  }
  vector<long long> f(80);
  f[1] = 1;
  for (int i = 2; i < 80; ++i) {
    f[i] = f[i - 1] + f[i - 2];
  }
  int BIT = 44;
  int LEN = 63;
//  debug(s, cnt);
  for (int i = 0; i < N; i += LEN) {
    int r = min(N - 1, i + LEN - 1);
    long long cur = 0;
    for (int j = i; j <= r; ++j) {
      if (s[j]) {
//        debug(j, f[r - j + 2]);
        cur += f[r - j + 2];
      }
    }
    if (__lg(cur) >= BIT) {
      debug(cur, __lg(cur));
    }
    for (int j = 0; j < BIT; ++j) {
      Send(cur >> j & 1);
    }
  }
  for (int i = 0; i < 18; ++i) {
    Send(cnt >> i & 1);
  }
}

Bruno

#include "Bruno.h"
#include "bits/stdc++.h"

using namespace std;

namespace {
  template<class T>
  ostream &operator << (ostream &os, vector<T> v) {
    int D = v.size();
    os << "{";
    for (int i = 0; i < D; ++i) {
      os << (i ? ", " : "") << v[i];
    }
    return os << "}";
  }
  
  void __print() {
      cerr << "] " << endl;
  }
  
  template<class T, class... V>
  void __print(T t, V... v) {
      cerr << t;
      if (sizeof...(v)) {
          cerr << ", ";
      }
      __print(v...);
  }
  
  #define debug(x...)  cerr << "[" << #x << "] = ["; __print(x);
}

void Bruno(int N, int L, vector<int> A) {
  vector<int> id;
  vector<long long> f(80);
  f[1] = 1;
  for (int i = 2; i < 80; ++i) {
    f[i] = f[i - 1] + f[i - 2];
  }
  int BIT = 44;
  int LEN = 63;
  int cur_id = 0;
  vector<bool> s(N + 70, 0);
  for (int i = 0; i + BIT - 1 < L; i += BIT) {
    long long x = 0;
    for (int j = i; j < i + BIT; ++j) {
      if (A[j]) {
        x |= (1ll << (j - i));
      }
    }
    int sz = min(N - 1, cur_id + LEN - 1);
    for (int j = cur_id; j <= sz; ++j) {
      if (x >= f[sz - j + 2]) {
        s[j] = 1;
//        debug(x, f[sz - j + 2], j);
        x -= f[sz - j + 2];
      }
    }
    cur_id = sz + 1;
  }
  int cnt = 0;
  for (int i = 0; i < 18; ++i) {
    if (A[L - 18 + i]) {
      cnt |= (1 << i);
    }
  }
//  debug(s, cnt);
  for (int i = 0; i < N; ++i) {
    if (s[i]) {
      id.push_back(i);
    }
  }
  if (id.empty()) {
    for (int i = 0; i < N; ++i) {
      Remove(i);
    }
    return;
  }
//  debug(id, cnt);
  for (int i = 0; i < id[0]; ++i) {
    Remove(i);
  }
  for (int i = id[0] + 1; i <= id[0] + cnt; ++i) {
    Remove(i);
  }
  int mem = id[0];
  id[0] += cnt;
  for (int i = id.back() + 1; i < N; ++i) {
    Remove(i);
  }
  for (int i = 1; i < (int)id.size(); ++i) {
    for (int j = id[i] - 1; j > id[i - 1]; --j) {
      Remove(j);
    }
    Remove(id[i]);
  }
  Remove(mem);
}

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