Submission #1312937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312937		pedreitorzelda	Triple Peaks (IOI25_triples)	C++20	14.53 / 100	2094 ms	1948 KiB

triples

#include<bits/stdc++.h>
using namespace std;

vector<int>construct_range(int M,int K){
    vector<int>a(M);
    for(int i=0;i<M;i++){
        if(i%4==0||i%4==2)a[i]=1;
        else if(i%4==1)a[i]=2;
        else a[i]=3;
    }return a;
    
}
bool check(int i1,int i2,int i3,vector<int>&H,set<tuple<int,int,int>>&s){
    vector<int>H_i = {H[i1],H[i2],H[i3]};
    sort(H_i.begin(),H_i.end());
    vector<int>H_i_2 ={abs(i2-i1),abs(i3-i1),abs(i3-i2)};
    sort(H_i_2.begin(),H_i_2.end());
    if(H_i[0]==H_i_2[0]&&H_i[1]==H_i_2[1]&&H_i[2]==H_i_2[2]){
        vector<int>ind = {i1,i2,i3};
        sort(ind.begin(),ind.end());
        if(s.find({ind[0],ind[1],ind[2]})!=s.end())return false;
        s.insert({ind[0],ind[1],ind[2]});
        //cout << i1 << " " << i2 << " " << i3 << endl;
        return true;
    }else return false;
}
long long count_triples(vector<int>H){
    set<tuple<int,int,int>>s;
    int n = H.size();
    int cant =0 ;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){//i+H[i],i-H[i],j+H[i],j-H[i]
            if(check(i,j,i+H[i],H,s)){
                cant++;
            }else if(check(i,j,i+H[j],H,s)){
                cant++;
            }else if(check(i,j,i-H[i],H,s)){
                cant++;
            }else if(check(i,j,i-H[j],H,s)){
                cant++;
            }else if(check(i,j,j+H[i],H,s)){
                cant++;
            }else if(check(i,j,j+H[j],H,s)){
                cant++;
            }else if(check(i,j,j-H[i],H,s)){
                cant++;
            }else if(check(i,j,j-H[j],H,s)){
                cant++;
            }
        }
    }return cant;
}
/*

si hay alguno q cuadra --> cuatro para un lado y simetrico y hecho, simulas
si ninguno cuadra-->

4--6----2

*//*
signed main(){
    cout << count_triples({4,1,4,3,2,6,1}) << '\n';
    vector<int>ans = construct_range(18,30);
    for(auto it : ans)cout << it << " ";
    cout << '\n';
    cout << count_triples(construct_range(18,30)) << '\n';
}*/

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 3.6667 / 5
• Subtask 8: 1.555 / 5
• Subtask 9: 0.6247 / 5
• Subtask 10: 0.2678 / 5
• Subtask 11: 0.3125 / 5
• Subtask 12: 0.1042 / 5