結果
| 問題 | No.2289 順列ソート |
| ユーザー |
 Gandalfr
|
| 提出日時 | 2023-09-02 10:47:35 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 31,392 bytes |
| コンパイル時間 | 1,808 ms |
| コンパイル使用メモリ | 211,816 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-06-11 17:28:21 |
| 合計ジャッジ時間 | 2,543 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 1 ms
5,376 KB |
| testcase_04 | AC | 2 ms
5,376 KB |
| testcase_05 | AC | 2 ms
5,376 KB |
| testcase_06 | AC | 2 ms
5,376 KB |
| testcase_07 | AC | 2 ms
5,376 KB |
| testcase_08 | AC | 2 ms
5,376 KB |
| testcase_09 | AC | 1 ms
5,376 KB |
| testcase_10 | AC | 2 ms
5,376 KB |
| testcase_11 | AC | 1 ms
5,376 KB |
| testcase_12 | AC | 1 ms
5,376 KB |
| testcase_13 | AC | 1 ms
5,376 KB |
| testcase_14 | AC | 2 ms
5,376 KB |
| testcase_15 | AC | 2 ms
5,376 KB |
| testcase_16 | AC | 1 ms
5,376 KB |
| testcase_17 | AC | 2 ms
5,376 KB |
| testcase_18 | AC | 1 ms
5,376 KB |
| testcase_19 | AC | 2 ms
5,376 KB |
| testcase_20 | AC | 1 ms
5,376 KB |
| testcase_21 | AC | 1 ms
5,376 KB |
| testcase_22 | AC | 1 ms
5,376 KB |
| testcase_23 | AC | 1 ms
5,376 KB |
ソースコード
#line 1 "playspace/main.cpp"
#include <bits/stdc++.h>
#line 8 "library/gandalfr/other/io_supporter.hpp"
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++)
os << v[i] << (i + 1 != (int)v.size() ? " " : "");
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::set<T> &st) {
for (const T &x : st) {
std::cout << x << " ";
}
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::multiset<T> &st) {
for (const T &x : st) {
std::cout << x << " ";
}
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::deque<T> &dq) {
for (const T &x : dq) {
std::cout << x << " ";
}
return os;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {
os << p.first << ' ' << p.second;
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, std::queue<T> &q) {
int sz = q.size();
while (--sz) {
os << q.front() << ' ';
q.push(q.front());
q.pop();
}
os << q.front();
q.push(q.front());
q.pop();
return os;
}
template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
for (T &in : v)
is >> in;
return is;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
#line 3 "library/gandalfr/math/matrix.hpp"
#line 8 "library/gandalfr/math/matrix.hpp"
template <class T> class matrix {
private:
int H, W;
std::valarray<std::valarray<T>> table;
enum rowtrans_operation_name { SCALE, SWAP, ADD };
struct rowtrans_operation {
int op, tar, res;
T scl;
};
using operations_history = std::vector<rowtrans_operation>;
public:
matrix() = default;
matrix(int _H, int _W, T val = 0)
: H(_H), W(_W), table(std::valarray<T>(val, _W), _H) {}
matrix(const std::vector<std::vector<T>> &vv)
: H(vv.size()), W(vv[0].size()), table(std::valarray<T>(W), H) {
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
table[i][j] = vv[i][j];
}
matrix(const std::valarray<std::valarray<T>> &vv)
: H(vv.size()), W(vv[0].size()), table(vv) {}
/**
* @brief 行列をリサイズする。
* @param val 拡張部分の値
*/
void resize(int _H, int _W, T val = 0) {
H = _H, W = _W;
table.resize(_H, std::valarray<T>(val, _H));
}
int size_H() const { return H; }
int size_W() const { return W; }
void transpose() {
matrix<T> ret(W, H);
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
ret.table[j][i] = table[i][j];
*this = std::move(ret);
}
void row_assign(int i, const std::valarray<T> &row) {
assert(W == (int)row.size());
table[i] = std::move(row);
}
void row_swap(int i, int j) {
assert(0 <= i && i < H);
assert(0 <= j && j < H);
table[i].swap(table[j]);
}
/**
* @attention O(n^3)
* @attention 整数型では正しく計算できない。double や fraction を使うこと。
* @attention 枢軸選びをしていないので double では誤差が出るかも。
*/
operations_history sweep_method() {
operations_history hist;
T ret = 1;
for (int h = 0, w = 0; h < H && w < W; w++) {
if (table[h][w] == 0) {
for (int piv = h + 1; piv < H; piv++) {
if (table[piv][w] != 0) {
hist.push_back({SWAP, h, piv, 0});
row_swap(h, piv);
break;
}
}
if (table[h][w] == 0) {
continue;
}
}
T inv = 1 / table[h][w];
hist.push_back({SCALE, -1, w, inv});
table[h] *= inv;
for (int j = h + 1; j < H; j++) {
hist.push_back({ADD, h, j, -table[j][w]});
table[j] -= table[h] * table[j][w];
}
h++;
}
return hist;
}
int rank() {
auto U(*this);
U.sweep_method();
int r = 0;
for (int i = 0; i < H; ++i) {
for (int j = i; j < W; ++j) {
if (U.table[i][j] != 0) {
r++;
break;
}
}
}
return r;
}
T determinant() const {
assert(H == W);
matrix<T> U(*this);
T det = 1;
auto hist = U.sweep_method();
if (U.table[H - 1][H - 1] == 0)
return 0;
for (auto &[op, tar, res, scl] : hist) {
switch (op) {
case SCALE:
det /= scl;
break;
case SWAP:
det *= -1;
break;
}
}
return det;
}
std::vector<T> solve_system_of_equations(const std::vector<T> &y) {
assert(H == W);
std::vector<T> x(y);
matrix<T> U(*this);
auto hist = U.sweep_method();
if (U.table[H - 1][H - 1] == 0)
return {};
for (auto &[op, tar, res, scl] : hist) {
switch (op) {
case SCALE:
x[res] *= scl;
break;
case SWAP:
std::swap(x[tar], x[res]);
break;
case ADD:
x[res] += x[tar] * scl;
break;
}
}
for (int i = H - 1; i >= 0; --i) {
for (int j = 0; j < i; ++j) {
x[j] -= U.table[j][i] * x[i];
}
}
return x;
}
matrix<T> inverse() {
assert(H == W);
matrix<T> INV(matrix<T>::E(H)), U(*this);
auto hist = U.sweep_method();
if (U.table[H - 1][H - 1] == 0)
return matrix<T>(0, 0);
for (auto &[op, tar, res, scl] : hist) {
switch (op) {
case SCALE:
INV.table[res] *= scl;
break;
case SWAP:
std::swap(INV.table[tar], INV.table[res]);
break;
case ADD:
INV.table[res] += INV.table[tar] * scl;
break;
}
}
for (int i = H - 1; i >= 0; --i) {
for (int j = 0; j < i; ++j) {
INV.table[j] -= INV.table[i] * U.table[j][i];
}
}
return INV;
}
void print() const {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
std::cout << table[i][j] << (j == W - 1 ? "" : " ");
}
std::cout << std::endl;
}
}
matrix<T> &operator+=(const matrix<T> &a) {
this->table += a.table;
return *this;
}
matrix<T> &operator-=(const matrix<T> &a) {
this->table -= a.table;
return *this;
}
matrix<T> &operator*=(const T &a) {
this->table *= a;
return *this;
}
matrix<T> &operator*=(const matrix<T> &a) {
assert(W == a.H);
matrix<T> a_t(a), ret(H, a.W);
a_t.transpose();
for (int i = 0; i < H; i++) {
for (int j = 0; j < a_t.H; j++) {
ret.table[i][j] = (table[i] * a_t.table[j]).sum();
}
}
*this = std::move(ret);
return *this;
}
matrix<T> &operator/=(const T &a) {
this->table /= a;
return *this;
}
/**
* @brief 行列の冪乗。
* @param n 指数
* @attention n が 0 なら単位行列。
* @attention 演算子の優先度に注意。
*/
matrix<T> operator^=(long long n) {
assert(H == W);
if (n == 0)
return *this = E(H);
n--;
matrix<T> x(*this);
while (n) {
if (n & 1)
*this *= x;
x *= x;
n >>= 1;
}
return *this;
}
matrix<T> operator+() { return *this; }
matrix<T> operator-() { return matrix<T>(*this) *= -1; }
matrix<T> operator+(const matrix<T> &a) { return matrix<T>(*this) += a; }
matrix<T> operator-(const matrix<T> &a) { return matrix<T>(*this) -= a; }
template <typename S> matrix<T> operator*(const S &a) {
return matrix<T>(*this) *= a;
}
matrix<T> operator/(const T &a) { return matrix<T>(*this) /= a; }
matrix<T> operator^(long long n) { return matrix<T>(*this) ^= n; }
friend std::istream &operator>>(std::istream &is, matrix<T> &mt) {
for (auto &arr : mt.table)
for (auto &x : arr)
is >> x;
return is;
}
T &operator()(int h, int w) {
assert(0 <= h && h < H && 0 <= w && w <= W);
return table[h][w];
}
/**
* @brief サイズ n の単位行列。
*/
static matrix<T> E(int N) {
matrix<T> ret(N, N);
for (int i = 0; i < N; i++)
ret.table[i][i] = 1;
return ret;
}
};
#line 3 "library/gandalfr/other/random.hpp"
#line 8 "library/gandalfr/graph/graph.hpp"
#line 3 "library/gandalfr/data_structure/union_find.hpp"
#line 6 "library/gandalfr/data_structure/union_find.hpp"
class union_find {
private:
int N;
mutable std::vector<int> par;
std::vector<int> nxt;
int group_num; // 集合の数
public:
union_find() : N(0), group_num(0) {}
union_find(int n) : N(n), par(n, -1), nxt(n), group_num(n) {
std::iota(nxt.begin(), nxt.end(), 0);
}
/**
* @brief 頂点を n 個に増やす
* @attention 小さくはできない
*/
void expand(int n) {
if (n <= N)
return;
par.resize(n, -1);
nxt.resize(n);
for (int i = N; i < n; ++i)
nxt[i] = i;
group_num += n - N;
N = n;
}
int leader(int x) const {
return (par[x] < 0 ? x : par[x] = leader(par[x]));
}
bool same(int x, int y) const { return leader(x) == leader(y); }
bool merge(int x, int y) {
if ((x = leader(x)) == (y = leader(y)))
return false;
if (-par[x] > -par[y])
std::swap(x, y);
par[x] += par[y];
par[y] = x;
std::swap(nxt[x], nxt[y]);
group_num--;
return true;
}
/**
* @brief x の属するグループのサイズを返す
*/
int size(int x) const { return -par[leader(x)]; }
/**
* @brief すべてのノードの数
*/
int size() const { return N; }
std::vector<int> contained_group(int x) const {
std::vector<int> ret{x};
for (int cu = nxt[x]; cu != ret[0]; cu = nxt[cu])
ret.push_back(cu);
return ret;
}
int count_groups() const { return group_num; }
std::vector<std::vector<int>> all_groups() const {
std::vector<std::vector<int>> result;
result.reserve(group_num);
std::vector<bool> used(N, false);
for (int i = 0; i < N; ++i) {
if (!used[i]) {
result.emplace_back(contained_group(i));
for (int x : result.back()) {
used[x] = true;
}
}
}
return result;
}
};
#line 3 "library/gandalfr/graph/edge.hpp"
namespace internal {
template <class DERIVED, class WEIGHT> struct _base_edge {
int from;
int to;
WEIGHT cost;
int id;
_base_edge() {}
_base_edge(int _from, int _to, WEIGHT _cost, int _id)
: from(_from), to(_to), cost(_cost), id(_id) {}
friend bool operator>(const _base_edge &e1, const _base_edge &e) {
return e1.compare(e) > 0;
}
friend bool operator>=(const _base_edge &e1, const _base_edge &e) {
return e1.compare(e) >= 0;
}
friend bool operator<(const _base_edge &e1, const _base_edge &e) {
return e1.compare(e) < 0;
}
friend bool operator<=(const _base_edge &e1, const _base_edge &e) {
return e1.compare(e) <= 0;
}
friend std::ostream &operator<<(std::ostream &os,
const _base_edge<DERIVED, WEIGHT> &e) {
e.print(os);
return os;
}
_base_edge &operator=(const _base_edge &e) = default;
virtual ~_base_edge() = default;
DERIVED minmax() const {
auto [f, t] = std::minmax(from, to);
return {f, t, cost, id};
}
DERIVED reverse() const { return {to, from, cost, id}; }
operator int() const { return to; }
protected:
virtual void print(std::ostream &os) const = 0;
virtual int compare(const _base_edge &e) const = 0;
};
} // namespace internal
template <class WEIGHT>
struct edge : public internal::_base_edge<edge<WEIGHT>, WEIGHT> {
using internal::_base_edge<edge<WEIGHT>, WEIGHT>::_base_edge;
protected:
void print(std::ostream &os) const override {
os << this->from << " " << this->to << " " << this->cost;
}
int compare(
const internal::_base_edge<edge<WEIGHT>, WEIGHT> &e) const override {
if (this->cost == e.cost) {
if (this->from == e.from)
return this->to - e.to;
return this->from - e.from;
}
return this->cost - e.cost;
}
};
template <> struct edge<int> : public internal::_base_edge<edge<int>, int> {
static inline const int cost = 1;
using internal::_base_edge<edge<int>, int>::_base_edge;
edge(int _from, int _to, int _id)
: _base_edge<edge<int>, int>(_from, _to, 0, _id) {}
protected:
void print(std::ostream &os) const override {
os << this->from << " " << this->to;
}
int compare(const internal::_base_edge<edge<int>, int> &e) const override {
if (this->from == e.from)
return this->to - e.to;
return this->from - e.from;
}
};
#line 12 "library/gandalfr/graph/graph.hpp"
/**
* @brief グラフを管理するクラス。
* @tparam WEIGHT int なら重みなし、そうでないなら重みつきグラフ
* @tparam is_directed 有向グラフかとうか
*/
template <typename WEIGHT, bool is_directed> class graph {
private:
int N;
std::vector<std::vector<edge<WEIGHT>>> G;
std::vector<edge<WEIGHT>> E;
union_find uf;
WEIGHT W = 0;
mutable std::vector<bool> visited; // dfs / bfs のための領域
bool forest_flag = true;
const WEIGHT WEIGHT_MAX = std::numeric_limits<WEIGHT>::max();
void reset_visited_flag(int node) const {
for (int x : uf.contained_group(node))
visited[x] = false;
}
void reset_visited_flag() const { visited.assign(N, false); }
public:
graph() : N(0){};
graph(int n) : N(n), G(n), uf(n), visited(n){};
/**
* @brief ノードの数をn個まで増やす
* @param n サイズ
* @attention 今のノード数より小さい数を渡したとき、変化なし
*/
void expand(int n) {
if (n <= N)
return;
N = n;
G.resize(n);
visited.resize(n);
uf.expand(n);
}
/**
* @return ノードの数
*/
int count_nodes() const { return N; }
/**
* @return 辺の数
*/
int count_edges() const { return E.size(); }
/**
* @param n ノード番号
* @return ノード n からの隣接頂点のリストの const 参照
*/
const std::vector<edge<WEIGHT>> &operator[](int n) const { return G[n]; }
/**
* @return グラフ全体の辺のリストの const 参照
*/
const std::vector<edge<WEIGHT>> &edges() const { return E; }
/**
* @param x ノード番号
* @param y ノード番号
* @return x, y が連結かどうか
*/
bool are_connected(int x, int y) const { return uf.same(x, y); }
/**
* @return 連結成分の数
*/
int count_connected_components() const { return uf.count_groups(); }
/**
* @return 連結成分のリストのリスト
*/
std::vector<std::vector<int>> weakly_connected_components() const {
return uf.all_groups();
}
/**
* @return 木か
*/
bool is_tree() const { return forest_flag && uf.count_groups() == 1; }
/**
* @return 森か
*/
bool is_forest() const { return forest_flag; }
/**
* @return グラフの重み
*/
WEIGHT weight() const { return W; }
/**
* @param e 辺
* @attention 渡した辺の id は保持される
*/
void add_edge(const edge<WEIGHT> &e) {
forest_flag &= uf.merge(e.from, e.to);
G[e.from].emplace_back(e);
if (!is_directed && e.from != e.to)
G[e.to].emplace_back(e.reverse());
if constexpr (is_directed) {
E.emplace_back(e);
} else {
E.emplace_back(e.minmax());
}
W += e.cost;
}
/**
* @attention 辺の id は、(現在の辺の本数)番目 が振られる
* @attention WEIGHT が int だとエラー
*/
void add_edge(int from, int to, WEIGHT cost) {
static_assert(!std::is_same<WEIGHT, int>::value);
add_edge({from, to, cost, (int)E.size()});
}
/**
* @attention 辺の id は、(現在の辺の本数)番目 が振られる
* @attention WEIGHT が int 以外だとエラー
*/
void add_edge(int from, int to) {
static_assert(std::is_same<WEIGHT, int>::value);
add_edge({from, to, (int)E.size()});
}
/**
* @brief グラフを連結なグラフに分けてリストにして返す
* @example auto[Gs, gr, nd] = G.decompose();
* @returns
* 1.グラフのリスト
* 2.各ノードがグラフのリストの何番目に属するか
* 3.各ノードがグラフのどのノードになっているか
*/
std::tuple<std::vector<graph>, std::vector<int>, std::vector<int>>
decompose() const {
std::vector<graph> Gs(uf.count_groups());
std::vector<std::vector<int>> groups(uf.all_groups());
std::vector<int> group_id(N), node_id(N);
for (int i = 0; i < (int)groups.size(); i++) {
Gs[i].expand(groups[i].size());
for (int j = 0; j < (int)groups[i].size(); j++) {
group_id[groups[i][j]] = i;
node_id[groups[i][j]] = j;
}
}
for (auto e : E) {
int id = group_id[e.from];
e.from = node_id[e.from];
e.to = node_id[e.to];
Gs[id].add_edge(e);
}
return std::make_tuple(std::move(Gs), std::move(group_id),
std::move(node_id));
}
/**
* @brief グラフを隣接行列に変換
* @param invalid 辺のないときの値
* @attention 自己ループが含まれていない限り、対角成分は 0
* @attention 多重辺を持たないと仮定
*/
matrix<WEIGHT> to_adjajency(WEIGHT invalid = 0) const {
matrix<WEIGHT> ret(N, N, invalid);
for (int i = 0; i < N; i++)
ret(i, i) = 0;
for (int i = 0; i < N; i++)
for (auto &e : G[i])
ret(i, e.to) = e.cost;
return ret;
}
/**
* @brief 行きがけ順に bfs
*/
std::vector<int> preorder(int start) const {
std::vector<int> result;
reset_visited_flag(start);
visited[start] = true;
auto dfs = [&](auto self, int cu, int pa = -1) -> void {
result.push_back(cu);
for (int to : G[cu]) {
if (visited[to]) continue;
visited[to] = true;
self(self, to, cu);
}
};
dfs(dfs, start);
return result;
}
/**
* @brief 通りがけ順に bfs
*/
std::vector<int> inorder(int start) const {
std::vector<int> result;
reset_visited_flag(start);
visited[start] = true;
auto dfs = [&](auto self, int cu, int pa = -1) -> void {
for (int to : G[cu]) {
if (visited[to]) continue;
visited[to] = true;
result.push_back(cu);
self(self, to, cu);
}
result.push_back(cu);
};
dfs(dfs, start);
return result;
}
/**
* @brief 帰りがけ順に bfs
*/
std::vector<int> postorder(int start) const {
std::vector<int> result;
reset_visited_flag(start);
visited[start] = true;
auto dfs = [&](auto self, int cu, int pa = -1) -> void {
for (int to : G[cu]) {
if (visited[to]) continue;
visited[to] = true;
self(self, to, cu);
}
result.push_back(cu);
};
dfs(dfs, start);
return result;
}
private:
using PAIR = std::pair<WEIGHT, int>;
using Dijkstra_queue =
std::priority_queue<PAIR, std::vector<PAIR>, std::greater<PAIR>>;
void run_bfs(std::vector<int> &dist, std::queue<int> &q) const {
while (!q.empty()) {
int cu = q.front();
q.pop();
for (auto &e : G[cu]) {
if (dist[e.to] != WEIGHT_MAX)
continue;
dist[e.to] = dist[cu] + 1;
q.push(e.to);
}
}
}
void run_Dijkstra(std::vector<WEIGHT> &dist, Dijkstra_queue &q) const {
while (!q.empty()) {
WEIGHT cur_dist = q.top().first;
int cu = q.top().second;
q.pop();
if (visited[cu])
continue;
visited[cu] = true;
for (auto &e : G[cu]) {
WEIGHT alt = cur_dist + e.cost;
if (dist[e.to] <= alt)
continue;
dist[e.to] = alt;
q.push({alt, e.to});
}
}
}
public:
/**
* @brief 最短距離を計算する
* @param start_node 始点
* @param invalid 到達不能な頂点に格納される値
* @return 各ノードまでの最短距離のリスト
*/
std::vector<WEIGHT> distances(int start_node, WEIGHT invalid) const {
std::vector<WEIGHT> dist(N, WEIGHT_MAX);
dist[start_node] = 0;
if constexpr (std::is_same<WEIGHT, int>::value) {
// BFS algorithm
std::queue<int> q;
q.push(start_node);
run_bfs(dist, q);
} else {
// Dijkstra's algorithm
Dijkstra_queue q;
q.push({0, start_node});
reset_visited_flag(start_node);
run_Dijkstra(dist, q);
}
for (auto &x : dist)
if (x == WEIGHT_MAX)
x = invalid;
return dist;
}
public:
/**
* @brief 最短距離を計算する
* @param start_nodes 始点のリスト
* @param invalid 到達不能な頂点に格納される値
* @return 各ノードまでの最短距離のリスト
*/
std::vector<WEIGHT> distances(const std::vector<int> &start_nodes,
WEIGHT invalid) const {
std::vector<WEIGHT> dist(N, WEIGHT_MAX);
for (auto &x : start_nodes)
dist[x] = 0;
if constexpr (std::is_same<WEIGHT, int>::value) {
// BFS algorithm
std::queue<int> q;
for (auto &x : start_nodes)
q.push(x);
run_bfs(dist, q);
} else {
// Dijkstra's algorithm
Dijkstra_queue q;
std::set<int> st;
for (auto &x : start_nodes) {
q.push({0, x});
st.insert(uf.leader(x));
}
for (auto &x : st) {
reset_visited_flag(x);
}
run_Dijkstra(dist, q);
}
for (auto &x : dist)
if (x == WEIGHT_MAX)
x = invalid;
return dist;
}
matrix<WEIGHT> distances_from_all_nodes(WEIGHT invalid = -1) {
auto mt(to_adjajency(WEIGHT_MAX));
int N = mt.size_H();
for (int k = 0; k < N; k++) // 経由する頂点
for (int i = 0; i < N; i++) // 始点
for (int j = 0; j < N; j++) // 終点
if (mt(i, k) != WEIGHT_MAX && mt(k, j) != WEIGHT_MAX)
mt(i, j) = std::min(mt(i, j), mt(i, k) + mt(k, j));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if (mt(i, j) == WEIGHT_MAX)
mt(i, j) = invalid;
return mt;
}
/**
* @brief 復元付き最短経路
* @attention 到達可能でないとき、空の配列で返る
*/
std::vector<edge<WEIGHT>> shortest_path(int start_node, int end_node) {
if (start_node == end_node)
return {};
auto dist = distances(start_node, WEIGHT_MAX);
if (dist[end_node] == WEIGHT_MAX)
return {};
auto R(this->reverse());
reset_visited_flag(end_node);
visited[end_node] = true;
int cu = end_node;
std::vector<edge<WEIGHT>> route;
while (cu != start_node) {
for (auto e : R[cu]) {
if (visited[e.to])
continue;
if (dist[cu] - e.cost == dist[e.to]) {
visited[cu = e.to] = true;
route.push_back(e.reverse());
break;
}
}
}
std::reverse(route.begin(), route.end());
return route;
}
WEIGHT diameter() const {
static_assert(!is_directed);
assert(is_tree());
std::vector<WEIGHT> dist(distances(0, -1));
dist = distances(
std::max_element(dist.begin(), dist.end()) - dist.begin(), -1);
return *std::max_element(dist.begin(), dist.end());
}
graph reverse() const {
if constexpr (!is_directed) {
return *this;
} else {
graph ret(N);
for (auto &e : E) {
ret.add_edge(e.reverse());
}
return ret;
}
}
std::vector<int> topological_sort() {
static_assert(is_directed);
std::vector<int> indeg(N, 0), sorted;
for (int to : E)
indeg[to]++;
std::queue<int> q;
for (int i = 0; i < N; i++)
if (!indeg[i])
q.push(i);
while (!q.empty()) {
int cu = q.front();
q.pop();
for (int to : G[cu]) {
if (!--indeg[to])
q.push(to);
}
sorted.push_back(cu);
}
return sorted;
}
/**
* @return 最小全域森
*/
graph minimum_spanning_forest() const {
static_assert(!is_directed);
graph ret(N);
std::vector<edge<WEIGHT>> tmp(edges());
std::sort(tmp.begin(), tmp.end());
for (auto &e : tmp)
if (!ret.are_connected(e.from, e.to))
ret.add_edge(e);
return ret;
}
private:
/**
* @see https://ei1333.github.io/luzhiled/snippets/graph/lowlink.html
* @attention 非連結でも動作
*/
int run_lowlink(int idx, int k, int par, std::vector<int> &ord,
std::vector<int> &low, std::vector<edge<WEIGHT>> &brds,
std::vector<int> &apts) {
visited[idx] = true;
ord[idx] = k++;
low[idx] = ord[idx];
bool is_apt = false;
int cnt = 0;
for (auto &e : G[idx]) {
if (!visited[e.to]) {
++cnt;
k = run_lowlink(e.to, k, idx, ord, low, brds, apts);
low[idx] = std::min(low[idx], low[e.to]);
is_apt |= ~par && low[e.to] >= ord[idx];
if (ord[idx] < low[e.to]) {
brds.emplace_back(e.minmax());
}
} else if (e.to != par) {
low[idx] = std::min(low[idx], ord[e.to]);
}
}
is_apt |= par == -1 && cnt > 1;
if (is_apt)
apts.push_back(idx);
return k;
}
public:
std::pair<std::vector<edge<WEIGHT>>, std::vector<int>> lowlink() {
static_assert(!is_directed);
std::vector<edge<WEIGHT>> brds;
std::vector<int> apts, ord(N, 0), low(N, 0);
reset_visited_flag();
int k = 0;
for (int i = 0; i < N; i++) {
if (!visited[i])
k = run_lowlink(i, k, -1, ord, low, brds, apts);
}
return {brds, apts};
}
void print() const {
std::cout << this->N << " " << this->E.size() << std::endl;
for (const edge<WEIGHT> &e : this->E)
std::cout << e << std::endl;
}
};
#line 5 "library/gandalfr/other/random.hpp"
template <int id> struct random_utility {
static inline std::mt19937 mt;
static void set_seed(int seed) {
mt.seed(seed); // mtにseedを設定
}
static long long random_int(long long min_value, long long max_value) {
std::uniform_int_distribution<long long> distribution(min_value,
max_value);
return distribution(mt);
}
static double random_double(double min_value, double max_value) {
std::uniform_real_distribution<double> distribution(min_value,
max_value);
return distribution(mt);
}
static graph<int, false> generate_tree(int V) {
graph<int, false> g(V);
for (int i = 1; i < V; ++i) {
g.add_edge(random_int(0, i - 1), i);
}
return g;
}
};
using rnd = random_utility<-1>;
#line 5 "playspace/main.cpp"
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MAXINT = std::numeric_limits<int>::max();
const int MININT = std::numeric_limits<int>::min();
const ll INFLL = 1001001001001001001;
const ll MAXLL = std::numeric_limits<ll>::max();
const ll MINLL = std::numeric_limits<ll>::min();
const ll MOD = 1000000007;
const ll _MOD = 998244353;
#define rep(i, j, n) for(ll i = (ll)(j); i < (ll)(n); i++)
#define rrep(i, j, n) for(ll i = (ll)(n-1); i >= (ll)(j); i--)
#define all(a) (a).begin(),(a).end()
#define debug(a) std::cerr << #a << ": " << a << std::endl
#define LF cout << endl
#ifdef ENABLE_MULTI_FOR
#define mrep(it, mr) for(multi_iter it(mr); !it.fin(); ++it)
#endif
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
void Yes(bool ok){ std::cout << (ok ? "Yes" : "No") << std::endl; }
int main(void) {
int N;
cin >> N;
vector<int> A(N);
cin >> A;
rep(i,0,N) A[i]--;
int ans = 0;
rep(i,0,N) {
int pos = find(all(A), i) - A.begin();
ans += (pos == i ? 0 : 1);
swap(A[i], A[pos]);
}
cout << ans << endl;
}