結果
| 問題 | No.3441 Sort Permutation 2 |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-19 11:24:31 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 38 ms / 2,000 ms |
| + 989µs | |
| コード長 | 1,082 bytes |
| 記録 | |
| コンパイル時間 | 4,531 ms |
| コンパイル使用メモリ | 383,936 KB |
| 実行使用メモリ | 17,456 KB |
| 最終ジャッジ日時 | 2026-11-19 11:24:42 |
| 合計ジャッジ時間 | 11,034 ms |
|
ジャッジサーバーID (参考情報) |
judge3_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 41 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, x, limit) for (long long i = (long long)x; i < (long long)limit; i++)
#define inp(x) for (auto &i : x) cin >> i
#define el '\n'
using ll = long long;
using vi = vector<int>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vi P(n);
inp(P);
for (auto &p : P) p--;
dsu uf(n);
rep(i, 0, n) uf.merge(i, P[i]);
auto groups = uf.groups();
auto g = [&](vi A) {
int x = A.size();
if (x == 1) return 0;
int stc = A[1] - A[0];
rep(i, 1, x - 1) {
stc = gcd(stc, A[i + 1] - A[i]);
}
return stc;
};
vi cnt(n, 0);
for (auto &A : groups) {
if (A.size() == 1) continue;
int d = g(A);
cnt[d] += (int)A.size() - 1;
}
vi ans(n - 1, 0);
for (int k = 1; k < n; k++) {
for (int j = k; j < n; j += k) {
ans[k - 1] += cnt[j];
}
}
for (auto x : ans) cout << x << el;
}