Submission #708763

#	Time	Username	Problem	Language	Result	Execution time	Memory
708763		ntdxl05	Ancient Machine (JOI21_ancient_machine)	C++17	30 / 100	102 ms	11112 KiB

Anna

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

namespace {

int variable_example = 0;

}

void Anna(int N, std::vector<char> S) {
const int dc[] = {'X', 'Y', 'Z'};
int idc[256];
  for (int i = 0; i < 3; i++) idc[dc[i]] = i;
  for (int i = 0; i < N; i++) {
    Send(idc[S[i]] >> 1 & 1);
    Send(idc[S[i]] & 1);
  }
}

Bruno

#include <bits/stdc++.h>
#include "Bruno.h"
#include <vector>

using namespace std;

namespace {

// int variable_example = 0;

const int inf = 1e9;

int FunctionExample(int P) { return 1 - P; }

template<class U, class V>
bool minz(U &a, V b) {
  if (a > b) return a = b, 1;
  return 0;
}
template<class U, class V>
bool maxz(U &a, V b) {
  if (a < b) return a = b, 1;
  return 0;
}

}  // namespace

void Bruno(int N, int L, std::vector<int> A) {
const int dc[] = {'X', 'Y', 'Z'};
int idc[256];
  for (int i = 0; i < L; i++) {
    // variable_example += FunctionExample(A[i]);
  }

  vector<char> S(N);
  for (int i = 0; i < N; i++) S[i] = dc[A[i << 1] << 1 | A[i << 1 | 1]];
  // vector<int> dp(1 << N, -inf), trc(1 << N, -1);
  // dp[0] = 0;
  // for (int msk = 0; msk < (1 << N) - 1; msk++) {
  //   vector<int> b(N);
  //   for (int i = 0; i < N; i++) b[i] = msk >> i & 1;
  //   for (int i = 0; i < N; i++) {
  //     if (b[i]) continue;
  //     int l = i - 1, r = i + 1;
  //     for (; ~l && !b[l]; l--);
  //     for (; r < N && !b[r]; r++);
  //     bool e = ~l && r < N && S[i] == 'Y' && S[l] == 'X' && S[r] == 'Z';
  //     if (maxz(dp[msk | 1 << i], dp[msk] + e)) trc[msk | 1 << i] = i;
  //   }
  // }

  // int cr = (1 << N) - 1;
  // while (cr) {
  //   auto &t = trc[cr];
  //   Remove(t);
  //   cr ^= 1 << t;
  // }

  while (S.size() && S.back() ^ 'Z') {
    Remove(S.size() - 1);
    S.pop_back();
  }
  int p = 0;
  for (; p < S.size() && S[p] ^ 'X'; p++) Remove(p);
  if ((int)S.size() - p < 3) {
    for (int i = p; i < S.size(); i++) Remove(i);
    return ;
  }
  // cerr << N << "\n"; cerr << p << " "; for (auto c: S) cout << c; cout << "\n";
  vector<int> vv;
  for (int i = p; i < S.size(); i++) {
    if (!vv.size() || ((S[vv.back()] != 'Y') ^ (S[i] != 'Y'))) vv.push_back(i);
    else if (i < S.size() - 1) Remove(i);
  }
  if (vv.back() < S.size() - 1) {
    Remove(vv.back());
    vv.back() = S.size() - 1;
  }
  // for (auto v: vv) cerr << v << " "; cerr << "\n";
  // return ;

  vector<int> Lf(N, -1), Rt(N, N), used(N);
  set<int> st;
  for (int i = 0; i < vv.size(); i++) {
    if (!(S[vv[i]] ^ 'Y') && !(S[vv[i - 1]] ^ 'X') && !(S[vv[i + 1]] ^ 'Z')) st.insert(vv[i]);
    if (i) Lf[vv[i]] = vv[i - 1];
    if (i < vv.size() - 1) Rt[vv[i]] = vv[i + 1];
  }
  while (st.size()) {
    int u = *begin(st); st.erase(begin(st));
    Remove(u); used[u] = 1;
    // cerr << u << "\n";
    int v = Rt[Rt[u]];
    if (v < N) {
      Remove(Rt[u]); used[Rt[u]] = 1;
      // cerr << "R " << Rt[u] << "\n";
      Lf[v] = Lf[u];
      Rt[Lf[u]] = v;
      if (!(S[Rt[v]] ^ 'Z')) st.insert(v);
    }
    else {
      Remove(Lf[u]); used[Lf[u]] = 1;
      // cerr << "L " << Lf[u] << "\n";
      v = Lf[Lf[u]];
      if (~v) {
        Rt[v] = Rt[u];
        Lf[Rt[u]] = v;
        if (!(S[Lf[v]] ^ 'X')) st.insert(v);
      }
    }
  }

  for (auto v: vv) {
    if (!used[v]) {
      // cerr << "O " << v << "\n";
      Remove(v);
    }
  }
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:17:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   17 |     Send(idc[S[i]] >> 1 & 1);
      |                  ^
Anna.cpp:18:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   18 |     Send(idc[S[i]] & 1);
      |                  ^
Anna.cpp: At global scope:
Anna.cpp:8:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    8 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:64:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (; p < S.size() && S[p] ^ 'X'; p++) Remove(p);
      |          ~~^~~~~~~~~~
Bruno.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = p; i < S.size(); i++) Remove(i);
      |                     ~~^~~~~~~~~~
Bruno.cpp:71:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for (int i = p; i < S.size(); i++) {
      |                   ~~^~~~~~~~~~
Bruno.cpp:73:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     else if (i < S.size() - 1) Remove(i);
      |              ~~^~~~~~~~~~~~~~
Bruno.cpp:75:17: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   if (vv.back() < S.size() - 1) {
      |       ~~~~~~~~~~^~~~~~~~~~~~~~
Bruno.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int i = 0; i < vv.size(); i++) {
      |                   ~~^~~~~~~~~~~
Bruno.cpp:87:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     if (i < vv.size() - 1) Rt[vv[i]] = vv[i + 1];
      |         ~~^~~~~~~~~~~~~~~
Bruno.cpp:30:5: warning: unused variable 'idc' [-Wunused-variable]
   30 | int idc[256];
      |     ^~~
Bruno.cpp: At global scope:
Bruno.cpp:13:5: warning: 'int {anonymous}::FunctionExample(int)' defined but not used [-Wunused-function]
   13 | int FunctionExample(int P) { return 1 - P; }
      |     ^~~~~~~~~~~~~~~

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