Submission #386377

#	Time	Username	Problem	Language	Result	Execution time	Memory
386377		Mamnoon_Siam	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	76 ms	8508 KiB

Anna

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

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

namespace {

ll dp[100];

vi int_to_zeckendorf(ll x) {
  vi ret;
  for(int i = 63-1; i >= 0; --i) {
    ret.emplace_back(dp[i] <= x);
    if(dp[i] <= x) x -= dp[i];
  }
  return ret;
}
ll zeckendorf_to_int(vi v) {
  ll ret = 0;
  for(int i = 0; i < 63; ++i) {
    ret += v[i] ? dp[i] : 0;
  }
  return ret;
}

void print(int x) { cerr << x << endl; }
void print(vi v) {
  for(int x : v) cerr << x << ' ';
  cerr << endl;
}

#ifdef LOCAL
#define debug(v) cerr << #v << " = "; print(v);
#else
#define debug(v)
#endif

}

void Anna(int N, std::vector<char> S) {
  dp[0] = 1, dp[1] = 2;
  for(int i = 2; i < 63; ++i) {
     dp[i] = dp[i-1] + dp[i-2];
  }
  S.resize(((sz(S)-1)/63+1)*63);
  for(int i = N; i < sz(S); ++i) S[i] = 'Y';


  debug(sz(S));


  vi mark(sz(S), 0);
  vi seq;

  int first_x = int(find(all(S), 'X') - S.begin());

  for(int i = 0; i < 17; ++i)
    seq.emplace_back(first_x >> i & 1);

  for(int i = first_x; i < sz(S); ++i) {
    if(S[i] == 'Z') mark[i] = 1;
  }

  for(int i = 1; i < sz(mark); ++i)
    if(mark[i-1] and !mark[i]) {
      for(int j = i-2; j >= 0 and mark[j]; --j)
        mark[j] = 0;
    }

  debug(mark);

  for(int i = 0; i < sz(S); i += 63) {
    ll x = zeckendorf_to_int(vi(mark.begin()+i, mark.begin()+i+63));
    for(int j = 0; j < 44; ++j) {
      seq.emplace_back(x >> j & 1);
    }
  }

  debug(vi(seq.begin()+17, seq.end()));

  for(int i = 0; i < sz(seq); ++i) Send(seq[i]);
}

Bruno

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

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

namespace {

ll dp[100];

vi int_to_zeckendorf(ll x) {
  vi ret;
  for(int i = 63-1; i >= 0; --i) {
    ret.emplace_back(dp[i] <= x);
    if(dp[i] <= x) x -= dp[i];
  }
  return ret;
}
ll zeckendorf_to_int(vi v) {
  ll ret = 0;
  for(int i = 0; i < 63; ++i) {
    ret += v[i] ? dp[i] : 0;
  }
  return ret;
}

void print(int x) { cerr << x << endl; }
void print(vi v) {
  for(int x : v) cerr << x << ' ';
  cerr << endl;
}

#ifdef LOCAL
#define debug(v) cerr << #v << " = "; print(v);
#else
#define debug(v)
#endif

}  // namespace

void Bruno(int N, int L, std::vector<int> A) {
  dp[0] = 1, dp[1] = 2;
  for(int i = 2; i < 63; ++i) {
     dp[i] = dp[i-1] + dp[i-2];
  }

  int first_x = 0;
  for(int i = 0; i < 17; ++i)
    first_x |= A[i] << i;

  A.erase(A.begin(), A.begin()+17);

  vi AA;

  for(int i = 0; i < sz(A); i += 44) {
    ll val = 0;
    for(int j = i; j < i+44; ++j) {
      val |= ll(A[j]) << (j-i);
    }
    vi tmp = int_to_zeckendorf(val);
    reverse(all(tmp));
    AA.insert(AA.end(), all(tmp));
  }

  // reverse(all(AA));

  debug(AA);

  // AA.resize(N);

  // debug(AA);

  for(int i = 0; i < min(N, first_x); ++i) {
    Remove(i);
  }

  if(first_x < N) {
    int prv = first_x;
    for(int i = first_x+1; i < N; ++i) {
      if(AA[i]) {
        for(int j = i-1; j > prv; --j) {
          Remove(j);
        }
        Remove(i);
        prv = i;
      }
    }
    Remove(first_x);
    for(int i = prv+1; i < N; ++i) {
      Remove(i);
    }
  }
}

Compilation message (stderr)

Anna.cpp:34:6: warning: 'void {anonymous}::print(vi)' defined but not used [-Wunused-function]
   34 | void print(vi v) {
      |      ^~~~~
Anna.cpp:33:6: warning: 'void {anonymous}::print(int)' defined but not used [-Wunused-function]
   33 | void print(int x) { cerr << x << endl; }
      |      ^~~~~
Anna.cpp:17:4: warning: 'vi {anonymous}::int_to_zeckendorf(ll)' defined but not used [-Wunused-function]
   17 | vi int_to_zeckendorf(ll x) {
      |    ^~~~~~~~~~~~~~~~~

Bruno.cpp:34:6: warning: 'void {anonymous}::print(vi)' defined but not used [-Wunused-function]
   34 | void print(vi v) {
      |      ^~~~~
Bruno.cpp:33:6: warning: 'void {anonymous}::print(int)' defined but not used [-Wunused-function]
   33 | void print(int x) { cerr << x << endl; }
      |      ^~~~~
Bruno.cpp:25:4: warning: 'll {anonymous}::zeckendorf_to_int(vi)' defined but not used [-Wunused-function]
   25 | ll zeckendorf_to_int(vi v) {
      |    ^~~~~~~~~~~~~~~~~

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