| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1264337 | anango | Triple Peaks (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include "triples.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define int long long
vector<int> heights;
void prv(vector<int> v) {
for (auto i:v) {
cout << i <<" ";
}
cout << endl;
}
int check(int a, int b, int c) {
if (a==b || b==c || c==a) return 0;
vector<int> s1 = {abs(a-b), abs(b-c), abs(c-a)};
vector<int> s2 = {heights[a], heights[b], heights[c]};
/*cout << a <<" " << b <<" " << c << endl;
prv(s1);
prv(s2);
cout <<" tested " << endl;*/
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
return s1==s2;
}
long long count_triples(std::vector<int32_t> H) {
//firstly, consider index 1 is part of a mythical triple (1 is a label not an index)
//there are two possibilities, either that index 1 and 2 are separated by the height of 1 (or index 1 and 3)
//or that indices 2 and 3 are separated by the height of 1
//if it's the former case, it's simple because we can just check index 2 positions +- H_1 of position of index 1
//and then check index 3 positions +- H_2 of position of index 1 and then +- H_2 of position of index 2
//so only 2 index 2 and 4 index 3 positions need to be considered
//in the case where indices 2 and 3 are separated by the height of 1
//then if indices 1 and 2 are separated by the height of 2 we're essentially back to the first case
//the only really hard case is if indices 1 and 2 are separated by the height of 3
//and indices 1 and 3 are separated by the height of 2
//etc
//ok note that one of the pairwise distances is the sum of the other two
//and thus one of the heights is the sum of the other two
//in fact the middle height is the sum of the 2 outer ones
//which means this case is impossible in subtask 4
//so we can easily get 35 points with this solution so far
//so we want two indices such that the distance from the first to index 1 on the left is equal to the height of the second
//and the distance from index 1 on the right to the second is the height of the first
//call these indices a,b and the middle index M
//b = a+H[M]
//so we definitely need:
//M-a = H[b]
//b-M = H[a]
//so summing, b-a = H[b]+H[a]
//maybe we first find pairs of indices such that b-a = H[b]+H[a] and then check that their midpoint works
//in fact this means that H[a]+a = b-H[b]
//so we can look at the values of H[a]+a over all a, look at the values of b-H[b] over all b, and then see for overlaps
//if st, where s is count of number of times p is a H[a]+a value and t is the count of number of times p is a H[b]+b value, is small
//then brute in O(n^2) all possible pairs
//if M is the middle
//H[M]-m = H[a]-a
//and H[M]+m = H[b]+b
//thus if we fix a, H[M]-m is forced
//and if we fix b, H[M]+m is forced
//just get subtasks 1-4
int n = H.size();
heights=vector<int>(H.begin(), H.end());
vector<vector<int>> results;
for (int i=0; i<n; i++) {
//type 1
for (auto j:{i-H[i], i+H[i]}) {
if (0<=j && j<n) {
for (auto k:{j-H[j], j+H[j], i-H[j], i+H[j]}) {
if (0<=k && k<n) {
//cout << i <<" " << j <<" " << k << endl;
if (check(i,j,k)) {
vector<int> res = {i,j,k};
sort(res.begin(), res.end());
results.push_back(res);
}
}
}
}
}
}
for (int i=0; i<n; i++) {
for (int j=max((int)0,i-20); j<min(n,i+20); j++) {
for (auto k:{j-H[i], j+H[i]}) {
if (0<=k && k<n) {
//cout << i <<" " << j <<" " << k << endl;
if (check(i,j,k)) {
vector<int> res = {i,j,k};
sort(res.begin(), res.end());
results.push_back(res);
}
}
}
}
}
sort(results.begin(), results.end());
results.erase(unique(results.begin(), results.end()),results.end());
int answer = results.size();
return answer;
}
std::vector<int> construct_range(int M, int K) {
vector<int> pattern = {3,1,1,2,1,4,3,2,3,1};
int pl = pattern.size();
vector<int> result;
for (int i=0; i<M; i++) {
result.push_back(pattern[i%pl]);
}
return result;
}