Submission #1250048

#TimeUsernameProblemLanguageResultExecution timeMemory
1250048testacc11Triple Peaks (IOI25_triples)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int part; if(!(cin >> part)) return 0; if(part != 1){ // This is Part I only. return 0; } int N; cin >> N; vector<int> H(N); for(int i = 0; i < N; i++){ cin >> H[i]; } // Precompute: // L1[j] = all i < j with i + H[i] == j (so H[i] = j - i) // S[T] = all k with k + H[k] == T vector<vector<int>> L1(N); vector<vector<int>> S(N + N); // k+H[k] in [0..2N-2] for(int i = 0; i < N; i++){ int j1 = i + H[i]; if(j1 < N) L1[j1].push_back(i); int T = i + H[i]; S[T].push_back(i); } ll ans = 0; // Main loop over the “middle” peak j for(int j = 0; j < N; j++){ int hj = H[j]; // Case A: H[j] = d1 = j - i // ⇒ i = j - H[j], check k = j + H[i], and H[k] == H[i]+H[j]. { int i = j - hj; if(i >= 0) { int hi = H[i]; int k = j + hi; if(k < N && hi + hj == H[k]) { ans++; } } } // Case B: H[j] = d2 = k - j // ⇒ k = j + H[j], check i = k - H[k], and H[i] == H[k] - H[j]. { int k = j + hj; if(k < N) { int hk = H[k]; int i = k - hk; if(i < j && i >= 0 && hk - hj == H[i]) { ans++; } } } // Case C1: H[j] = d3 = (k - i), with H[i] = d1 = j - i // ⇒ i in L1[j], then k = i + H[j], and check H[k] = d2 = H[j] - H[i]. for(int i : L1[j]) { int hi = H[i]; int k = i + hj; if(k > j && k < N && H[k] == hj - hi) { ans++; } } // Case C2: H[j] = d3 = (k - i), with H[k] = d1 = j - i // ⇒ all k with k + H[k] = j + H[j] (so H[k] = (j+H[j]) - k = j - (k-j) = d1), // then set i = k - H[j] and check H[i] = d2 = k - j. int Tj = j + hj; if(Tj < (int)S.size()){ for(int k : S[Tj]) { if(k <= j) continue; int i = k - hj; if(i < j && i >= 0 && H[i] == k - j) { ans++; } } } } cout << ans << "\n"; return 0; }

Compilation message (stderr)

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