Submission #1264339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264339		anango	Triple Peaks (IOI25_triples)	C++20	24.15 / 100	915 ms	85620 KiB

triples

#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<int32_t> construct_range(int32_t M, int32_t K) {
    
    
    vector<int> pattern = {3,1,1,2,1,4,3,2,3,1};
    int pl = pattern.size();
    vector<int32_t> result;
    for (int i=0; i<M; i++) {
        result.push_back(pattern[i%pl]);
    }
    return result;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 6 / 6
• Subtask 3: 0 / 10
• Subtask 4: 11 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 4.1667 / 5
• Subtask 8: 1.6225 / 5
• Subtask 9: 0.6499 / 5
• Subtask 10: 0.2786 / 5
• Subtask 11: 0.325 / 5
• Subtask 12: 0.1083 / 5