Submission #1265219

#TimeUsernameProblemLanguageResultExecution timeMemory
1265219Canuc80kTriple Peaks (IOI25_triples)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; // -------------------- phần đếm bộ ba (giữ đúng giao diện sếp đang dùng) -------------------- ll res = 0; map<string, ll> mm; static inline void add(string type, ll i, ll j, ll k) { // if (type.back() != 'G') return; // mm[type] ++; // cout << "--Spec: " << type << ' ' << i << ' ' << j << ' ' << k << endl; (void)type; (void)i; (void)j; (void)k; res ++; } // Đếm số bộ ba kiểu “A[j] max” bằng kỹ thuật heavy/light trên hai mảng a,b static long long countr(const vector<int> &a, const vector<int> &b) { int n = (int)a.size(); if (n == 0) return 0; int T = max(1, (int)std::sqrt((double)n)); // posA[v] = các chỉ số i có a[i] = v (tăng dần) unordered_map<int, vector<int>> posA; posA.reserve(n * 2); for (int i = 0; i < n; ++i) posA[a[i]].push_back(i); // posPair[(x,y)] = các chỉ số j có (a[j]=x, b[j]=y) (tăng dần) auto pack = [](int x, int y) -> uint64_t { return ( (uint64_t)(uint32_t)x << 32 ) | (uint32_t)y; }; unordered_map<uint64_t, vector<int>> posPair; posPair.reserve(n * 2); for (int i = 0; i < n; ++i) posPair[pack(a[i], b[i])].push_back(i); // Đánh dấu heavy theo bậc của a=y vector<int> heavyY; heavyY.reserve(posA.size()); unordered_set<int> isHeavy; isHeavy.reserve(posA.size() * 2); for (auto &p : posA) { if ((int)p.second.size() > T) { heavyY.push_back(p.first); isHeavy.insert(p.first); } } long long ans = 0; // ----- LIGHT: xử lý theo k, mỗi lần duyệt ≤ T chỉ số i và đếm j bằng binary search for (int k = 0; k < n; ++k) { int x = a[k], y = b[k]; auto itY = posA.find(y); if (itY == posA.end()) continue; if (isHeavy.find(y) != isHeavy.end()) continue; // y nặng sẽ xử lý ở phần HEAVY const auto &Iy = itY->second; // các i có a[i] = y for (int t = 0; t < (int)Iy.size() && Iy[t] < k; ++t) { int i = Iy[t]; uint64_t key = pack(x, b[i]); auto itPair = posPair.find(key); if (itPair == posPair.end()) continue; const auto &vec = itPair->second; // chỉ số j có (a[j]=x, b[j]=b[i]) // Đếm j trong (i, k): i < j < k int L = int(upper_bound(vec.begin(), vec.end(), i) - vec.begin()); int R = int(lower_bound(vec.begin(), vec.end(), k) - vec.begin()); ans += (ll)(R - L); } } // ----- HEAVY: quét toàn mảng cho từng y nặng for (int y : heavyY) { // cntI[t] = số i đã thấy (i < hiện tại) với a[i]=y và b[i]=t unordered_map<int, int> cntI; cntI.reserve(T * 4); // P[x] = số cặp (i, j) đã tạo với i có a[i]=y, b[i]=b[j], j có a[j]=x (và i<j) unordered_map<int, long long> P; P.reserve(T * 8); for (int t = 0; t < n; ++t) { // 1) k = t (b[k] = y): cộng số cặp (i, j) có j < k, i < j if (b[t] == y) { auto itP = P.find(a[t]); if (itP != P.end()) ans += itP->second; } // 2) j = t: tạo cặp (i, j) với mọi i trước đó thỏa a[i]=y, b[i]=b[j] P[a[t]] += (long long)cntI[b[t]]; // 3) i = t: thêm i vào kho với a[i]=y if (a[t] == y) cntI[b[t]]++; } } return ans; } // Đếm tổng số bộ ba dựa trên các điều kiện của sếp static long long count_triples(vector<int> H) { res = 0; int n = (int)H.size(); // #TH: a[k] max for (int k = 2; k < n; k ++) { int i = k - H[k]; if (i < 0 || H[i] >= H[k]) continue; int j1 = k - H[i], j2 = i + H[i]; if (j1 < 0 || H[j1] >= H[k] || H[j1] != j1 - i) j1 = -1; if (j2 >= k || H[j2] >= H[k] || H[j2] != k - j2) j2 = -1; if (j1 != -1) add("A[k] Max: ", i, j1, k); if (j2 != -1 && j1 != j2) add("A[k] Max: ", i, j2, k); } // #TH: a[i] max for (int i = 0; i + 2 < n; i ++) { int k = i + H[i]; if (k >= n || H[k] >= H[i]) continue; int j1 = k - H[k], j2 = i + H[k]; if (j1 < 0 || H[j1] >= H[i] || H[j1] != j1 - i) j1 = -1; if (j2 >= k || H[j2] >= H[i] || H[j2] != k - j2) j2 = -1; if (j1 != -1) add("A[i] Max: ", i, j1, k); if (j2 != -1 && j1 != j2) add("A[i] Max: ", i, j2, k); } // #TH: a[j] max, j - i = a[i] for (int i = 0; i + 2 < n; i ++) { int j = i + H[i]; if (j >= n || H[j] <= H[i]) continue; int k = i + H[j]; if (k >= n || H[k] >= H[j] || k - H[k] != j || k - j == H[i]) k = -1; if (k != -1) add("A[j] Ma1: ", i, j, k); } // Phần còn lại (A[j] Ma2) quy về đếm với a[i]=i+H[i], b[i]=i-H[i] vector<int> a(n), b(n); for (int i = 0; i < n; i ++) a[i] = H[i] + i; for (int i = 0; i < n; i ++) b[i] = i - H[i]; res += countr(a, b); return res; } // -------------------- hàm dựng đạt full điểm -------------------- // Ý tưởng: làm việc trên hệ toạ độ (x, y) = (i - H[i], i + H[i]). // Tạo đủ N điểm sao cho các tổng x+y phủ 0,2,4,...,2N-2 (mỗi tổng xuất hiện 1 lần). // Khi ánh xạ ngược: p=(x+y)/2 là vị trí, h=(y-x)/2 là H[p]. Ta có H[0]=1 từ tổng 0 (điểm (-1,1)), // còn các tổng chẵn cung cấp p=1..N-1. Cấu trúc này tạo rất nhiều bộ ba dạng "A[j] là max". std::vector<int> construct_range(int n, int k) { const int N = n; vector<int> H(N, 1); // Seed cho p=0: (x,y)=(-1,1) -> H[0]=1 vector<int> X; X.reserve(N); X.push_back(-1); vector<int> Y; Y.reserve(N); Y.push_back(1); // S là tập các số chẵn đã chọn để ghép (khởi tạo với 0) vector<int> S; S.reserve(N); S.push_back(0); // usedSum[t] đánh dấu tổng t = x + y đã được dùng (0..2N-2) vector<char> usedSum(2 * N, 0); usedSum[0] = 1; // Score cho các số chẵn ứng viên; NEG để đánh dấu không hợp lệ const int NEG = -1000000000; 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); }; // Lặp: chọn một giá trị chẵn 'opt' thêm vào S, cố gắng tạo các tổng mới x+opt chưa dùng while ((int)X.size() < N) { int opt = pick_best_even(); if (opt == -1) break; // không còn tổng chẵn mới trong [0..2N-2] for (int x : S) { int s = x + opt; // tổng cần tạo if (s >= 0 && s <= 2 * N - 2 && !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); } // Giảm điểm cho các z có thể trùng lặp tạo ra cùng tổng này for (int y : S) { int z = x + opt - y; if (0 <= z && z < 2 * N) score[z]--; } if ((int)X.size() == N) break; } } // Tăng điểm cho các khoảng i để opt+i còn dư chỗ chưa dùng for (int i = 0; opt + i <= 2 * N - 2; i += 2) if (!usedSum[opt + i] && score[i] != NEG) score[i]++; S.push_back(opt); score[opt] = NEG; } // Dự phòng: nếu vì lý do nào đó chưa đủ N điểm, lấp nốt theo cách tuyến tính 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 - 2 && !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; } } S.push_back(t); } // Ánh xạ (x,y) -> (p,h): p=(x+y)/2, h=(y-x)/2 // Với (-1,1) -> p=0,h=1; với tổng chẵn 2..2N-2 -> p=1..N-1. for (int idx = 0; idx < (int)X.size(); ++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 N nhỏ (ví dụ M=20) nếu thiếu K 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; } // -------------------- main tối giản (có thể bỏ nếu harness tự gọi construct_range) -------------------- int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long k; if (!(cin >> n >> k)) return 0; auto H = construct_range(n, (int)k); for (int i = 0; i < n; ++i) { if (i) cout << ' '; cout << H[i]; } cout << '\n'; // #ifdef LOCAL // cerr << "triples = " << count_triples(H) << "\n"; // #endif return 0; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccnTS4Qk.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccywVwyI.o:triples.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccnTS4Qk.o: in function `main':
grader.cpp:(.text.startup+0x37b): undefined reference to `count_triples(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status