Submission #1249566

#TimeUsernameProblemLanguageResultExecution timeMemory
1249566Charizard2021Triple Peaks (IOI25_triples)C++20
35 / 100
1073 ms1984 KiB
#include<bits/stdc++.h> #include "triples.h" using namespace std; bool check(int i, int j, int k, int Hi, int Hj, int Hk){ vector<int> v; v.push_back(j - i); v.push_back(k - j); v.push_back(k - i); vector<int> v2; v2.push_back(Hi); v2.push_back(Hj); v2.push_back(Hk); sort(v2.begin(), v2.end()); sort(v.begin(), v.end()); if(v == v2){ return true; } return false; } long long count_triples(vector<int> H){ int n = (int)H.size(); if(n <= 2000){ long long ans = 0; for(int i = 0; i < n; i++){ for(int k = i + 2; k < n; k++){ if(H[k] != k - i && H[i] != k - i){ if(H[k] + H[i] == k - i){ int j1 = i + H[i]; int j2 = i + H[k]; if(i < j1 && j1 < k){ ans += check(i, j1, k, H[i], H[j1], H[k]); } if(i < j2 && j2 < k && j1 != j2){ ans += check(i, j2, k, H[i], H[j2], H[k]); } } } else{ if(H[k] == k - i){ int j1 = i + H[i]; int j2 = k - H[i]; if(i < j1 && j1 < k){ ans += check(i, j1, k, H[i], H[j1], H[k]); } if(i < j2 && j2 < k && j1 != j2){ ans += check(i, j2, k, H[i], H[j2], H[k]); } } if(H[i] == k - i){ int j1 = i + H[k]; int j2 = k - H[k]; if(i < j1 && j1 < k){ ans += check(i, j1, k, H[i], H[j1], H[k]); } if(i < j2 && j2 < k && j1 != j2){ ans += check(i, j2, k, H[i], H[j2], H[k]); } } } } } return ans; } int thing = 0; for(int i = 0; i < n; i++){ thing = max(thing, H[i]); } if(thing <= 10){ 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(i + 10, n - 1); k++){ vector<int> v; v.push_back(j - i); v.push_back(k - j); v.push_back(k - i); vector<int> v2; v2.push_back(H[i]); v2.push_back(H[j]); v2.push_back(H[k]); sort(v2.begin(), v2.end()); sort(v.begin(), v.end()); if(v == v2){ ans++; } } } } return ans; } bool s4 = true; for(int i = 0; i < n - 1; i++){ if(H[i] > H[i + 1]){ s4 = false; break; } } if(s4){ long long ans = 0; for(int k = 0; k < n; k++){ int i = k - H[k]; if(0 <= i && i < k){ if(H[k] != k - i && H[i] != k - i){ if(H[k] + H[i] == k - i){ int j1 = i + H[i]; int j2 = i + H[k]; if(i < j1 && j1 < k){ ans += check(i, j1, k, H[i], H[j1], H[k]); } if(i < j2 && j2 < k && j1 != j2){ ans += check(i, j2, k, H[i], H[j2], H[k]); } } } else{ if(H[k] == k - i){ int j1 = i + H[i]; int j2 = k - H[i]; if(i < j1 && j1 < k){ ans += check(i, j1, k, H[i], H[j1], H[k]); } if(i < j2 && j2 < k && j1 != j2){ ans += check(i, j2, k, H[i], H[j2], H[k]); } } if(H[i] == k - i){ int j1 = i + H[k]; int j2 = k - H[k]; if(i < j1 && j1 < k){ ans += check(i, j1, k, H[i], H[j1], H[k]); } if(i < j2 && j2 < k && j1 != j2){ ans += check(i, j2, k, H[i], H[j2], H[k]); } } } } } return ans; } } std::vector<int> construct_range(int M, int K) { return {1, 1, 1}; }

Compilation message (stderr)

triples.cpp: In function 'long long int count_triples(std::vector<int>)':
triples.cpp:141:1: warning: control reaches end of non-void function [-Wreturn-type]
  141 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...