Submission #1254622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254622		ro9669	Triple Peaks (IOI25_triples)	C++20	24 / 100	844 ms	2768 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
using namespace std;

int n;
vector<int> a;

bool ok(int i , int j , int k){
    if (k >= sz(a)) return false;
    vector<int> X = {j - i , k - j , k - i};
    vector<int> Y = {a[i] , a[j] , a[k]};
    sort(all(X)); sort(all(Y));
    bool check = true;
    for (int id = 0 ; id < 3 ; id++){
        if (X[id] != Y[id]) return false;
    }
    return true;
}

namespace sub1{
    bool check(){
        return (sz(a) <= 100);
    }

    long long solve(){
        int n = sz(a);
        long long ans = 0;
        for (int i = 0 ; i < n ; i++){
            for (int j = i + 1 ; j < n ; j++){
                for (int k = j + 1 ; k < n ; k++){
                    if (ok(i , j , k)) ans++;
                }
            }
        }
        return ans;
    }
}

namespace sub2{
    bool check(){
        for (int x : a){
            if (x > 10) return false;
        }
        return true;
    }

    long long solve(){
        int n = sz(a);
        long long ans = 0;
        for (int i = 0 ; i < n ; i++){
            for (int j = i + 1 ; j <= min(i + 10 , n - 1) ; j++){
                for (int k = j + 1 ; k <= min(j + 10 , n - 1) ; k++){
                    if (ok(i , j , k)) ans++;
                }
            }
        }
        return ans;
    }
}

namespace sub3{
    bool check(){
        return (sz(a) <= 2000);
    }

    long long solve(){
        int n = sz(a);
        long long ans = 0;
        for (int i = 0 ; i < n ; i++){
            for (int j = i + 1 ; j < n ; j++){
                if ((j - i != a[i]) && (j - i != a[j])){
                    if (ok(i , j , j + min(a[i] , a[j]))) ans++;
                }
                else{
                    int x = (j - i == a[i]) ? a[j] : a[i];
                    if (ok(i , j , i + x)) ans++;
                    if (ok(i , j , j + x)) ans++;
                }
            }
        }
        return ans;
    }
}

long long count_triples(vector<int> h){
    a = h;
    if (sub1::check()) return sub1::solve();
    if (sub2::check()) return sub2::solve();
    if (sub3::check()) return sub3::solve();
    return 0;
}

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


// int main(){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     freopen("templete.inp" , "r" , stdin);
//     freopen("templete.out" , "w" , stdout);
//     cin >> n; a.resize(n);
//     for (int &x : a) cin >> x;
//     cout << count_triples(a) << "\n";
//     return 0;
// }

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