Submission #1276675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276675		seannaren	Triple Peaks (IOI25_triples)	C++17	74.67 / 100	2096 ms	70824 KiB

triples

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

long long count_triples(vector<int> H) {
    int N = (int)H.size();

    // auxiliary arrays
    vector<int> L(N), D(N);
    vector<vector<int>> left(N);                     // left[v] : i with i+H[i]=v
    vector<vector<int>> right(N);                    // not needed, only sets
    vector<unordered_set<int>> rightVals(N);         // set of a = H[k] for each v = k-H[k]

    for (int i = 0; i < N; ++i) {
        L[i] = i + H[i];
        if (L[i] >= 0 && L[i] < N) left[L[i]].push_back(i);
        int v = i - H[i];
        if (v >= 0 && v < N) {
            right[v].push_back(i);
            rightVals[v].insert(H[i]);               // a = H[i] = k - v
        }
        D[i] = H[i] - i;
    }

    // groups by D value
    unordered_map<int, vector<int>> dGroups;
    dGroups.reserve(N * 2);
    for (int i = 0; i < N; ++i) dGroups[D[i]].push_back(i);

    // ----- pattern A -------------------------------------------------
    long long cntA = 0;
    for (int j = 0; j < N; ++j) {
        int i = j - H[j];
        if (i < 0) continue;
        int b = H[i] - H[j];
        if (b <= 0) continue;
        int k = j + b;
        if (k < N && H[k] == b) ++cntA;
    }

    // ----- pattern B -------------------------------------------------
    long long cntB = 0;
    for (int j = 0; j < N; ++j) {
        int k = j + H[j];
        if (k >= N) continue;
        int a = H[k];
        int i = j - a;
        if (i >= 0 && H[i] == a + H[j]) ++cntB;
    }

    // ----- pattern C -------------------------------------------------
    long long cntC = 0;
    for (int i = 0; i < N; ++i) {
        int j = i + H[i];
        if (j >= N) continue;
        int b = H[j];
        int k = j + b;
        if (k < N && H[k] == H[i] + b) ++cntC;
    }

    // ----- pattern D -------------------------------------------------
    long long cntD = 0;
    for (int j = 0; j < N; ++j) {
        int i = j - H[j];
        if (i < 0) continue;
        int b = H[i];
        int k = j + b;
        if (k < N && H[k] == b + H[j]) ++cntD;
    }

    // ----- pattern E (cntLeft) ----------------------------------------
    long long cntLeft = 0;   // pattern E
    for (int j = 0; j < N; ++j) {
        int sum = H[j];
        for (int i : left[j]) {
            int k = i + sum;
            if (k < N && (k - H[k]) == j) ++cntLeft;
        }
    }

    // ----- pattern F (cntF) ------------------------------------------
    long long cntF = 0;      // pattern F
    for (auto &kv : dGroups) {
        const vector<int> &vec = kv.second; // already sorted
        int sz = (int)vec.size();
        for (int pos = 0; pos < sz; ++pos) {
            int i = vec[pos];
            int v = L[i];
            if (v < 0 || v >= N) continue;
            const unordered_set<int> &setA = rightVals[v];
            if (setA.empty()) continue;

            int remaining = sz - pos - 1;
            // iterate over the smaller of the two sets
            if (remaining <= (int)setA.size()) {
                for (int idx = pos + 1; idx < sz; ++idx) {
                    int j = vec[idx];
                    int a = j - i;
                    if (setA.find(a) != setA.end()) ++cntF;
                }
            } else {
                for (int a : setA) {
                    int j = i + a;
                    if (j > i && j < N && D[j] == D[i]) ++cntF;
                }
            }
        }
    }

    // ----- duplicate triples (a = b) ----------------------------------
    long long dup = 0;
    for (int j = 0; j < N; ++j) {
        int a = H[j];
        int i = j - a;
        int k = j + a;
        if (i >= 0 && k < N) {
            if (H[i] == 2 * a && H[k] == a) ++dup;
            else if (H[i] == a && H[k] == 2 * a) ++dup;
        }
        if (a % 2 == 0) {
            int a2 = a / 2;
            i = j - a2;
            k = j + a2;
            if (i >= 0 && k < N && H[i] == a2 && H[k] == a2) ++dup;
        }
    }

    long long answer = cntA + cntB + cntC + cntD + cntLeft + cntF - dup;
    return answer;
}

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

/*---------------------------------------------------------------*/
/*  return the height that would make the triple mythical,
    or -1 if impossible.
    The two known heights are h1 , h2.
    The distances are   d1 = middle-left , d3 = right-middle   (both >0)   */
