Submission #1285784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285784		eri16	Triple Peaks (IOI25_triples)	C++20	18 / 100	187 ms	3120 KiB

triples

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

using namespace std;

long long solve(int hi,int hj, int ht, int i, int j, int t){
    vector <int> v,v1;
    v.push_back(hi);
    v.push_back(hj);                
    v.push_back(ht);
                
    v1.push_back(j-i);
    v1.push_back(t-j);
    v1.push_back(t-i);
                
    sort(v.begin(),v.end());
    sort(v1.begin(),v1.end());                
                
    int qwe=1;
                
    for (int zz=0; zz<3; zz++){
        if (v[zz]!=v1[zz]){qwe=0;}
    }
                
    return qwe;
}

long long count_triples(vector<int> h) {
    
    long long n=h.size();
    
    long long ans=0;
    if (n<=2000){
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            
            int ds1=j-i;
            
            if (ds1==h[j]){
                int ps1,ps2,ps3,ps4,ds2;                
                ds2=h[i];
                
                ps1=i-ds2;
                ps2=j-ds2;
                ps3=i+ds2;
                ps4=j+ds2;
                
                if (ps1>=0 && ps1<n){ans+=solve(h[i],h[j],h[ps1],i,j,ps1);}
                if (ps2>=0 && ps2<n){ans+=solve(h[i],h[j],h[ps2],i,j,ps2);}
                if (ps3>=0 && ps3<n){ans+=solve(h[i],h[j],h[ps3],i,j,ps3);}
                if (ps4>=0 && ps4<n){ans+=solve(h[i],h[j],h[ps4],i,j,ps4);}
                
            }
            else if (ds1==h[i]){
                int ps1,ps2,ps3,ps4,ds2;                
                ds2=h[j];
                
                ps1=i-ds2;
                ps2=j-ds2;
                ps3=i+ds2;
                ps4=j+ds2;
                
                if (ps1>=0 && ps1<n){ans+=solve(h[i],h[j],h[ps1],i,j,ps1);}
                if (ps2>=0 && ps2<n){ans+=solve(h[i],h[j],h[ps2],i,j,ps2);}
                if (ps3>=0 && ps3<n){ans+=solve(h[i],h[j],h[ps3],i,j,ps3);}
                if (ps4>=0 && ps4<n){ans+=solve(h[i],h[j],h[ps4],i,j,ps4);}                
            }
            
            else if(ds1+min(h[i],h[j])==max(h[i],h[j])){
                int ps1,ps2;
                
                ps1=i-min(h[i],h[j]);
                ps2=j+min(h[i],h[j]);
                
                if (ps1>=0 && ps1<n){ans+=solve(h[i],h[j],h[ps1],i,j,ps1);}
                if (ps2>=0 && ps2<n){ans+=solve(h[i],h[j],h[ps2],i,j,ps2);}                
                

            }
        }
    }
    
    return(ans);
        
    }
    
    else{
    
    vector<vector<int>> pos(11);
    
    for (int i=0; i<n; i++){pos[h[i]].push_back(i);}

    long long ans=0;

    for (int i=0; i<n; i++) {
        int hi=h[i];
        int j1=i+hi;
        int j2=i-hi;

        for (int j : {j1, j2}) {
            if (j<0 || j>=n || j==i) continue;
            int hj=h[j];

            int k1=i+hj;
            int k2=j+hi;
            int k3=j+hj;
            int k4=i-hj;

            for (int k : {k1, k2, k3, k4}) {
                if (k < 0 || k >= n || k == i || k == j) continue;
                vector<int> vals = {hi, hj, h[k]};
                vector<int> dist = {abs(j-i), abs(k-j), abs(k-i)};
                sort(vals.begin(), vals.end());
                sort(dist.begin(), dist.end());
                if (vals == dist) ans++;
            }
        }
    }

    return ans / 3;}
}
    
    


    
vector<int> construct_range(int M, int K) {vector <int> vv;return(vv);}    
/*

int main(){
    cout << count_triples({4, 1, 4, 3, 2, 6, 1});
}
*/


//

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