Submission #212938

#	Time	Username	Problem	Language	Result	Execution time	Memory
212938		aboluo2003	Stray Cat (JOI20_stray)	C++14	100 / 100	92 ms	16400 KiB

Anthony

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

namespace {


}  // namespace

std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
  vector<int> rt (M, 0);
  vector<vector<int>> G (N);
  for (int i = 0; i < M; i++) {
    G[U[i]].push_back(V[i]);
    G[V[i]].push_back(U[i]);
  }
  if (A >= 3) {
    vector<int> dep (N, -1);
    queue<int> Q;
    Q.push(0);
    dep[0] = 0;
    while (!Q.empty()) {
      int p = Q.front();
      Q.pop();
      for (auto e : G[p]) {
        if (dep[e] == -1) {
          dep[e] = dep[p] + 1;
          Q.push(e);
        }
      }
    }
    for (int i = 0; i < M; i++) {
      int x = U[i], y = V[i];
      if (dep[x] > dep[y]) {
        swap(x, y);
      }
      rt[i] = dep[x] % 3;
    }
  } else {
    vector<int> col (N, 0);
    vector<int> dep (N, 0);
    function<void(int, int, int)> dfs = [&] (int p, int fa, int cdis) {
      static char str[] = "110100";
      if (p) {
        cdis = (G[fa].size() == 2u) ? (cdis % 6 + 1) : (0);
        col[p] = (!cdis) ? (col[fa] ^ 1) : (str[cdis - 1] - '0');
        dep[p] = dep[fa] + 1;
      }
      for (auto e : G[p]) {
        if (e ^ fa) {
          dfs(e, p, cdis);
        }
      }
    };
    dfs(0, -1, 0);
    for (int i = 0; i < M; i++) {
      int x = U[i], y = V[i];
      if (dep[x] > dep[y]) {
        swap(x, y);
      }
      rt[i] = col[y];
//      cerr << x << " " << y << " " << rt[i] << '\n';
    }
  }
  return rt;
}

Catherine

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

namespace {

  int A, B;
  
  bool has_dir;
  int last_col;
  vector<int> seq;

  bool match(const char* s) {
    int len = strlen(s);
    if (len > seq.size()) {
      return false;
    }
    int t = seq.size();
    while (len-- && t--) {
      if (s[len] - '0' != seq[t]) {
        return false;
      }
    }
    return true;
  }

}  // namespace

void Init(int A, int B) {
  ::A = A;
  ::B = B;
  has_dir = false;
  last_col = -1;
}

int Move(std::vector<int> y) {
  if (A >= 3) {
    const static int go[3] = {1, 2, 0};
    vector<int> id;
    for (int i = 0; i < A; i++) {
      if (y[i]) {
        id.push_back(i);
      }
    }
    int sz = id.size();
    assert(sz <= 2 && sz >= 1);
    if (sz == 1) {
      return id[0]; 
    } else {
      return go[3 ^ id[0] ^ id[1]];
    }
  } else {
    if (has_dir) {
      if (!y[0] + !y[1] == 1) {
        return last_col = !y[0];
      } else {
        return last_col = last_col ^ 1;
      }
    } else {
      int sum = last_col != -1;
      for (auto x : y) {
        sum += x;
      }
      if (sum > 2) {
        has_dir = true;
        if (last_col == -1) {
          return last_col = y[0] > y[1];
        } else {
          if (!y[last_col]) {
            return -1;
          } else {
            return last_col = last_col ^ 1;
          }
        }
      } else if (sum == 1) {
        has_dir = true;
        if (last_col == -1) {
          return last_col = !y[0];
        } else {
          return -1;
        }
      } else {
        if (last_col == -1) {
          if (y[0] == 2) {
            last_col = 0;
            seq = vector<int>{0, 0};
          } else if (y[1] == 2) {
            last_col = 1;
            seq = vector<int>{1, 1};
          } else {
            last_col = 1;
            seq = vector<int>{0, 1};
          }
          return last_col;
        } else {
          seq.push_back(!y[0]);
          int sz = seq.size();
          if (sz >= 4) {
            if (seq[sz - 2] == 1 && seq[sz - 3] == 0 && seq[sz - 4] == 1) {
              has_dir = true;
              if (seq[sz - 1] == 0) {
                return -1;
              }
            } else if (seq[sz - 1] == 1 && seq[sz - 2] == 0 && seq[sz - 3] == 1) {
              has_dir = true;
              if (seq[sz - 4] == 1) {
                return -1;
              }
            } else if (match("00110") || match("01001")) {
              has_dir = true;
              return -1;
            } 
          }
          return last_col = !y[0];
        }
      }
    }
  }
  return -1;
}

Compilation message (stderr)

Catherine.cpp: In function 'bool {anonymous}::match(const char*)':
Catherine.cpp:15:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (len > seq.size()) {
         ~~~~^~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 71 / 71
• Subtask 7: 9 / 9