Submission #1249475

#TimeUsernameProblemLanguageResultExecution timeMemory
1249475bronze_coderTriple Peaks (IOI25_triples)C++20
59.93 / 100
2097 ms31300 KiB
#include "triples.h" #include <bits/stdc++.h> using namespace std; long long count_triples(vector<int> H){ int n = H.size(); long long count = 0; for(int i=0;i<n;i++){ int a = H[i]; int j = i+a; if(j<n){ int k; k = j+H[j]; if(i<k&&k<n&&k!=j&&k-i==H[k]){ count++; } k = i+H[j]; if(i<k&&k<n&&k!=j&&max(k-j,j-k)==H[k]&&k!=j+H[i]){ count++; } k = j-H[j]; if(i<k&&k<n&&k!=j&&k-i==H[k]&&k!=i+H[j]){ count++; } } j = i-a; if(j>=0){ int k = i+H[j]; if(k<n&&i-j!=H[j]&&k>j&&k-j==H[k]){ count++; } } } vector<vector<int>> heights1(2*n); vector<vector<int>> heights2(2*n); for(int i=0;i<n;i++){ heights1[i+H[i]].push_back(i); heights2[i-H[i]+n].push_back(i); } int m1 = 0; int m2 = 0; for(int i=0;i<2*n;i++){ int s1 = heights1[i].size(); int s2 = heights2[i].size(); m1 = max(m1,s1); m2 = max(m2,s2); } if(m1<m2){ for(int a=0;a<2*n;a++){ for(int i1=0;i1<heights1[a].size();i1++){ for(int j1=i1+1;j1<heights1[a].size();j1++){ int j = heights1[a][i1]; int k = heights1[a][j1]; int i = k-H[j]; if(i>=0&&H[i]==k-j){ count++; } } } } } else{ for(int a=0;a<2*n;a++){ for(int i1=0;i1<heights2[a].size();i1++){ for(int j1=i1+1;j1<heights2[a].size();j1++){ int i = heights2[a][i1]; int j = heights2[a][j1]; int k = H[i]+j; if(k<n&&H[k]==j-i){ count++; } } } } } return count; } vector<int> construct_range(int m, int k){ if(m==20){ return {2,1,1,3,2,3,4,1,2,1,3,1,2,1,4,3,2,3,1,1}; } else{ vector<int> q = {2,1,1,3,2,3,4,1,2,1,3,1,2,1,4,3,2,3,1,1,2,1,4,3,2,3,1,1,2,7,5,5,4,3,1,2,1,4,3,2,3,1,1,2,3,4,1,2,1,3,3,2,5,4,1,2,1,3}; vector<int> x = {4,5,4,1,2,1,3}; for(int i=0;i<m;i++){ if(q.size()<m){ q.push_back(x[i%7]); } } return q; } }
#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...