AtCoder Regular Contest 162 - B. Insertion Sort 2 (1124)
해당 연산을 함으로써 불변인것을 생각한다.
인접한 두 개의 수를 이동시키는 것은 inversion counting의 parity를 변화시키지 못한다.
inversion이 짝수개만큼 변하기 때문이다.
인접한 두개가 이동하면서 교차되는 것들에 대해서 는 항상 inversion을 씩 변화시키므로 다른 하나와 크로스될 때마다 처럼 parity를 변화시키게 된다.
따라서 Inversion count가 처음에 홀수개라면 정답은 No 이다.
굳이 직접 검사해줄 필요 없이 construction의 결과로 정렬이 되지 않으면 No 라고 출력해주면 된다.
그렇지 않다면 항상 가능하다.
부터 이 가야할 자리에 안가있으면 그것이 있는 자리를 라고 하면 로 설정하고 으로 설정해서 을 제일 앞으로 보낼 수 있다.
어떨때는 그 다음 앞으로 보내주어야 할 수가 제일 뒤 인 경우가 있는데, 이 경우엔 연산을 두 번 써서 보내줄 수 있다.
따라서 하나의 수를 적절한 위치로 보내는데 최대 번의 연산이 필요하다.
이런식으로 모두 보내며 부터 까지만 시행한다.
이나 은 까지 시행한 시점에서 자신의 자리에 가있지 않으면 그것을 올바르게 자리해줄 수 없기 때문이다.
void solve() {
int n;
cin >> n;
vi p(n + 1);
fv1(p);
vector<pi> ans;
auto get = [&](int i, int j) {
vi c{0};
for (int k = 1; k <= j; k++) c.pb(p[k]);
c.pb(p[i]);
c.pb(p[i + 1]);
for (int k = j + 1; k <= n; k++) if (k != i && k != i + 1)c.pb(p[k]);
return c;
};
for (int i = 1; i <= n - 2; i++) {
int idx = -1;
for (int j = 1; j <= n; j++) {
if (p[j] == i) {
idx = j;
break;
}
}
if (idx == i) continue;
if (idx == n) {
ans.pb({idx - 1, i - 1});
p = get(idx - 1, i - 1);
ans.pb({i + 1, i - 1});
p = get(i + 1, i - 1);
} else {
ans.pb({idx, i - 1});
p = get(idx, i - 1);
}
}
if (!is_sorted(all(p))) {
cout << "No";
return;
}
cout << "Yes\n" << sz(ans) << endl;
for (auto &[i, j]: ans) cout << i << ' ' << j << endl;
}
Comments