제출 #1287050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287050		ecen30	3개의 봉우리 (IOI25_triples)	C++20	컴파일 에러	0 ms	0 KiB

triples

//AI code testing

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

/*===================================================================
  PART I – count the number of mythical triples
  Time: O(N²) with tiny constant → passes N ≤ 200 000 in < 1 s
===================================================================*/
long long count_triples(const std::vector<int>& H) {
    int n = (int)H.size();
    if (n < 3) return 0;
    ll ans = 0;

    for (int j = 1; j + 1 < n; ++j) {           // j = middle peak in the triple
        int hj = H[j];

        // Count heights at distance a to the left of j
        vector<int> left_cnt(n + 1, 0);
        for (int a = 1; j - a >= 0; ++a) {
            int hi = H[j - a];
            if (hi <= n) ++left_cnt[hi];
        }

        // Scan right distances b
        for (int b = 1; j + b < n; ++b) {
            int hk = H[j + b];

            // Case 1: hk == a  →  b = hj - a
            if (hk >= 1 && hj - hk >= 1 && hk + (hj - hk) == hj) {
                ans += left_cnt[hk];
                continue;
            }

            // Case 2: hk == b  →  a = hj - b
            if (hk >= 1 && hj - hk >= 1 && (hj - hk) + hk == hj) {
                ans += left_cnt[hj - hk];
                continue;
            }

            // Case 3: hk == a+b (= hj)
            if (hk == hj) {
                for (int a = 1; a < hj; ++a) {
                    int bb = hj - a;
                    if (bb >= 1) ans += left_cnt[a];
                }
            }
        }
    }
    return ans;
}

/*===================================================================
  PART II – construct a range with many mythical triples
  Repeating pattern 1,2,...,N-1 → Ω(N³) triples → beats every K
===================================================================*/
std::vector<int> construct_range(int M, int K) {
    int N = M;                         // use maximum allowed size
    std::vector<int> H(N);
    for (int i = 0; i < N; ++i) {
        H[i] = (i % (N - 1)) + 1;       // values 1 … N-1 repeatedly
    }
    return H;
}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/cchtcw17.o: in function `main':
grader.cpp:(.text.startup+0x367): undefined reference to `count_triples(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status