제출 #1312949

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312949		pedreitorzelda	3개의 봉우리 (IOI25_triples)	C++20	6.53 / 100	2092 ms	23340 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;
}
void try_find(int i,int pos2,int &n,int &cant,vector<int>&H,set<tuple<int,int,int>>&s){
    if(pos2-H[pos2]>=0&&check(i,pos2,pos2-H[pos2],H,s)){
        cant++;
    }if(pos2+H[pos2]<n&&check(i,pos2,pos2+H[pos2],H,s)){
        cant++;
    }if(i-H[pos2]>=0&&check(i,pos2,i-H[pos2],H,s)){
        cant++;
    }if(i+H[pos2]<n&&i+H[pos2]!=pos2-H[pos2]&&check(i,pos2,i+H[pos2],H,s)){
        cant++;
    }
    return;
}
long long count_triples(vector<int>H){
    // strat:
    /*
    - sweepline til one such that H[j]-act_dis = my_i --> non_direct
    - sweepline til one such that H[j]-act_dis = 0 --> direct
    - direct connection of H[i]
    */
   int n = H.size();
   map<int,vector<int>>swip_r;
   for(int i=0;i<n;i++){
        if(swip_r[H[i]-i].empty())swip_r[H[i]-i].push_back(1);
        swip_r[H[i]-i].push_back(i);
   }set<tuple<int,int,int>>s;
   int cant = 0;
    for(int i=0;i<n;i++){
        int cant_eq = 0;
        if(!swip_r[H[i]-i].empty()){
            for(int j=swip_r[H[i]-i][0];j<swip_r[H[i]-i].size();j++){
                int it = swip_r[H[i]-i][j];
                if(it<=i){
                    swip_r[H[i]-i][0]++;
                    continue;
                }
                if(check(i,it,i+H[it],H,s))cant_eq++;
            }
        }
        
        //int extra = 0;
        if(i+H[i]<n)try_find(i,i+H[i],n,cant,H,s);
        if(i-H[i]>=0)try_find(i-H[i],i,n,cant,H,s);
       // cout << i << " ::" << extra << " " << cant_eq << endl; 
        cant+=cant_eq;
    }//cout << cant << "--" << s.size() << endl;
    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: 0 / 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