I was upsolving 2123F - Minimize Fixed Points from yesterday's contest.
This is my submission: 327094692
I wasn't expecting an AC but it passes.
Cleaned up code:
constexpr int N = 2e5 + 10;
int lf[N]; // largest factor
void precompute() {
lf[1] = 1;
for (int i = 2; i < N; i += 1) {
if (lf[i]) continue;
for (int j = i; j < N; j += i) lf[j] = i;
}
}
void solve() {
int n;
cin >> n;
vector<int> ans(n + 1);
iota(all(ans), 0);
// maintain gcd property at all times and only check for fixed points
for (int i = n; i > 1; i -= 1) {
swap(ans[lf[i]], ans[i]);
}
for (int i = 1; i <= n; i += 1) cout << ans[i] << " ";
cout << endl;
}
It simply swaps out each number with its largest factor.
I'm struggling to prove if (and why) this would work every time though.




