Submission #1264320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264320		anango	Triple Peaks (IOI25_triples)	C++20	2.65 / 100	14 ms	1860 KiB

triples

#include "triples.h"
#define ll long long
using namespace std;

long long count_triples(std::vector<int> 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
    return 0ll;
}

std::vector<int> construct_range(int M, int K) {
    
    
    vector<int> pattern = {2,1};
    int pl = pattern.size();
    vector<int> result={1};
    for (int i=0; i<M-1; i++) {
        result.push_back(pattern[i%pl]);
    }
    return result;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 1.5 / 5
• Subtask 8: 0.6225 / 5
• Subtask 9: 0.2499 / 5
• Subtask 10: 0.1071 / 5
• Subtask 11: 0.125 / 5
• Subtask 12: 0.0417 / 5