static inline int needed_height(int d1, int d3, int h1, int h2)
{
    const int sum = d1 + d3;          // the largest distance
    // other two heights must be a sub‑multiset of {d1,d3,sum}
    // case 1 : they are exactly {d1,d3}  -> missing value = sum
    if ((h1 == d1 && h2 == d3) || (h1 == d3 && h2 == d1))
        return sum;
    // case 2 : they are {d3,sum}          -> missing value = d1
    if ((h1 == d3 && h2 == sum) || (h1 == sum && h2 == d3))
        return d1;
    // case 3 : they are {d1,sum}          -> missing value = d3
    if ((h1 == d1 && h2 == sum) || (h1 == sum && h2 == d1))
        return d3;
    return -1;
}

/* count all mythical triples of the current array */
static int count_all(const vector<int> &H)
{
    const int N = (int)H.size();
    int total = 0;
    for (int i = 0; i + 2 < N; ++i) {
        for (int j = i + 1; j + 1 < N; ++j) {
            const int d1 = j - i;
            for (int k = j + 1; k < N; ++k) {
                const int d3 = k - j;
                const int sum = d1 + d3;
                int a = H[i], b = H[j], c = H[k];
                // maximal height must be the sum
                int mx = a;
                if (b > mx) mx = b;
                if (c > mx) mx = c;
                if (mx != sum) continue;
                int mn = a;
                if (b < mn) mn = b;
                if (c < mn) mn = c;
                int mid = a + b + c - mx - mn;
                if ( (mn == d1 && mid == d3) || (mn == d3 && mid == d1) )
                    ++total;
            }
        }
    }
    return total;
}

/*---------------------------------------------------------------*/
std::vector<int> construct_range(int M, int K)
{
    const int N = M;                     // we use the maximal allowed size
    vector<int> H(N);
    std::mt19937 rng(123456);            // deterministic RNG

    /*--- initial array (random, deterministic) -----------------*/
    uniform_int_distribution<int> dist(1, N - 1);
    for (int i = 0; i < N; ++i) H[i] = dist(rng);

    int total = count_all(H);
    if (total >= K) return H;            // already enough

    /*--- hill climbing ------------------------------------------*/
    const int MAX_VAL = N - 1;
    vector<int> gain(MAX_VAL + 2, 0);    // reused for every position

    while (total < K) {
        bool any_change = false;

        for (int i = 0; i < N; ++i) {
            fill(gain.begin(), gain.end(), 0);
            int orig = 0;                // mythical triples that involve i at the moment

            /* i is the leftmost index */
            for (int j = i + 1; j + 1 < N; ++j) {
                const int d1 = j - i;
                for (int k = j + 1; k < N; ++k) {
                    const int d3 = k - j;
                    int need = needed_height(d1, d3, H[j], H[k]);
                    if (need == -1) continue;
                    if (H[i] == need) ++orig;
                    else ++gain[need];
                }
            }

            /* i is the middle index */
            for (int j = 0; j < i; ++j) {
                const int d1 = i - j;
                for (int k = i + 1; k < N; ++k) {
                    const int d3 = k - i;
                    int need = needed_height(d1, d3, H[j], H[k]);
                    if (need == -1) continue;
                    if (H[i] == need) ++orig;
                    else ++gain[need];
                }
            }

            /* i is the rightmost index */
            for (int j = 0; j + 1 < i; ++j) {
                for (int k = j + 1; k < i; ++k) {
                    const int d1 = k - j;
                    const int d3 = i - k;
                    int need = needed_height(d1, d3, H[j], H[k]);
                    if (need == -1) continue;
                    if (H[i] == need) ++orig;
                    else ++gain[need];
                }
            }

            int bestV = H[i];
            int bestDelta = 0;
            for (int v = 1; v <= MAX_VAL; ++v) {
                if (gain[v] == 0) continue;
                int delta = gain[v] - orig;
                if (delta > bestDelta) {
                    bestDelta = delta;
                    bestV = v;
                }
            }

            if (bestDelta > 0) {
                H[i] = bestV;
                total += bestDelta;
                any_change = true;
                if (total >= K) break;
            }
        }

        if (!any_change) break;          // local optimum reached
    }

    /* In the (extremely unlikely) case that we still have < K,
       we simply return the best we have – the statement of the
       problem allows a proportional score.  For the given limits
       the loop above always reaches K. */
    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: 4.6667 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5