Submission #1275985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275985		sakibulislam	Triple Peaks (IOI25_triples)	C++20	13.65 / 100	29 ms	24236 KiB

triples

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

long long count_triples(std::vector<int> H) {
    int n = H.size();

    ll ans = 0LL;

    for (int i=0; i<n; i++){
        int k = i+H[i];

        if (k<n && H[k]<H[i]){
            if (H[i+H[k]]==H[i]-H[k])
                ans++;
            if (2*H[k]!=H[i] && H[k-H[k]]==H[i]-H[k])
                ans++;
        }

    }


    for (int k=0; k<n; k++){
        int i = k-H[k];
        if (i>=0 && H[i]<H[k]){
            if (H[k-H[i]]==H[k]-H[i])
                ans++;
            if (2*H[i]!=H[k] && H[i+H[i]]==H[k]-H[i])
                ans++;
        }
    }

    for (int i=0; i<n; i++){
        int j = i+H[i];
        if (j<n && H[j]>H[i]){
            int k = i+H[j];

            if (k<n && H[k]+H[i]==H[j])
                ans++;
        }
    }


    vector<int> pp[2*n+1];

    for (int i=0; i<n; i++){
        pp[i-H[i]+n].push_back(i);
    }

    int rt = (int)sqrt(n);

    for (int x=0; x<=2*n; x++){
        if (pp[x].size()<=rt){
            for (int a=0; a<pp[x].size(); a++){
                int j = pp[x][a];
                for (int b=0; b<a; b++){
                    int i = pp[x][b];
                    int k = i+H[j];
                    if (H[i]<H[j] && k<n){
                        if (H[i]+H[k]==H[j])
                            ans++;
                    }

                }
            }
        }
        else{
            for (int k=0; k<n; k++){
                int sum = x-n+k;
                int diff = H[k];

                if (diff%2==sum%2){
                    int i = (sum-diff)/2;
                    int j = (sum+diff)/2;

                    if (i>-1 && j>-1 && i-H[i]+n==x && j-H[j]+n==x)
                        ans++;

                }
            }
        }
    }
    return ans;
}

std::vector<int> construct_range(int M, int K) {
    vector<int> r = {1, 2, 1};
    for (int i=3; i<M; i++)
        r.push_back(i%2+1);
    return r;
}

• 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: 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