제출 #1250658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1250658		NekoRolly	3개의 봉우리 (IOI25_triples)	C++20	37.65 / 100	2096 ms	2736 KiB

triples

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

int n;
vector<int> h;

bool same(vector<int> a,vector<int> b){
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int i=0; i<3; i++)
        if (a[i] != b[i]) return false;
    return true;
}

bool check(int i,int j,int k){
    bool flag = 0 <= i && i < j && j < k && k < n && same({k-i, k-j, j-i}, {h[i], h[j], h[k]});
    // if (flag) cout << i << " " << j << " " << k << " <-\n";
    // return 0 <= i && i < j && j < k && k < n && same({k-i, k-j, j-i}, {h[i], h[j], h[k]});
    return flag;
}

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

    bool not_desc = true;
    for (int i=0; i+1<n; i++)
        if (h[i] > h[i+1])
            not_desc = false;

    ll ans = 0;
    for (int i=0; i<n; i++){
        int l = i - h[i];
        int r = i + h[i];
        if (l >= 0){
            ans += check(l, l+h[l], i);
            if (l+h[l] != i-h[l])
                ans += check(l, i-h[l], i);
        }
        if (r < n){
            ans += check(i, r-h[r], r);
            if (r-h[r] != i+h[r])
                ans += check(i, i+h[r], r);
        }
        if (!not_desc){
            l = max(l+1, 0);
            r = min(r-1, n-1);
            for (int j=l; j+h[i]<=r; j++)
                ans += check(j, i, j+h[i]);
        }
    }

    return ans;
}

vector<int> construct_range(int M, int K){
    int md = M/2;
    vector<int> vec(M);

    for (int i=0; i<M; i++){
        if (i == md)
            vec[md] = md;
        else
            vec[i] = abs(i-md);
    }

    return vec;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 1.5 / 5
• Subtask 8: 0.6225 / 5
• Subtask 9: 0.2499 / 5
• Subtask 10: 0.1071 / 5
• Subtask 11: 0.125 / 5
• Subtask 12: 0.0417 / 5