Submission #1320982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320982		duccw	Triple Peaks (IOI25_triples)	C++20	Compilation error	0 ms	0 KiB

triples

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

ll count_mythical_triples(const vector<int> &H) {
    int N = H.size();
    int maxH = N;
    vector<vector<int>> L(N), R(N);
    for (int t = 0; t < N; ++t) {
        long long jl = (long long)t + H[t];
        if (jl < N) L[jl].push_back(t);
        long long jr = (long long)t - H[t];
        if (jr >= 0) R[jr].push_back(t);
    }

    ll ans = 0;
    vector<int> cnt(maxH + 1, 0);
    vector<int> used; used.reserve(256);
    for (int j = 0; j < N; ++j) {
        if (L[j].empty() || R[j].empty()) continue;
        used.clear();
        for (int idx : R[j]) {
            int h = H[idx];
            if (cnt[h] == 0) used.push_back(h);
            ++cnt[h];
        }
        for (int idx : L[j]) {
            int need = H[j] - H[idx];
            if (need >= 1 && need <= maxH) ans += cnt[need];
        }
        for (int h : used) cnt[h] = 0;
    }

    // Case B: left i holds full distance
    for (int i = 0; i < N; ++i) {
        int b = H[i];
        int k = i + b;
        if (k >= N) continue;
        int t = H[k];
        int val = b - t;
        if (val <= 0) continue;
        int j1 = i + t;
        if (i < j1 && j1 < k && H[j1] == val) ++ans;
        int j2 = k - t;
        if (j2 != j1 && i < j2 && j2 < k && H[j2] == val) ++ans;
    }

    // Case C: right k holds full distance
    for (int k = 0; k < N; ++k) {
        int b = H[k];
        int i = k - b;
        if (i < 0) continue;
        int t = H[i];
        int val = b - t;
        if (val <= 0) continue;
        int j1 = i + t;
        if (i < j1 && j1 < k && H[j1] == val) ++ans;
        int j2 = k - t;
        if (j2 != j1 && i < j2 && j2 < k && H[j2] == val) ++ans;
    }
    return ans;
}

vector<int> construct_range(int M, ll K) {
    // Build pattern [1,2,1,2,...] to produce lots of triples
    int N = M;
    vector<int> H(N);
    for (int i = 0; i < N; ++i) H[i] = (i % 2) + 1;
    // If still not enough triples, pattern can be extended: repeat [1,2,3,1,2,3,...] etc
    return H;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int mode;
    cin >> mode;
    if (mode == 1) {
        int N;
        cin >> N;
        vector<int> H(N);
        for (int i = 0; i < N; ++i) cin >> H[i];
        cout << count_mythical_triples(H) << "\n";
    } else if (mode == 2) {
        int M;
        ll K;
        cin >> M >> K;
        vector<int> H = construct_range(M, K);
        cout << H.size() << "\n";
        for (int i = 0; i < (int)H.size(); ++i) {
            if (i) cout << " ";
            cout << H[i];
        }
        cout << "\n";
    }
}

Compilation message (stderr)

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