Submission #1267050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267050		Canuc80k	Triple Peaks (IOI25_triples)	C++20	100 / 100	1407 ms	44464 KiB

triples

#include <bits/stdc++.h>
using namespace std;

// ==================== Helpers (internal linkage) ====================
namespace {

inline uint64_t pack2(int x, int y) {
    return ( (uint64_t)(uint32_t)x << 32 ) | (uint32_t)y;
}

// Đếm các bộ ba thuộc “nhánh A[j] là max” bằng kỹ thuật heavy/light
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));

    unordered_map<int, vector<int>> posA;
    posA.reserve(n * 2);
    for (int i = 0; i < n; ++i) posA[a[i]].push_back(i);

    unordered_map<uint64_t, vector<int>> posPair;
    posPair.reserve(n * 2);
    for (int i = 0; i < n; ++i) posPair[pack2(a[i], b[i])].push_back(i);

    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
    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;

        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 = pack2(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])

            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 += (long long)(R - L);
        }
    }

    // HEAVY
    for (int y : heavyY) {
        unordered_map<int, int> cntI;               // b[i] -> đếm i (a[i]=y)
        unordered_map<int, long long> P;            // a[j] -> số cặp (i,j) đã tạo
        cntI.reserve(T * 4);
        P.reserve(T * 8);

        for (int t = 0; t < n; ++t) {
            if (b[t] == y) {
                auto itP = P.find(a[t]);
                if (itP != P.end()) ans += itP->second;
            }
            P[a[t]] += (long long)cntI[b[t]];
            if (a[t] == y) cntI[b[t]]++;
        }
    }

    return ans;
}

} // namespace

// ==================== API expected by grader ====================

// Đếm tổng số bộ ba theo đặc tả bài (giữ giao diện như grader gọi)
long long count_triples(std::vector<int> H) {
    long long res = 0;
    int n = (int)H.size();

    // Case: 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) res++;
        if (j2 != -1 && j1 != j2) res++;
    }

    // Case: 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) res++;
        if (j2 != -1 && j1 != j2) res++;
    }
    
    // Case: 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) res++;
    }

    // Case còn lại quy về đếm bằng a = i+H[i], b = 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 (không cần main; grader sẽ gọi)
std::vector<int> construct_range(int n, int k) {
    const int N = n;
    vector<int> H(N, 1);

    // ==================== Phase 1: dựng khung (tọa độ) ====================
    // 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(max(2, 2 * N), 0);
    usedSum[0] = 1;

    const int NEG = -1000000000;
    vector<int> score(max(2, 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 < (int)score.size()) 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);
    }

    // ==================== Phase 2: booster mạnh cho N nhỏ (N ≤ 200) ====================
    if (N <= 200) {
        auto cur = count_triples(H);
        if (cur < k) {
            // ---- (A) Coordinate-descent nhiều lượt
            for (int outer = 0; outer < 6 && cur < k; ++outer) {
                bool improved = false;
                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]) {
                        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;
                        improved = true;
                    }
                }
                if (!improved) break;
            }

            // ---- (B) 2-opt: thử swap cặp & tinh chỉnh cục bộ
            if (cur < k) {
                bool changed = true;
                for (int round = 0; round < 3 && changed && cur < k; ++round) {
                    changed = false;
                    for (int i = 0; i < N && cur < k; ++i) {
                        for (int j = i + 1; j < N && cur < k; ++j) {
                            if (H[i] != H[j]) {
                                swap(H[i], H[j]);
                                long long cand = count_triples(H);
                                if (cand > cur) { cur = cand; changed = true; continue; }
                                swap(H[i], H[j]);
                            }
                            // chỉnh một đầu nhanh với vài giá trị "đinh"
                            int candvals[6] = {1, 2, 3, N-1, N-2, max(1, j - i)};
                            for (int t = 0; t < 6 && cur < k; ++t) {
                                int old = H[i];
                                int v = candvals[t];
                                if (v == old) continue;
                                H[i] = v;
                                long long cand = count_triples(H);
                                if (cand > cur) { cur = cand; changed = true; break; }
                                H[i] = old;
                            }
                        }
                    }
                }
            }

            // ---- (C) Shake (deterministic RNG) để thoát kẹt local max
            if (cur < k) {
                uint64_t seed = 1469598103934665603ULL; // FNV offset
                auto rnd = [&seed]() -> uint32_t {
                    // xorshift64* deterministic
                    seed ^= seed >> 12; seed ^= seed << 25; seed ^= seed >> 27;
                    return (uint32_t)((seed * 2685821657736338717ULL) >> 32);
                };

                vector<int> bestH = H;
                long long bestCnt = cur;

                for (int it = 0; it < 200 && bestCnt < k; ++it) {
                    vector<int> T = bestH;
                    int mflip = 2 + (it % 4); // 2..5 vị trí
                    for (int t = 0; t < mflip; ++t) {
                        int idx = (int)(rnd() % N);
                        int val = 1 + (int)(rnd() % (N - 1));
                        T[idx] = val;
                    }
                    long long cand = count_triples(T);
                    if (cand > bestCnt) {
                        bestCnt = cand;
                        bestH.swap(T);
                    }
                }
                H.swap(bestH);
            }
        }
    }

    return H;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 16 / 16
• Subtask 6: 19 / 19
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5