Submission #389704

#	Time	Username	Problem	Language	Result	Execution time	Memory
389704		rama_pang	Navigation 2 (JOI21_navigation2)	C++17	100 / 100	990 ms	892 KiB

Anna

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

namespace {

pair<int, int> GetSpecial(pair<int, int> a, pair<int, int> b) {
  /* List of classes determined by 2 special colors

    Case 1:
    000 000 000
    000 000 000
    110 101 011

    000 000 000
    110 101 011
    000 000 000

    110 101 011
    000 000 000
    000 000 000

    Case 2:
    000 000 000
    001 010 100
    100 001 010

    001 010 100
    100 001 010
    000 000 000

    100 001 010
    000 000 000
    001 010 100

    Case 3:
    000 000 000
    010 100 001
    100 001 010

    010 100 001
    100 001 010
    000 000 000

    100 001 010
    000 000 000
    010 100 001

    Case 4:
    000 000 000
    100 001 010
    100 001 010

    100 001 010
    100 001 010
    000 000 000

    100 001 010
    000 000 000
    100 001 010
  */

  const vector<int> dx = {0, 1, 1, 1};
  const vector<int> dy = {1, 0, 1, 2};

  for (int d = 0; d < 4; d++) {
    if ((a.first  + dx[d]) % 3 == b.first &&
        (a.second + dy[d]) % 3 == b.second) {
      return a;
    }
  }
  return b;
}

} // namespace

void Anna(int N, int K, vector<int> R, vector<int> C) {
  // Solution:
  // We mark a node (x, y), where x mod 3 = 0 and y mod 3 = 0 with
  // color L. Then, for Bruno, when we look at the 9 viewable cells,
  // we know which one has x mod 3 = 0 and y mod 3 = 0.
  //
  // After that, we can identify each cell having 1 of 9 equivalence
  // classes. The i-th class will hold information about the i-th goal.
  // For the i-th goal, we only need to keep track of 13 possible information:
  // 9, if the goal is close (9-adjacent to the cell of the class), and 4
  // if the goal is far away. This yield 13 (for goal information) + 1 (to
  // determine which cell has class x mod 3 = 0 and y mod 3 = 0).
  //
  // Since there are only 7 goals, there are only 7 possible values for the
  // case when the goal is close. We color the other 2 values with L, and,
  // while more difficult, we can still determine the 9 class of each cell.
  // With this, we only need 7 (goal is near) + 4 (goal is fat) + 1 (special
  // color L) = 12 colors.

  vector<vector<int>> has_goal(3, vector<int>(3));
  for (int i = 0; i < K; i++) {
    has_goal[R[i] % 3][C[i] % 3] = 1;
  }

  vector<pair<int, int>> no_goals;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (!has_goal[i][j]) {
        no_goals.emplace_back(i, j);
      }
    }
  }

  assert(no_goals.size() >= 2);
  no_goals.resize(2);

  vector<vector<int>> goal(3, vector<int>(3, -1));
  auto zero = GetSpecial(no_goals[0], no_goals[1]);

  for (int i = 0, cnt = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      int x = (zero.first + i) % 3;
      int y = (zero.second + j) % 3;
      if (pair(x, y) != no_goals[0] && pair(x, y) != no_goals[1]) {
        goal[i][j] = cnt++;
      }
    }
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      int g = goal[(i + 3 - zero.first) % 3][(j + 3 - zero.second) % 3];
      if (g == -1) {
        assert(!has_goal[i % 3][j % 3]);
        SetFlag(i, j, 12);
      } else {
        int close = -1;
        for (int di = -1; di <= 1; di++) {
          for (int dj = -1; dj <= 1; dj++) {
            if (R[g] == i + di && C[g] == j + dj) { // goal is close
              assert(close == -1);
              assert(goal[(R[g] + 3 - zero.first) % 3][(C[g] + 3 - zero.second) % 3] != -1);
              close = goal[(R[g] + 3 - zero.first) % 3][(C[g] + 3 - zero.second) % 3] + 1;
            }
          }
        }
        if (close != -1) {
          assert(1 <= close && close <= 7);
          SetFlag(i, j, close);
        } else {
          if (i + 1 < R[g]) {
            SetFlag(i, j, 8);
          } else if (i - 1 > R[g]) {
            SetFlag(i, j, 9);
          } else if (j + 1 < C[g]) {
            SetFlag(i, j, 10);
          } else if (j - 1 > C[g]) {
            SetFlag(i, j, 11);
          } else {
            assert(false);
          }
        }
      }
    }
  }
}

