Submission #1255829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255829		AlesL0	Triple Peaks (IOI25_triples)	C++20	16.29 / 100	96 ms	9748 KiB

triples

#include <bits/stdc++.h>
#include "triples.h"

using namespace std;

typedef long long ll;

bool check_triple(vector <int> a, vector <int> b){
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    if (a[0] != b[0] || a[1] != b[1] || a[2] != b[2])return 0;
    return 1;
}

void find_triples(vector <tuple<int, int, int>> &triples, ll n, vector <int> &H, int i, int j){
    for (int x : {i, j}){
        for (int y : {-H[j], H[j]}){
            int z = x+y;
            if (z < 0 || z >= n || z == i || z == j)continue;
            if (check_triple({abs(i-j), abs(i-z), abs(j-z)}, {H[i], H[j], H[z]})){
                vector <int> v = {i, j, z};
                sort(v.begin(), v.end());
                triples.push_back({v[0], v[1], v[2]});
            }
        }
    }
}

/*bool cmp_triple(tuple <int, int, int> a, tuple <int, int, int> b){
    if (get<0>(a) == get<0>(b)){
        if (get<1>(a) == get<1>(b))return (get<2>(a) < get<2>(b));
        return (get<1>(a) < get<1>(b));
    }
    return (get<0>(a) < get<0>(b));
}*/

long long count_triples(std::vector<int> H) {
    ll n = H.size();
    vector <tuple <int, int, int>> triples;
    for (int i = 0; i < n; i++){
        if (i-H[i] >= 0)find_triples(triples, n, H, i, i-H[i]);
        if (i+H[i] < n)find_triples(triples, n, H, i, i+H[i]);
    }
    sort(triples.begin(), triples.end());
    ll count = 0;
    if (!triples.empty()){
        //cerr << get<0>(triples[0]) << " " << get<1>(triples[0]) << " " << get<2>(triples[0]) << "\n";
        count++;
    }
    for (int i = 1; i < triples.size(); i++){
        if (triples[i] != triples[i-1]){
            count++;
            //cerr << get<0>(triples[i]) << " " << get<1>(triples[i]) << " " << get<2>(triples[i]) << "\n";
        }
    }

    vector <pair <ll, ll>> h(n);
    for (int i = 0; i < n; i++)h[i] = {H[i], i};
    sort(h.begin(), h.end());
    reverse(h.begin(), h.end());
    ll cur = -1;
    for (int i = 0; i < n; i++){
        while (cur < n-1 && h[cur+1].first > 2*h[i].first)cur++;
    }

    return count;
}

std::vector<int> construct_range(int M, int K) {
    ll n = M;
    vector <int> v(n);
    for (int i = 0; i < n/2; i++)v[i] = i+1;
    for (int i = n/2; i < n-1; i++)v[i] = n-i-1;
    v[n-1] = 1;
    return v;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 11 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 3 / 5
• Subtask 8: 1.245 / 5
• Subtask 9: 0.4998 / 5
• Subtask 10: 0.2143 / 5
• Subtask 11: 0.25 / 5
• Subtask 12: 0.0833 / 5