Submission #1250869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250869		lukameladze	Triple Peaks (IOI25_triples)	C++20	0 / 100	79 ms	16456 KiB

triples

#include "triples.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <iostream>
#define pb push_back
using namespace std;
int check(int i, int j, int k, vector<int>& h) {
    vector <int> x, x2;
    x.pb(h[i]);
    x.pb(h[j]);
    x.pb(h[k]);
    sort(x.begin(), x.end());
    x2.pb(abs(i - j));
    x2.pb(abs(j - k));
    x2.pb(abs(k - i));
    sort(x2.begin(), x2.end());
    if (x[0] == x2[0] && x[1] == x2[1] && x[2] == x2[2]) {
        return 1;
    }
    return 0;
}
long long count_triples(std::vector<int> H) {
    int n = H.size();
    long long ans = 0;
    vector <int> h(n);
    for (int i = 0; i < n; i++) {
        h[i] = H[i];
        // cout<<h[i]<<" ";
    }
    // cout<<"\n";
    for (int i = 0; i < n; i++) {
        int k = h[i] + i;
        if (k <= i + 1) continue;
        int j = h[k] + i;
        if (j > i && j < k) {
            ans += check(i, j, k, h);
        }
        int j2 = h[k] - k;
        if (j2 > i && j2 < k && j2 != j) {
            ans += check(i, j2, k, h);
        }
    }

    for (int k = 0; k < n; k++) {
        int i = k - h[k];
        if (i < 0) continue;
        int j = h[i] + i;
        if (j > i && j < k) {
            ans += check(i, j, k, h);
        }
        int j2 = k - h[i];
        if (j2 > i && j2 < k && j2 != j) {
            ans += check(i, j2, k, h);
        }
    }

    for (int i = 0; i < n; i++) {
        int j = h[i] + i;
        if (j <= i + 1) continue;
        int k = h[j] + i;
        if (k > j && k < n) {
            ans += check(i, j, k, h);
        }
    }
    vector <vector<int>> vec(2 * n + 1);
    for (int i = 0; i < n; i++) {
        vec[h[i] - i + n].pb(i);
    }
    int b = 300;
    for (int dif = 0; dif < 2 * n; dif++) {

        if (vec[dif].size() < b) {
            for (int i : vec[dif]) {
                for (int j : vec[dif]) {
                    if (j <= i) continue;
                    
                    int k = h[j] + i;
                    // if (dif == n) {
                    //     cout << i << " " << j << " " << k << " " << h[i] << " " << h[j] << "\n";
                    // }
                    if (k > j && k < n && h[j] == k - i) {
                        // if (dif == n) {
                        //     cout << i << " -- " << j << " " << k << " " << h[i] << " " << h[j] << "\n";
                        // }
                        ans += check(i, j, k, h);
                    }
                }
            }
        } else {
            int act = dif - n;
            // vector <int> fix(n, 0);
            // for (int idx : vec[dif]) {
            //     fix[idx] = 1;
            // }
            for (int k = 2; k < n; k++) {
                int i2 = k - h[k] - act;
                if (i2 < 0 || i2 % 2) continue;
                int i = i2 / 2;
                if (i < 0 || i >= n) continue;
                int j = h[k] + i;
                if (j > i && j < k && h[j] == k - i) {
                    ans += check(i, j, k, h);
                }
            }
        }
    }
    return ans;
}

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

• 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: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5