Submission #1259015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259015		Sorting	3개의 봉우리 (IOI25_triples)	C++20	34 / 100	2096 ms	14252 KiB

triples

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <iomanip>
#include <queue>
#include <stack>
#include <numeric>
#include <cassert>
#include <cmath>
#include <random>
#include <ctime>
#include <chrono>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)x.size())
#define rep(i, a, b) for(int i = a; i < b; ++i)

template<typename C> struct rge{C l, r;};
template<typename C> rge<C> range(C i, C j) { return rge<C>{i, j}; }
template<typename C> ostream& operator<<(ostream &os, rge<C> r) { os << '{'; for(auto it = r.l; it != r.r; it++) os << "," + (it == r.l) << *it; os << '}'; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '{' << p.first << "," << p.second << '}'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ","; return os << '}'; }
void dbg_out() { cerr << ']' << endl; }
template<typename A> void dbg_out(A H) { cerr << H; dbg_out(); }
template<typename A, typename B, typename... C> void dbg_out(A H, B G, C... T) { cerr << H << ","; dbg_out(G, T...); }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = [", dbg_out(__VA_ARGS__)
#else
#define debug(...)
#endif

template <typename T>
void remove_duplicates(vector<T> &v){
    sort(all(v));
    v.resize(unique(all(v)) - v.begin());
}

template <typename T> void chmin(T &a, T b){ a = (b < a) ? b : a; }
template <typename T> void chmax(T &a, T b){ a = (b > a) ? b : a; } 

ll n;
vi h;

ll count_easy() {
    set<array<int, 3>> triples;

    auto test3 = [&](int a, int b, int c) {
        if (c < 0 || c >= n) {
            return;
        }
        int arr[3]{a, b, c};
        sort(arr, arr + 3);
        a = arr[0];
        b = arr[1];
        c = arr[2];

        int diffs[3]{b - a, c - b, c - a};
        int vals[3]{h[a], h[b], h[c]};
        sort(diffs, diffs + 3);
        sort(vals, vals + 3);

        for (int i = 0; i < 3; ++i) {
            if (diffs[i] != vals[i]) {
                return;
            }
        }

        triples.insert({a, b, c});
    };

    auto test2 = [&](int a, int b) {
        if (b < 0 || b >= n) {
            return;
        }
        test3(a, b, a + h[b]);
        test3(a, b, a - h[b]);
        test3(a, b, b + h[b]);
        test3(a, b, b - h[b]);
    };

    for (int i = 0; i < n; ++i) {
        test2(i, i - h[i]);
        test2(i, i + h[i]);
    }
    return triples.size();
}

ll count_triples(vector<int> H) {
    swap(H, h);
    n = h.size();

    ll ans = count_easy();
    for (int i = 0; i < n; ++i) {
        int j = i + h[i];
        int k = j + h[i];

        if (k >= n) {
            continue;
        }
        ans -= h[k] == h[i] && h[j] == 2 * h[i];
    }

    for (int i = 0; i < n; ++i) {
        int j = i + 1;
        int k = j + h[i];
        for (; k < n; ++j, ++k) {
            ans += (h[j] == (k - i)) && (h[k] == (j - i));
        }
    }
    return ans;
}

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

#ifdef LOCAL_TEST
int main() {
    vector<int> H = {4,1,4,3,2,6,1};
    cout << count_triples(H) << "\n"; // 3
}
#endif

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 6
• Subtask 3: 10 / 10
• Subtask 4: 0 / 11
• Subtask 5: 16 / 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