CS Academy Round #38: C. Bounded Difference
実装が面倒。
problem
長さ$N$の整数列$A$が与えられる。点の交換を$1$回だけして隣り合う要素の差の絶対値が高々$K$であるようにできるか、できるなら具体的に示せ。
solution
制約を満たしていない点を列挙する。たくさんあるなら不可能。 少ないなら、任意の点$i$と制約を満たさない点$j$の対$(i, j)$の全てについて交換を試す。 交換が制約に影響するのは交換した点の周囲だけなので、$1$回の交換について制約の確認は$O(1)$にできる。 全体で$O(N)$。
implementation
#include <algorithm>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
pair<int, int> solve(int n, int k, vector<int> a) {
auto is_valid_at = [&](int i) { return abs(a[i] - a[i + 1]) <= k; };
vector<int> invalid;
repeat (i, n - 1) {
if (not is_valid_at(i)) {
invalid.push_back(i);
}
}
if (invalid.empty()) {
return { -1, 0 }; // already valid
} else {
if (invalid.size() <= 4) {
auto is_valid_around = [&](int j) {
int l = max(0, j - 2);
int r = min(n, j + 2);
repeat_from (i, l, r - 1) {
if (not is_valid_at(i)) return false;
}
return true;
};
vector<int> is;
for (int i : invalid) {
is.push_back(i);
is.push_back(i + 1);
}
whole(sort, is);
is.erase(whole(unique, is), is.end());
repeat (j, n) {
for (int i : is) {
swap(a[i], a[j]);
bool is_valid = true;
if (not is_valid_around(j)) is_valid = false;
for (int k : is) {
if (not is_valid_around(k)) is_valid = false;
}
if (is_valid) return { i, j };
swap(a[i], a[j]);
}
}
}
return { -1, -1 }; // no valid solution
}
}
int main() {
int n, k; scanf("%d%d", &n, &k);
vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
pair<int, int> result = solve(n, k, a);
if (result.first == -1) {
printf("%d\n", result.second);
} else {
printf("%d %d\n", result.first + 1, result.second + 1);
}
return 0;
}