| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1254613 | ro9669 | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
using namespace std;
int n;
vector<int> a;
bool ok(int i , int j , int k){
if (k >= sz(a)) return false;
vector<int> X = {j - i , k - j , k - i};
vector<int> Y = {a[i] , a[j] , a[k]};
sort(all(X)); sort(all(Y));
bool check = true;
for (int id = 0 ; id < 3 ; id++){
if (X[id] != Y[id]) return false;
}
return true;
}
namespace sub1{
bool check(){
return (sz(a) <= 100);
}
long long solve(){
int n = sz(a);
long long ans = 0;
for (int i = 0 ; i < n ; i++){
for (int j = i + 1 ; j < n ; j++){
for (int k = j + 1 ; k < n ; k++){
if (ok(i , j , k)) ans++;
}
}
}
return ans;
}
}
namespace sub2{
bool check(){
for (int x : a){
if (x > 10) return false;
}
return true;
}
long long solve(){
int n = sz(a);
long long ans = 0;
for (int i = 0 ; i < n ; i++){
for (int j = i + 1 ; j <= min(i + 10 , n - 1) ; j++){
for (int k = j + 1 ; k <= min(j + 10 , n - 1) ; k++){
if (ok(i , j , k)) ans++;
}
}
}
return ans;
}
}
namespace sub3{
bool check(){
return (sz(a) <= 2000);
}
long long solve(){
int n = sz(a);
long long ans = 0;
for (int i = 0 ; i < n ; i++){
for (int j = i + 1 ; j < n ; j++){
if ((j - i != a[i]) && (j - i != a[j])){
if (ok(i , j , j + min(a[i] , a[j]))) ans++;
}
else{
int x = (j - i == a[i]) ? a[j] : a[i];
if (ok(i , j , i + x)) ans++;
if (ok(i , j , j + x)) ans++;
}
}
}
return ans;
}
}
long long count_triples(vector<int> a){
if (sub1::check()) return sub1::solve();
if (sub2::check()) return sub2::solve();
if (sub3::check()) return sub3::solve();
return 0;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("templete.inp" , "r" , stdin);
freopen("templete.out" , "w" , stdout);
cin >> n; a.resize(n);
for (int &x : a) cin >> x;
cout << count_triples(a) << "\n";
return 0;
}