제출 #1285791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285791		eri16	3개의 봉우리 (IOI25_triples)	C++20	24 / 100	1531 ms	1984 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{

    for (int i=0; i<n; i++){
        
        long long t=i+h[i];
        long long j=t-h[t];
        
        ans+=solve(h[i],h[j],h[t],i,j,t);
        
   
        }
    }
}
    
    


    
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});
}
*/


//

컴파일 시 표준 에러 (stderr) 메시지

triples.cpp: In function 'long long int count_triples(std::vector<int>)':
triples.cpp:140:1: warning: control reaches end of non-void function [-Wreturn-type]
  140 | }
      | ^

• 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