Submission #1251262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251262		fafnir	Triple Peaks (IOI25_triples)	C++20	70 / 100	115 ms	16200 KiB

triples

#include <bits/stdc++.h>
using namespace std;

// #define LOCAL

// Part I
/*
    hi,hj,hk

    WLOG i < j < k

    Case work on which hi/hj/hk has largest value k-i

    Case 1: h[i] = k-i 
        *) Fixing i, fixes k
           -> k = i+h[i]
        *) Then
            hk = k-j or hk = j-i
            -> In both cases: j is fixed, 2*N possible triples


    Case 2: h[k] = k-i
        *) Fixing k, fixes i
            -> i = k-h[k]
        *) Now,
            h[i] = j-i or h[i] = k-j
            -> In both cases: j fixed, 2*N possible triples

    Case 3: h[j] = k-i
        *) If h[i] = j-i
          -> Fixing i, fixes j (h[i]+i = j)
          -> Then k = h[j]+i = k

        *) h[i] = k-j
           h[j] = k-i
           h[k] = j-i

           --> h[j]-h[i] = k-i-(k-j) = j-i
           --> h[j]-j = h[i]-i = c

           --> h[k] - h[j] = j - k
               h[k] + k = h[j] + j


        2D points/lines
        h[i] - i = 0
        [-N, N] -> [0,2*N]

        (i,h[i])
        (j,h[j])
        (k,h[k])

        Equations:
            i)      h[j] + j = h[k] + k
            ii)     h[j]-j   = h[i] - i


        
        For equation ii) --> O(n^2) solution
            -> If diagonal has size <= sqrt(n), then O(n) possible
            ->
                h[k]+k = h[j]+j = diag+j+j




*/

constexpr long long MUL = 200'001;
constexpr long long MULSQ = MUL * MUL;

long long chash(int i, int j, int k) {
    array<int,3> a{i,j,k};
    sort(a.begin(), a.end());
    long long h = a[0];
    h += MUL * a[1];
    h += MULSQ * a[2];
    return h;
}

bool check(int i, int j, int k, vector<int>& h) {
    if (min(i,min(j,k)) < 0 || max(i,max(j,k)) >= h.size()) {
        return false;
    }
    array<int,3> a{abs(j-i), abs(k-i), abs(k-j)};
    array<int,3> b{h[i],h[j],h[k]};
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    return a==b;
}

int count_triples(vector <int32_t> a){
    int n = a.size();
    int ans = 0;
    for (int i = 0; i < n; i++){
        if (i + a[i] < n){
            int j = i + a[i];
            if (a[j] < a[i]){
                int k = j - a[j];
                if (a[k] + a[j] == a[i]){
                    ans++;
                }
                
                if (2 * a[j] != a[i]){
                    k = i + a[j];
                    if (a[k] + a[j] == a[i]){
                        ans++;
                    }
                }
            }
        }
        
        if (i - a[i] >= 0){
            int j = i - a[i];
            if (a[j] < a[i]){
                int k = j + a[j];
                if (a[k] + a[j] == a[i]){
                    ans++;
                }
                
                if (2 * a[j] != a[i]){
                    k = i - a[j];
                    if (a[k] + a[j] == a[i]){
                        ans++;
                    }
                }
            }
        }
    }
    
    vector <int> b[2 * n + 1];
    for (int i = 0; i < n; i++){
        b[a[i] - i + n].push_back(i);
    }
    
    int cutoff = sqrt(n);
    
    for (int x = 1; x <= 2 * n; x++){
        if (b[x].size() <= cutoff){
            for (int v1 = 0; v1 < b[x].size(); v1++){
                int i = b[x][v1];
                for (int v2 = 0; v2 < v1; v2++){
                    int j = b[x][v2];
                    int k = j + a[i];
                    if (k < n && k > i){
                        if (a[i] == (k - j) && a[j] == (k - i) && a[k] == (i - j)){
                            ans++;
                        }
                    }
                }
            }
        } else {
            for (int k = 0; k < n; k++){
                int C = x - n;
                int sum = k - C;
                int diff = a[k];
                
                if (diff % 2 == sum % 2){
                    int i = (sum - diff) / 2;
                    int j = (sum + diff) / 2;
                    
                    if (0 <= i && i < n && 0 <= j && j < n && a[i] - i == C && a[j] - j == C){
                        ans++;
                    }
                }
            }
        }
    }
    
    for (int i = 0; i < n; i++){
        int j = i + a[i];
        if (j < n && a[j] > a[i]){
            int k = i + a[j];
            if (k < n){
                if (a[k] + a[i] == a[j] && a[k] != a[i]){
                    ans++;
                }
            }
        }
    }
    
    return ans;
}


std::vector<int> construct_range(int M, int K) {
    M = 0;
    K = 0;
    return {M,K};
}



#ifdef LOCAL
int32_t main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tc;
    cin >> tc;

    while (tc--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (auto& e : a) cin >> e;

        cout << count_triples(a) << '\n';
    }


    return 0;
}
#endif

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 16 / 16
• Subtask 6: 19 / 19
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5