Submission #216027

#	Time	Username	Problem	Language	Result	Execution time	Memory
216027		eriksuenderhauf	Stray Cat (JOI20_stray)	C++14	91 / 100	90 ms	17324 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) {
  // const int ln = 6;
  // for (int i = 0; i < (1<<ln); i++) {
  //   string cur, xcur;
  //   for (int j = ln-1; ~j; j--) {
  //     cur.pb((char)('0'+((i >> j) & 1)));
  //     xcur.pb(cur.back()^1);
  //   }
  //   string tmp = cur + cur;
  //   int ok = tmp.find(cur, 1) != string::npos;
  //   int o = tmp.find(xcur) != string::npos;
  //   reverse(tmp.begin(), tmp.end());
  //   ok &= ok ^ (tmp.find(cur) != string::npos);
  //   o &= tmp.find(xcur) == string::npos;
  //   if (ok) {
  //     cerr << cur << " " << xcur << endl;
  //   }
  // }
  for (int i = 0; i < M; i++)
    adj[U[i]].pb(i), adj[V[i]].pb(i);
  if (A > 2) {
    deque<int> pq;
    pq.pb(0);
    fill(dp, dp+N, N+1);
    dp[0] = 0;
    vi X(M);
    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;
  }
  vi X(M);
  function<void(int,int,int,int)> dfs = [&](int u, int p, int d, int l) {
    int f = (u != 0 && sz(adj[u]) > 2 ? 1 : 0);
    // cerr << u << " " << f << " " << l << endl;
    trav(x, adj[u]) {
      int v = U[x]^V[x]^u;
      if (v != p) {
        X[x] = f ? l : bl[d%sz(bl)]-'0';
        dfs(v, u, d+(f?0:1), X[x]^1);
      }
    }
  };
  dfs(0, -1, 0, 0);
  // for (int i = 0; i < M; i++)
  //   cerr << U[i] << " " << V[i] << " / " << X[i] << endl;
  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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int get(int l, int r) {
  return uniform_int_distribution<int>(l,r)(rng);
}

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);
    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;
  }
  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) {
    // cerr << "found dir: " << pos[0] << "\n";
    fnd = 1;
    if (pos[0] >= 0)
      return -1;
    return 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: 0 / 9