Submission #1285913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285913		eri16	Triple Peaks (IOI25_triples)	C++20	44.24 / 100	1541 ms	40200 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;
    
    int maxh=0;
    
    for (int i=0; i<n; i++){
        maxh=max(maxh,h[i]);
    }
    
    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 if(maxh<=10){    
    
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n && j<=i+10; j++){
            for (int t=j+1; t<n && t<=j+10; t++){
                
                vector <int> v,v1;
                v.push_back(h[i]);
                v.push_back(h[j]);                
                v.push_back(h[t]);
                
                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;}
                }
                
                ans+=qwe;
                
                
            }
        }
    }
    
    return(ans);
    }
    
    else{
    //The heights are non-decreasing.
    //That is, H[i − 1] ≤ H[i] for each i such that 1 ≤ i < N
           
        for (int i=n-1; i>=0; i--){
        
        long long t=i-h[i];
        if (t>=0){
        long long j1=t+h[t];
        long long j2=i-h[t];
        if (j1<n){
        if (i==j1+h[j1]){ans++;}
        }
        if (j2>=0 && j1!=j2){
        if (t==j2-h[j2]){ans++;}    
        }    
        }
        }
        return (ans);    
    }
}
    
    


    
vector<int> construct_range(int M, int K){
    vector <int> v,v1;
    
    v1={5, 2, 3, 3, 1, 2, 1, 4, 3, 2, 7, 6, 5, 6, 3, 4, 1, 2, 1, 3};
        
    for (int i=0; i<M; i++){
        v.push_back(v1[i%20]);
    }


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

//

• 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: 5 / 5
• Subtask 8: 2.305 / 5
• Subtask 9: 0.9247 / 5
• Subtask 10: 0.3964 / 5
• Subtask 11: 0.4625 / 5
• Subtask 12: 0.1542 / 5