Submission #1054005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054005		awu	Ancient Machine (JOI21_ancient_machine)	C++17	97 / 100	57 ms	16136 KiB

Anna

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

// #define int long long
#define ll long long
// #define double long double
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(...) [&](decltype(__VA_ARGS__) _x){cerr << #__VA_ARGS__ << " = " << _x << endl; return _x;}(__VA_ARGS__)
using pii = pair<int, int>;
const ll inf = 1ll << 60;
// const int inf = 1 << 30;
const int MOD = 1e9 + 7;

template <typename T, typename U>
ostream& operator<<(ostream& out, pair<T, U> p) {
  out << "(" << p.f << ", " << p.s << ")";
  return out;
}
template <typename T, typename = decltype(begin(declval<T>()))>
typename enable_if<!is_same<T, string>::value, ostream&>::type operator<<(ostream& out, const T& a) {
  string dlm = "";
  out << "{";
  for(auto& i : a) {
    out << dlm << i;
    dlm = ", ";
  }
  return out << "}";
}
void my_assert(bool b) {
  if(!b) {
    cerr << "Assertion failed" << endl;
    *((volatile int*)0);
  }
}
#undef assert
#define assert my_assert

const int X = 4;

#include "Anna.h"
void Anna(int n, vector<char> s) {
  vector<int> b;
  b.push_back(1);
  int x = -1, z = -1;
  for(int i = 0; i < n; i++) {
    if(s[i] == 'X' && x == -1) x = i;
    if(s[i] == 'Z') z = i;
  }
  if(x == -1 || z == -1 || x > z) return;
  for(int i = 0; i < n; i++) {
    if(i < x || i > z) b.push_back(0);
    else if(i == x || i == z) b.push_back(1);
    else if(i < n - 1 && s[i] == 'Y' && s[i + 1] == 'X') {
      b.push_back(1);
      i++;
    } else b.push_back(0);
  }
  while(b.back() == 0) b.pop_back();
  // debug(b);
  int j = 0;
  vector<int> c;
  while(j < b.size() - 1) {
    int cnt = -1;
    do {
      cnt++;
      j++;
    } while(b[j] != 1);
    c.push_back(cnt);
  }
  // debug(c);
  vector<int> best;
  for(int i = 1; i <= 1 << X; i++) {
    vector<int> a;
    for(int j = 0; j < X; j++) {
      a.push_back(((i - 1) >> j) & 1);
    }
    int m = (1 << i) - 1;
    auto append = [&](int v) {
      for(int j = 0; j < i; j++) {
        a.push_back((v >> j) & 1);
      }
    };
    for(auto j : c) {
      append(j % m);
      for(int k = 0; k < j / m; k++) {
        append(m);
      }
    }
    if(best.empty() || a.size() < best.size()) best = a;
  }
  for(auto i : best) {
    Send(i);
  }
}

Bruno

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

// #define int long long
#define ll long long
// #define double long double
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(...) [&](decltype(__VA_ARGS__) _x){cerr << #__VA_ARGS__ << " = " << _x << endl; return _x;}(__VA_ARGS__)
using pii = pair<int, int>;
const ll inf = 1ll << 60;
// const int inf = 1 << 30;
const int MOD = 1e9 + 7;

template <typename T, typename U>
ostream& operator<<(ostream& out, pair<T, U> p) {
  out << "(" << p.f << ", " << p.s << ")";
  return out;
}
template <typename T, typename = decltype(begin(declval<T>()))>
typename enable_if<!is_same<T, string>::value, ostream&>::type operator<<(ostream& out, const T& a) {
  string dlm = "";
  out << "{";
  for(auto& i : a) {
    out << dlm << i;
    dlm = ", ";
  }
  return out << "}";
}
void my_assert(bool b) {
  if(!b) {
    cerr << "Assertion failed" << endl;
    *((volatile int*)0);
  }
}
#undef assert
#define assert my_assert

const int X = 4;

#include "Bruno.h"
void Bruno(int n, int l, vector<int> a) {
  if(l == 0) {
    for(int i = 0; i < n; i++) {
      Remove(i);
    }
    return;
  }
  // debug(a);
  int i = 0;
  for(int j = 0; j < X; j++) {
    i |= a[j] << j;
  }
  i++;
  int m = (1 << i) - 1;
  a = vector<int>(a.begin() + X, a.end());
  vector<int> b;
  for(int j = 0; j < a.size(); j += i) {
    int v = 0;
    for(int k = 0; k < i; k++) {
      v |= a[j + k] << k;
    }
    if(v != m) {
      b.push_back(1);
    }
    for(int k = 0; k < v; k++) {
      b.push_back(0);
    }
  }
  vector<int> r;
  int oc = 0;
  int x = -1, z = -1;
  for(auto j : b) {
    if(j == 1) {
      if(oc == 1) {
        x = r.size();
        r.push_back(1);
      } else if(oc >= 2) {
        r.push_back(1);
        r.push_back(1);
      }
      oc++;
    } else {
      r.push_back(0);
    }
  }
  // debug(r);
  z = r.size();
  r.push_back(1);
  r.resize(n, 0);
  // debug(r);
  for(int i = 0; i < n; i++) {
    if(r[i] == 0) Remove(i);
  }
  for(int i = n - 1; i >= 0; i--) {
    if(i == x || i == z) continue;
    if(r[i] == 1) Remove(i);
  }
  // debug(x);
  // debug(z);
  Remove(x);
  Remove(z);
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:65:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   while(j < b.size() - 1) {
      |         ~~^~~~~~~~~~~~~~

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int j = 0; j < a.size(); j += i) {
      |                  ~~^~~~~~~~~~

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