Language: C++

/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>

using Position = std::pair<int32_t, int32_t>;  // row, column

struct Audience {
  bool exited{false};
  int32_t distance_to_exit{INT32_MAX};
};

class Solution {
 public:
  Solution() = delete;
  explicit Solution(const int32_t N) noexcept;
  int32_t CalculateNumberOfPairs(const std::vector<int32_t> &people_to_exit) noexcept;

 private:
  void ExitOneAudience(const Position &position) noexcept;
  Position GetPosition(const int32_t audience_number) const noexcept;
  void UpdateDistance(const Position &position, const int32_t distance) noexcept;
  void UpdateAllOfDistances() noexcept;
  int32_t GetDistanceWhenEmpty(const Position &position) const noexcept;
  bool IsValidPosition(const Position &position) const noexcept;
  bool IsEmpty(const Position &position) const noexcept;
  int32_t GetDistance(const Position &position) const noexcept;
  void PrintDebug() const noexcept;

 private:
  int32_t N_;
  int32_t number_of_dislike_;
  std::vector<std::vector<Audience>> audiences_;
  std::queue<Position> q_;
};

const int32_t neighbours[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

Solution::Solution(const int32_t N) noexcept : N_(N), number_of_dislike_(0) {
  audiences_ = std::vector<std::vector<Audience>>(N, std::vector<Audience>(N));

  for (int32_t row = 0; row < N; ++row) {
    UpdateDistance(Position(row, 0), 0);
    UpdateDistance(Position(row, N - 1), 0);
  }
  for (int32_t column = 0; column < N; ++column) {
    UpdateDistance(Position(0, column), 0);
    UpdateDistance(Position(N - 1, column), 0);
  }

  UpdateAllOfDistances();
}

int32_t Solution::CalculateNumberOfPairs(const std::vector<int32_t> &people_to_exit) noexcept {
  for (const int32_t person_number_to_exit : people_to_exit) {
    const Position position_to_exit = GetPosition(person_number_to_exit);
    ExitOneAudience(position_to_exit);
  }

  return number_of_dislike_;
}

void Solution::ExitOneAudience(const Position &position) noexcept {
  number_of_dislike_ += GetDistance(position);
  std::cerr << "exit: +=" << GetDistance(position) << std::endl;
  audiences_[position.first][position.second].exited = true;
  audiences_[position.first][position.second].distance_to_exit = GetDistanceWhenEmpty(position);
  q_.push(position);
  UpdateAllOfDistances();
}

void Solution::UpdateDistance(const Position &position, const int32_t distance) noexcept {
  if (GetDistance(position) > distance) {
    audiences_[position.first][position.second].distance_to_exit = distance;
    q_.push(position);
  }
}

void Solution::UpdateAllOfDistances() noexcept {
  while (q_.size() > 0) {
    const Position c_position = q_.front();
    const int32_t c_distance = GetDistance(c_position);
    q_.pop();
    for (const auto &next : neighbours) {
      const Position next_position = Position(c_position.first + next[0], c_position.second + next[1]);
      if (IsValidPosition(next_position)) {
        if (IsEmpty(c_position)) {
          UpdateDistance(next_position, c_distance);
        } else {
          UpdateDistance(next_position, c_distance + 1);
        }
      }
    }
  }
}

int32_t Solution::GetDistanceWhenEmpty(const Position &position) const noexcept {
  int32_t minimum_distance = INT32_MAX;
  for (const auto &neighbour : neighbours) {
    const Position neighbour_position = Position(position.first + neighbour[0], position.second + neighbour[1]);
    if (IsValidPosition(neighbour_position)) {
      const int32_t temp_distance =
          IsEmpty(neighbour_position) ? GetDistance(neighbour_position) : GetDistance(neighbour_position) + 1;
      minimum_distance = std::min(temp_distance, minimum_distance);
    } else {
      minimum_distance = 0;
    }
  }
  return minimum_distance;
}

Position Solution::GetPosition(const int32_t audience_number) const noexcept {
  return Position((audience_number - 1) / N_, (audience_number - 1) % N_);
}

bool Solution::IsValidPosition(const Position &position) const noexcept {
  return (position.first >= 0 && position.first < N_ && position.second >= 0 && position.second < N_);
}

bool Solution::IsEmpty(const Position &position) const noexcept {
  return audiences_[position.first][position.second].exited;
}

int32_t Solution::GetDistance(const Position &position) const noexcept {
  return audiences_[position.first][position.second].distance_to_exit;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int32_t N;
  cin >> N;
  vector<int32_t> P(N);
  Solution *solution = new Solution(N);
  for (int32_t i = 0; i < N; ++i) {
    cin >> P[i];
  }
  const int64_t result = solution->CalculateNumberOfPairs(P);
  cout << result << endl;
  delete solution;

  return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:130:3: error: 'cin' was not declared in this scope; did you mean 'std::cin'?
  130 |   cin.tie(0);
      |   ^~~
      |   std::cin
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:146,
                 from a.cc:5:
/usr/include/c++/14/iostream:62:18: note: 'std::cin' declared here
   62 |   extern istream cin;           ///< Linked to standard input
      |                  ^~~
a.cc:131:3: error: 'ios' has not been declared
  131 |   ios::sync_with_stdio(false);
      |   ^~~
a.cc:135:3: error: 'vector' was not declared in this scope
  135 |   vector<int32_t> P(N);
      |   ^~~~~~
a.cc:135:3: note: suggested alternatives:
In file included from /usr/include/c++/14/vector:66,
                 from /usr/include/c++/14/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:53:
/usr/include/c++/14/bits/stl_vector.h:428:11: note:   'std::vector'
  428 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
/usr/include/c++/14/vector:93:13: note:   'std::pmr::vector'
   93 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
a.cc:135:17: error: expected primary-expression before '>' token
  135 |   vector<int32_t> P(N);
      |                 ^
a.cc:135:19: error: 'P' was not declared in this scope
  135 |   vector<int32_t> P(N);
      |                   ^
a.cc:141:3: error: 'cout' was not declared in this scope; did you mean 'std::cout'?
  141 |   cout << result << endl;
      |   ^~~~
      |   std::cout
/usr/include/c++/14/iostream:63:18: note: 'std::cout' declared here
   63 |   extern ostream cout;          ///< Linked to standard output
      |                  ^~~~
a.cc:141:21: error: 'endl' was not declared in this scope; did you mean 'std::endl'?
  141 |   cout << result << endl;
      |                     ^~~~
      |                     std::endl
In file included from /usr/include/c++/14/istream:41,
                 from /usr/include/c++/14/sstream:40,
                 from /usr/include/c++/14/complex:45,
                 from /usr/include/c++/14/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:127:
/usr/include/c++/14/ostream:744:5: note: 'std::endl' declared here
  744 |     endl(basic_ostream<_CharT, _Traits>& __os)
      |     ^~~~