Submission #748700

#	Time	Username	Problem	Language	Result	Execution time	Memory
748700		piOOE	Stray Cat (JOI20_stray)	C++17	29 / 100	58 ms	16148 KiB

Anthony

#include "Anthony.h"
#include <queue>
#include <utility>
#include <vector>

namespace {

  using std::vector;

}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
  vector<vector<int>> G(N);
  for (int i = 0; i < M; ++i) {
    G[U[i]].push_back(i);
    G[V[i]].push_back(i);
  }
  std::queue<int> que;
  vector<int> dist(N, N);
  vector<int> colors(N, -1);
  dist[0] = 0;
  que.push(0);
  for (; !que.empty(); ) {
    const int u = que.front();
    que.pop();
    for (const int i : G[u]) {
      const int v = U[i] ^ V[i] ^ u;
      if (dist[v] > dist[u] + 1) {
        dist[v] = dist[u] + 1;
        que.push(v);
        if (A == 2) {
          if (u == 0) {
            colors[v] = 0;
          } else if (G[u].size() >= 3) {
            colors[v] = ("010011"[colors[u]] == '0') ? 1 : 0;
          } else {
            colors[v] = (colors[u] + 1) % 6;
          }
        }
      }
    }
  }
  vector<int> x(M, -1);
  for (int i = 0; i < M; ++i) {
    int u = U[i], v = V[i];
    if (dist[u] > dist[v]) {
      std::swap(u, v);
    }
    if (A == 2) {
      x[i] = "010011"[colors[v]] - '0';
    } else {
      x[i] = dist[u] % 3;
    }
  }
  return x;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    int A, B, e = -1;
    bool ok = false;

    vector<int> adj;
    vector<int> code{0, 1, 0, 0, 1, 1};

    bool extendable(vector<int> a) {
        for (int i = 0; i < size(code); ++i) {
            bool yay = true;

            for (int k = 0; k < size(a); ++k) {
                if (a[k] != code[(i + k) % size(code)]) {
                    yay = false;
                    break;
                }
            }

            if (yay) {
                return true;
            }
        }

        return false;
    }
}

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

int Move(std::vector<int> yy) {
    vector<int> y = yy;
    if (e != -1) {
        y[e] += 1;
    }

    int deg = accumulate(y.begin(), y.end(), 0);

    if (A >= 3) {
        int fi = -1, se = -1, cnt = 0;

        for (int i = 0; i < A; ++i) {
            if (y[i]) {
                fi = fi == -1 ? i : fi;
                se = i;
                cnt += 1;
            }
        }

        if (fi != 0 || se != 2) {
            return e = fi;
        } else {
            return e = se;
        }
    } else {
        if (deg == 2) {
            if (ok) {
                return e = find(yy.begin(), yy.end(), 1) - yy.begin();
            }

            int a = -1, b = -1;

            for (int i = 0; i < A; ++i) {
                if (y[i]) {
                    a = a == -1 ? i : a;
                    b = i;
                }
            }

            if (e == -1) {
                adj.push_back(a);
                adj.push_back(b);
                return e = b;
            }

            int c = a ^ b ^ e;
            adj.push_back(c);

            if (adj.size() == 5) {
                ok = true;
                if (extendable(adj)) {
                    return -1;
                }
                return c;
            } else {
                return e = c;
            }
        } else {
            ok = true;
            int ans = find(y.begin(), y.end(), 1) - y.begin();
            if (ans == e) {
                return -1;
            } else {
                return e = ans;
            }
        }

        assert(false);
    }
}

Compilation message (stderr)

Catherine.cpp: In function 'bool {anonymous}::extendable(std::vector<int>)':
Catherine.cpp:14:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         for (int i = 0; i < size(code); ++i) {
      |                         ~~^~~~~~~~~~~~
Catherine.cpp:17:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |             for (int k = 0; k < size(a); ++k) {
      |                             ~~^~~~~~~~~

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