| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1265216 | Canuc80k | Triple Peaks (IOI25_triples) | C++20 | 0 ms | 0 KiB |
std::vector<int> construct_range(int n, int k) {
const int N = n;
// Kế hoạch: dựng tập S các số chẵn (tọa độ), sau đó tạo đúng N cặp (x,y)
// sao cho mọi tổng chẵn 2..2N-2 xuất hiện đúng 1 lần; thêm cặp (-1,1) cho p=0.
std::vector<int> H(N, 1);
// Seed điểm p=0: (x,y)=(-1,1) -> H[0]=1
std::vector<int> X{ -1 }, Y{ 1 };
// S bắt đầu với 0 (chẵn). usedSum[t] = đã dựng tổng t = x + y.
std::vector<int> S; S.reserve(N);
S.push_back(0);
std::vector<char> usedSum(2 * N, 0);
// score[t] ~ “lợi ích” nếu thêm t vào S (chỉ xét t chẵn trong [2..2N-2])
const int NEG = -1e9;
std::vector<int> score(2 * N, NEG);
for (int t = 2; t <= 2 * N - 2; t += 2) score[t] = 1;
auto pick_best_even = [&]() -> int {
int opt = -1, mx = 0;
for (int i = 0; i < (int)score.size(); ++i) {
if (score[i] > mx) { mx = score[i]; opt = i; }
}
return (mx == 0 ? -1 : opt);
};
// Vòng lặp: mỗi lần thêm 1 giá trị chẵn 'opt' vào S, ghép với toàn bộ x∈S cũ
// để tạo các tổng mới x+opt (chưa dùng) => sinh ra cặp (min,max).
while ((int)X.size() < N) {
int opt = pick_best_even();
if (opt == -1) break; // không còn tổng mới trong [0..2N-2]
for (int x : S) {
int s = x + opt;
if (s >= 0 && s < 2 * N && !usedSum[s]) {
usedSum[s] = 1;
if (x < opt) { X.push_back(x); Y.push_back(opt); }
else { X.push_back(opt); Y.push_back(x); }
// Cập nhật điểm cho các t có thể cũng tạo ra 's' cùng S
for (int y : S) {
int z = x + opt - y;
if (0 <= z && z < 2 * N) score[z]--;
}
if ((int)X.size() == N) break;
}
}
// Cập nhật lợi ích cho các chênh lệch i sao cho opt+i vẫn trong biên
for (int i = 0; opt + i < 2 * N; i += 2)
if (!usedSum[opt + i]) score[i]++;
S.push_back(opt);
score[opt] = NEG;
}
// Phòng hờ: nếu vì lý do nào đó chưa đủ N điểm, lấp nốt theo kiểu đơn giản.
for (int t = 2; (int)X.size() < N && t <= 2 * N - 2; t += 2) {
for (int x : S) {
int s = x + t;
if (s >= 0 && s < 2 * N && !usedSum[s]) {
usedSum[s] = 1;
if (x < t) { X.push_back(x); Y.push_back(t); }
else { X.push_back(t); Y.push_back(x); }
if ((int)X.size() == N) break;
}
}
// đừng quên đưa t vào S để tăng độ phủ
S.push_back(t);
}
// Ánh xạ (x,y) -> (p,h): p=(x+y)/2, h=(y-x)/2
// Với (-1,1) ta được p=0,h=1; với các tổng chẵn 2..2N-2 ta được p=1..N-1.
for (int idx = 0; idx < N; ++idx) {
int p = (X[idx] + Y[idx]) / 2;
int h = (Y[idx] - X[idx]) / 2;
if (0 <= p && p < N) H[p] = std::clamp(h, 1, N - 1);
}
// Booster cực nhẹ cho case nhỏ (M=20) để chắc chắn ≥K (tránh vòng lặp nặng)
// Với N lớn thì bản dựng đã dư K nên không chạy booster.
auto comb3 = [&](long long m) { return (m < 3 ? 0LL : m * (m - 1) * (m - 2) / 6); };
long long mS = (long long)S.size();
bool need_boost = ( (long long)k > comb3(mS) ); // ước lượng thấp số triple kiểu j-max
if (need_boost && N <= 200) {
long long cur = count_triples(H);
if (cur < k) {
for (int i = 0; i < N && cur < k; ++i) {
int bestVal = H[i];
long long bestCnt = cur;
for (int val = 1; val <= N - 1; ++val) {
if (val == H[i]) continue;
int old = H[i];
H[i] = val;
long long cand = count_triples(H);
if (cand > bestCnt) { bestCnt = cand; bestVal = val; }
H[i] = old;
}
if (bestVal != H[i]) { H[i] = bestVal; cur = bestCnt; }
}
}
}
return H;
}