Submission #1249991

#TimeUsernameProblemLanguageResultExecution timeMemory
1249991Jakub_WozniakTriple Peaks (IOI25_triples)C++20
43.97 / 100
2092 ms2632 KiB
#include "triples.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<vector <int> ,ll> pvl; #define st first #define nd second int ile = 0; vector<int> construct_range(int M, int K) { if(M == 0)return {}; if(M == 1)return {1}; if(M == 2)return {1,1}; if(M == 3)return {1,2,1}; if(M == 4)return {1,2,2,1}; if(M == 5)return {1,1,2,1,1}; if(M == 6)return {1,2,1,1,2,1}; if(M == 7)return {1,2,1,2,1,2,1}; if(M == 8)return {1,1,2,1,1,2,1,1}; int S = 5; if(S%2 == 0)S--; int R = M -((S-1) + S*((M-S+1)/S)); M = ((S-1) + S*((M-S+1)/S)); vector <int> temp = construct_range((M-S+1)/S,K); vector <int> r; for(int i = 0 ; i < S ; i++) { if(i%2 == 0)for(auto p : temp)r.push_back(p); else for(auto p : temp)r.push_back((M-S+1)/S+1-p); if(i != S-1)r.push_back((M-S+1)/S+1); } temp = construct_range(R , K); for(auto p : temp)r.push_back(p); return r; } long long count_triplesnd(vector<int> H) { int N = H.size(); ll ile = 0; for(int i = N-1 ; i >= 0 ; i--) { int k = i-H[i]; if(k < 0)continue; int j = k+H[k]; if(j < 0 || j >= N); else if(H[k]+H[j] == H[i] && (i-j) == H[j] && k < j && j < i)ile++; j = i-H[k]; if(k+H[k] == j)continue; if(j < 0 || j >= N); else if(H[k]+H[j] == H[i] && (j-k) == H[j] && k < j && j < i)ile++; } return ile; } long long count_triples(vector<int> H) { int N = H.size(); int B = 0; bool czynd = 1; for(int i = 0; i < N ; i++)B = max(B , H[i]); for(int i = 1; i < N ; i++) { if(H[i-1] > H[i])czynd = 0; } if(czynd)return count_triplesnd(H); ll ile = 0; for(int i = 0 ; i < N ; i++) { for(int j = i+1 ; j < min(N,i+B+1) ; j++) { int d = j-i; if(H[i] == d || H[j] == d) { int R = 0; if(H[i] == d)R = H[j]; else R = H[i]; int k = j+R; if(k >= 0 && k < N && k > j && H[k] == R+d)ile++; k = i+R; if(k >= 0 && k < N && k > j && R == H[k]+d)ile++; } else { int k = j+min(H[i] , H[j]); if(k >= 0 && k < N && H[k] == d && min(H[i],H[j])+d == max(H[i],H[j]))ile++; } } } return ile; }
#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...