| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1255551 | Aviansh | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
bool checkTriple(int i, int j, int k, vector<int>&arr){
if(!(i<j&&j<k)){
return 0;
}
int n = arr.size();
if(i<0||j<0||k<0||i>=n||j>=n||k>=n){
return 0;
}
vector<int>arr1 = {j-i,k-i,k-j};
vector<int>arr2 = {arr[i],arr[j],arr[k]};
sort(arr1.begin(),arr1.end());
sort(arr2.begin(),arr2.end());
if(arr1[0]==arr2[0]&&arr1[1]==arr2[1]&&arr1[2]==arr2[2]){
return 1;
}
return 0;
}
long long count_triples(vector<int> arr) {
int n = arr.size();
set<array<int,3>>triples;
vector<int>mp[1e5+5];
int offset = 50000;
for(int i = 0;i<n;i++){
mp[arr[i]-i+offset].push_back(i);
}
for(int i = 0;i<n;i++){
int a,b,c;
//case 1:
a = i;
b = arr[a]+a;
if(b>=0&&b<n)
c = arr[b]+a;
if(checkTriple(a,b,c,arr)){
triples.insert({a,b,c});
}
//case 2:
a=i;
c=arr[a]+a;
if(c>=0&&c<n)
b=c-arr[c];
if(checkTriple(a,b,c,arr)){
triples.insert({a,b,c});
}
//case 3:
a=i;
c=arr[a]+a;
if(c>=0&&c<n)
b=arr[c]+a;
if(checkTriple(a,b,c,arr)){
triples.insert({a,b,c});
}
//case 4:
a=i;
b=arr[a]+a;
if(b>=0&&b<n)
c=arr[b]+b;
if(checkTriple(a,b,c,arr)){
triples.insert({a,b,c});
}
//case 5:
//later
//case 6:
b=i;
a=b-arr[b];
if(a>=0&&a<n)
c=arr[a]+b;
if(checkTriple(a,b,c,arr)){
triples.insert({a,b,c});
}
}
int ans = 0;
for(int z = 0;z<1e5+5;z++){
pair<int,vector<int>>p={z,mp[z]};
int siz = p.second.size();
for(int i = 0;i<siz;i++){
for(int j = i+1;j<siz;j++){
int a = p.second[i];
int b = p.second[j];
int c = arr[b]+a;
if(c-b==b-a)
continue;
if(checkTriple(a,b,c,arr)){
ans++;
}
}
}
}
return triples.size()+ans;
}
vector<int> construct_range(int M, int K) {
vector<int>arr(M);
for(int i = 0;i<M;i++){
if(i%2){
arr[i]=1;
}
else{
arr[i]=2;
}
}
return arr;
}