Submission #1265216

#TimeUsernameProblemLanguageResultExecution timeMemory
1265216Canuc80kTriple Peaks (IOI25_triples)C++20
Compilation error
0 ms0 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; }

Compilation message (stderr)

triples.cpp:1:6: error: 'vector' in namespace 'std' does not name a template type
    1 | std::vector<int> construct_range(int n, int k) {
      |      ^~~~~~
triples.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
  +++ |+#include <vector>
    1 | std::vector<int> construct_range(int n, int k) {