Submission #1198204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198204		abczz	Ancient Machine (JOI21_ancient_machine)	C++20	0 / 100	37 ms	6588 KiB

Anna

#include "Anna.h"
#include <vector>
#include <iostream>
#include <random>
#define ll long long

using namespace std;

namespace {
  using namespace std;
  random_device rd;
  mt19937 mt(rd());

  void dtb(ll u) {
    for (int i=16; i>=0; --i) {
      if (u & (1LL<<i)) Send(1);
      else Send(0);
    }
  }
}

void Anna(int N, std::vector<char> S) {
  vector <ll> U, V;
  ll a = -1e18, b = 1e18, x = 0, y = 0;
  for (ll i=N-1; i>=0; --i) {
    if (S[i] == 'Z') a = max(a, i);
    else if (S[i] == 'X') b = min(b, i);
  }
  if (b >= a-1) return;
  dtb(b);
  dtb(a);
  U.resize(N+3);
  V.resize(N+3);
  for (int i=0; i<N+3; ++i) U[i] = V[i] = 0;
  for (int i=b; i<=a; ++i) {
    if (S[i] == 'X') {
      x = 0;
      if (S[i-1] == 'Y' || y) ++y;
    }
    else if (S[i] == 'Y') {
      y = 0;
      for (int j=i-1; j>=i-x; --j) U[j] = 1;
      x = 0;
    }
    else {
      if (S[i-1] == 'X' || x) ++x;
      for (int j=i-1; j>=i-y; --j) V[j] = 1;
      y = 0;
    }
  }
  x = y = 0;
  for (int i=b+1; i<a; i+=2) {
    if (U[i] || U[i+1]) ++x;
    if (V[i] || V[i+1]) ++y;
  }
  ll p = 0, cur, opt;
  if (x < y) {
    Send(0);
    ll cnt[4] = {0, 0, 0, 0};
    for (int i=b+1; i<a; i+=2) {
      cur = U[i] * 2 + U[i+1];
      if (p == 0) ++cnt[cur];
      p = cur;
    }
    p = 0;
    if (cnt[1] >= max(cnt[2], cnt[3])) {
      opt = 1;
      Send(0);
      Send(1);
    }
    else if (cnt[2] >= max(cnt[1], cnt[3])) {
      opt = 2;
      Send(1);
      Send(0);
    }
    else {
      opt = 3;
      Send(1);
      Send(1);
    }
    for (int i=b+1; i<a; i+=2) {
      ll r = opt-1;
      cur = U[i] * 2 + U[i+1];
      if (p == 0) {
        if (!cur) Send(0);
        else {
          Send(1);
          if (cur == r+1) Send(0);
          else {
            Send(1);
            if (cur == (r+1)%3 + 1) Send(0);
            else Send(1);
          }
        }
      }
      else if (p == 1 || p == 3) {
        if (!cur) Send(0);
        else {
          Send(1);
          if (cur == 2) Send(0);
          else Send(1);
        }
      }
      else if (p == 2) {
        if (!cur) Send(0);
        else Send(1);
      }
      p = cur;
    }
  }
  else {
    swap(x, y);
    swap(U, V);
    Send(1);
    if ((a-b+1) & 1) ++a;
    ll cnt[4] = {0, 0, 0, 0};
    for (int i=a-1; i>=b+1; i-=2) {
      cur = U[i] * 2 + U[i-1];
      if (p == 0) ++cnt[cur];
      p = cur;
    }
    p = 0;
    if (cnt[1] >= max(cnt[2], cnt[3])) {
      opt = 1;
      Send(0);
      Send(1);
    }
    else if (cnt[2] >= max(cnt[1], cnt[3])) {
      opt = 2;
      Send(1);
      Send(0);
    }
    else {
      opt = 3;
      Send(1);
      Send(1);
    }
    for (int i=a-1; i>=b+1; i-=2) {
      ll r = opt-1;
      cur = U[i] * 2 + U[i-1];
      ++cnt[cur];
      if (p == 0) {
        if (!cur) Send(0);
        else {
          Send(1);
          if (cur == r+1) Send(0);
          else {
            Send(1);
            if (cur == (r+1)%3 + 1) Send(0);
            else Send(1);
          }
        }
      }
      else if (p == 1 || p == 3) {
        if (!cur) Send(0);
        else {
          Send(1);
          if (cur == 2) Send(0);
          else Send(1);
        }
      }
      else if (p == 2) {
        if (!cur) Send(0);
        else Send(1);
      }
      p = cur;
    }
  }
}

Bruno

#include "Bruno.h"
#include <vector>
#include <iostream>
#include <random>
#define ll long long

namespace {
using namespace std;
random_device rd;
mt19937 mt(rd());
}

void Bruno(int N, int L, std::vector<int> A) {
  if (L == 0) {
    for (int i=0; i<N; ++i) Remove(i);
    return;
  }
  vector <ll> V;
  int nx = 0;
  ll b = 0, a = 0;
  for (int i=16; i>=0; --i) b += (1LL<<i) * A[nx++];
  for (int i=16; i>=0; --i) a += (1LL<<i) * A[nx++];
  ll ty = A[nx++], p = 0, cur;
  for (int i=0; i<b; ++i) Remove(i);
  for (int i=a+1; i<N; ++i) Remove(i);
  ll opt = A[nx++] * 2;
  opt += A[nx++];
  if (!ty) {
    V.push_back(b);
    for (int i=b+1; i<a; i+=2) {
      ll r = opt-1;
      if (p == 0) {
        if (A[nx++] == 0) cur = 0;
        else {
          if (A[nx++] == 0) cur = r+1;
          else {
            if (A[nx++] == 0) cur = (r+1)%3 + 1;
            else cur = (r+2)%3 + 1;
          }
        }
      }
      else if (p == 1 || p == 3) {
        if (A[nx++] == 0) cur = 0;
        else {
          if (A[nx++] == 0) cur = 2;
          else cur = 3;
        }
      }
      else if (p == 2) {
        if (A[nx++] == 0) cur = 0;
        else cur = 1;
      }
      if (cur & 2) Remove(i);
      else V.push_back(i);
      if (i+1 != a) {
        if (cur & 1) Remove(i+1);
        else V.push_back(i+1);
      }
      p = cur;
    }
    while (!V.empty()) {
      auto u = V.back();
      V.pop_back();
      Remove(u);
    }
    Remove(a);
  }
  else {
    V.push_back(a);
    if ((a-b+1) & 1) ++a;
    for (int i=a-1; i>=b+1; i-=2) {
      ll r = opt-1;
      if (p == 0) {
        if (A[nx++] == 0) cur = 0;
        else {
          if (A[nx++] == 0) cur = r+1;
          else {
            if (A[nx++] == 0) cur = (r+1)%3 + 1;
            else cur = (r+2)%3 + 1;
          }
        }
      }
      else if (p == 1 || p == 3) {
        if (A[nx++] == 0) cur = 0;
        else {
          if (A[nx++] == 0) cur = 2;
          else cur = 3;
        }
      }
      else if (p == 2) {
        if (A[nx++] == 0) cur = 0;
        else cur = 1;
      }
      if (i != V[0]) {
        if (cur & 2) Remove(i);
        else V.push_back(i);
      }
      if (cur & 1) Remove(i-1);
      else V.push_back(i-1);
      p = cur;
    }
    while (!V.empty()) {
      auto u = V.back();
      V.pop_back();
      Remove(u);
    }
    Remove(b);
  }
}

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