Submission #1250517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250517		fafnir	Triple Peaks (IOI25_triples)	C++20	8 / 100	2093 ms	1864 KiB

triples

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

// #define LOCAL

// Part I
const long long CON = 100;

long long chash(int i, int j, int k) {
    array<int,3> coords{i,j,k};
    sort(coords.begin(), coords.end());
    long long h = coords[0];
    h += CON * coords[1];
    h += CON * CON * coords[2];
    return h;
}

bool checkTriple(int i, int j, int k, vector<int>& h) {
    const int n = h.size();
    array<int,3> a{abs(i-j),abs(j-k),abs(k-i)};

    array<int,3> b{h[i], h[j], h[k]};
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    return a == b;
}


long long count_triples(vector<int> H) {
    const int n = H.size();
    long long cnt = 0;
    unordered_set<long long> cs;
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            int hi = H[i];
            int hj = H[j];
            for (auto& k : vector<int>{i-hi,i+hi,i-hj,i+hj,j-hi,j+hi,j-hj,j+hj}) {
                if (checkTriple(i,j,k,H)) {
                    cs.insert(chash(i,j,k));
                    break;
                }
            }
            
        }
    }

    return cs.size();
}

std::vector<int> construct_range(int M, int K) {
    return {};
}



#ifdef LOCAL
int32_t main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (auto& e : a) cin >> e;

    cout << count_triples(a) << '\n';


    return 0;
}
#endif

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