Submission #216942

#	Time	Username	Problem	Language	Result	Execution time	Memory
216942		eriksuenderhauf	Stray Cat (JOI20_stray)	C++14	100 / 100	75 ms	17144 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define trav(x, a) for (const auto& x: a)
#define sz(x) (int)(x).size()
#define pb push_back
using namespace std;

namespace {
  const int N = 2e4 + 5;
  vi adj[N];
  int dp[N];
  string bl = "001011";
}

vi Mark(int N, int M, int A, int B, vi U, vi V) {
  for (int i = 0; i < M; i++)
    adj[U[i]].pb(i), adj[V[i]].pb(i);
  vi X(M);
  if (A > 2) {
    deque<int> pq;
    pq.pb(0);
    fill(dp, dp+N, N+1);
    dp[0] = 0;
    for (int i = 0; i < M; i++)
      X[i] = 2;
    while (!pq.empty()) {
      int u = pq.front(); pq.pop_front();
      trav(x, adj[u]) {
        int v = U[x]^V[x]^u;
        if (dp[v] > dp[u] + 1) {
          dp[v] = dp[u] + 1;
          pq.pb(v);
        }
        if (dp[v] == dp[u] + 1 || dp[v] == dp[u]) {
          X[x] = dp[u]%3;
        }
      }
    }
    return X;
  }
  function<void(int,int,int,int)> dfs = [&](int u, int p, int d, int l) {
    if (u != 0 && sz(adj[u]) > 2) d = l ? 0 : 2;
    trav(x, adj[u]) {
      int v = U[x]^V[x]^u;
      if (v != p) {
        X[x] = bl[d%sz(bl)]-'0';
        dfs(v, u, d+1, X[x]);
      }
    }
  };
  dfs(0, -1, 0, 0);
  return X;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define sz(x) (int)(x).size()
#define pb push_back
using namespace std;
int A, B;

void Init(int A, int B) {
  ::A = A;
  ::B = B;
}

namespace {
  int lst = -1;
  bool fnd = 0;
  string bl = "001011001011";
  string rbl = "110100110100";
  string cur = "";
}

int Move(vi y) {
  if (A > 2) {
    if (~lst) y[lst]++;
    if (y[0] && y[1])
      return lst = 0;
    if (y[0] && y[2])
      return lst = 2;
    if (y[1] && y[2])
      return lst = 1;
    for (int i = 0; i < 3; i++)
      if (y[i])
        return lst = i;
  }
  if (fnd) {
    if (y[0]+y[1] > 1)
      y[lst]++;
    return lst = (y[0]==1 ? 0 : 1);
  }
  if (lst == -1) {
    if (y[0]+y[1] == 1) {
      fnd = 1;
      return lst = (y[0]==1 ? 0 : 1);
    }
    if (y[0]+y[1] > 2) {
      fnd = 1;
      return lst = (y[0]==1 ? 0 : 1);
    }
    lst = (y[0]>0 ? 0 : 1);
    y[lst]--;
    cur.pb(y[0]>0 ? '0' : '1');
    cur.pb((char)('0'+lst));
    return lst;
  }
  if (y[0]+y[1]==0) {
    fnd = 1;
    return -1;
  }
  if (y[0]+y[1]>1) {
    fnd = 1;
    y[lst]++;
    if (y[lst] == 1)
      return -1;
    return lst = lst^1;
  }
  cur.pb((y[0] == 1 ? '0' : '1'));
  vector<int> pos;
  for (int i = 0; i < 6; i++) {
    bool fl = 1;
    for (int j = 0; fl && j < sz(cur); j++)
      fl &= cur[j] == bl[i+j];
    if (fl)
      pos.pb(i);
    fl = 1;
    for (int j = 0; fl && j < sz(cur); j++)
      fl &= cur[j] == rbl[i+j];
    if (fl)
      pos.pb(~i);
  }
  if (sz(pos) == 1) {
    fnd = 1;
    return pos[0] >= 0 ? -1 : (lst = (y[0]==1 ? 0 : 1));
  }
  lst = (y[0]==1 ? 0 : 1);
  // cur.pb((char)('0'+lst));
  return lst;
}

• 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