Bruno

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

namespace {

pair<int, int> GetSpecial(pair<int, int> a, pair<int, int> b) {
  /* List of classes determined by 2 special colors

    Case 1:
    000 000 000
    000 000 000
    110 101 011

    000 000 000
    110 101 011
    000 000 000

    110 101 011
    000 000 000
    000 000 000

    Case 2:
    000 000 000
    001 010 100
    100 001 010

    001 010 100
    100 001 010
    000 000 000

    100 001 010
    000 000 000
    001 010 100

    Case 3:
    000 000 000
    010 100 001
    100 001 010

    010 100 001
    100 001 010
    000 000 000

    100 001 010
    000 000 000
    010 100 001

    Case 4:
    000 000 000
    100 001 010
    100 001 010

    100 001 010
    100 001 010
    000 000 000

    100 001 010
    000 000 000
    100 001 010
  */

  const vector<int> dx = {0, 1, 1, 1};
  const vector<int> dy = {1, 0, 1, 2};

  for (int d = 0; d < 4; d++) {
    if ((a.first  + dx[d]) % 3 == b.first &&
        (a.second + dy[d]) % 3 == b.second) {
      return a;
    }
  }
  return b;
}

} // namespace

vector<int> Bruno(int K, vector<int> value) {
  vector<int> res(K, -1);

  vector<pair<int, int>> no_goals;
  vector<vector<int>> values(3, vector<int>(3));
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      values[i][j] = value[i * 3 + j];
      if (values[i][j] == 12) {
        no_goals.emplace_back(i, j);
      }
    }
  }

  assert(no_goals.size() == 2);

  vector<vector<int>> goal(3, vector<int>(3, -1));
  auto zero = GetSpecial(no_goals[0], no_goals[1]);

  for (int i = 0, cnt = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      int x = (zero.first + i) % 3;
      int y = (zero.second + j) % 3;
      if (pair(x, y) != no_goals[0] && pair(x, y) != no_goals[1]) {
        goal[i][j] = cnt++;
      }
    }
  }

  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      int g = goal[(i + 3 - zero.first) % 3][(j + 3 - zero.second) % 3];
      int close = values[i][j];

      if (close == 12) {
        assert(g == -1);
        continue;
      }

      assert(g != -1);

      // g-th goal has clue "close"
      if (1 <= close && close <= 7) {
        int Rg = -100, Cg = -100;
        for (int di = -1; di <= 1; di++) {
          for (int dj = -1; dj <= 1; dj++) {
            if (goal[(i + di + 6 - zero.first) % 3][(j + dj + 6 - zero.second) % 3] + 1 == close) {
              assert(Rg == -100 && Cg == -100);
              Rg = i + di;
              Cg = j + dj;
            }
          }
        }

        const auto Move = [&](int sr, int sc, int er, int ec) {
          if (sr < er) {
            return 2;
          } else if (sr > er) {
            return 3;
          } else if (sc < ec) {
            return 0;
          } else if (sc > ec) {
            return 1;
          } else {
            return 4;
          }
        };

        res[g] = Move(1, 1, Rg, Cg);
      } else {
        if (close == 8) {
          res[g] = 2;
        } else if (close == 9) {
          res[g] = 3;
        } else if (close == 10) {
          res[g] = 0;
        } else if (close == 11) {
          res[g] = 1;
        }
      }
    }
  }

  return res;
}

• Subtask 1: 100 / 100