Submission #1250927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250927		KN200711	Triple Peaks (IOI25_triples)	C++20	57.53 / 100	2106 ms	413636 KiB

triples

#include "triples.h"
# include <bits/stdc++.h>
# pragma GCC optimize("unroll-loops")
# pragma GCC optimize("Ofast")
# define ll long long
# define fi first
# define se second
# define pii pair<int, int>
using namespace std;

vector<int> num[600001];
vector< pair<int, pii> > ct;
int ss[200001];

pair<int, pii> sr(int a, int b, int c) {
    if(a > b) swap(a, b);
    if(b > c) swap(b, c);
    if(a > b) swap(a, b);
    return {a, {b, c}};
}

int fn() {
    sort(ct.begin(), ct.end());
    int cnt = 0;
    for(int i=0;i<ct.size();i++) {
        if(i == 0 || ct[i] != ct[i - 1]) cnt++;
    }
    return cnt;
}

int arr[200001];
int N;

bool cek(int a, int b, int c) {
    if(a == b || a == c || b == c) return 0;
    if(a < 1 || b < 1 || c < 1) return 0;
    if(a > N || b > N || c > N) return 0;
    // cout<<"cek ? "<<a<<" "<<b<<" "<<c<<endl;
    if(sr(abs(a - b), abs(a - c), abs(b - c)) == sr(arr[a], arr[b], arr[c])) return 1;
    return 0;
}

ll count_triples(vector<int> H) {
    ct.clear();
    N = H.size();

    for(int i=0;i<N;i++) {
        arr[i + 1] = H[i];
    }

    for(int i=1;i<=N;i++) {
        // cout<<"cc : "<<i<<" "<<i + arr[i]<<endl;
        if(i > arr[i]) {
            int x = i - arr[i];
            if(x > arr[x]) {
                int y = x - arr[x];
                if(cek(i, x, y)) ct.push_back(sr(i, x, y));
            }
            if(x + arr[x] <= N) {
                if(cek(i, x, x + arr[x])) ct.push_back(sr(i, x, x + arr[x]));
            }
            if(i - arr[x] > 0) {
                if(cek(i, x, i - arr[x])) ct.push_back(sr(i, x, i - arr[x]));
            }
            if(i + arr[x] <= N) {
                if(cek(i, x, i + arr[x])) ct.push_back(sr(i, x, i + arr[x]));
            }
        }
        if(i + arr[i] <= N) {
            int x = i + arr[i];
            if(x > arr[x]) {
                int y = x - arr[x];
                if(cek(i, x, y)) ct.push_back(sr(i, x, y));
            }
            if(x + arr[x] <= N) {
                if(cek(i, x, x + arr[x])) ct.push_back(sr(i, x, x + arr[x]));
            }
            if(i - arr[x] > 0) {
                if(cek(i, x, i - arr[x])) ct.push_back(sr(i, x, i - arr[x]));
            }
            if(i + arr[x] <= N) {
                if(cek(i, x, i + arr[x])) ct.push_back(sr(i, x, i + arr[x]));
            }
        }
    }

    // cout<<"fn : "<<fn()<<endl;

    int sq = ceil(sqrt(N));

    for(int i=0;i<=3*N;i++) num[i].clear();

    for(int i=N;i>=1;i--) {
        for(auto x : num[i + arr[i] + N]) {
            if(cek(i, x, i + arr[x])) ct.push_back(sr(i, x, i + arr[x]));
        }
        if(num[i - arr[i] + N].size() < sq) num[i - arr[i] + N].push_back(i);
        else ss[i]++;    
    }


    for(int i=0;i<=3*N;i++) num[i].clear();

    for(int i=N;i>=1;i--) {
        for(auto x : num[i + arr[i] + N]) {
            if(cek(i, x, x - arr[i])) ct.push_back(sr(i, x, x - arr[i]));
        }
        if(num[i + arr[i] + N].size() < sq) num[i + arr[i] + N].push_back(i);
        else ss[i]++;
    }

    int calc = 0;
    for(int i=1;i<=N;i++) calc++;


    for(int i=1;i<=N;i++) {
        if(ss[i] == 2) {
            for(int c = max(1, i - arr[i]);c <= i + arr[i] && c <= N;c++) {
                if(cek(c, i, c + arr[i])) ct.push_back(sr(c, i, arr[i]));
            }
        }
    }

    return fn();
}
std::vector<int> construct_range(int M, int K) {
    vector<int> arr = {3, 1, 2, 1, 4, 3, 2, 7};
    vector<int> ans(M);
    for(int i=0;i<M;i++) {
        ans[i] = arr[i % 8];
    }
    return ans;
}

• 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: 0 / 19
• Subtask 7: 3.6667 / 5
• Subtask 8: 1.555 / 5
• Subtask 9: 0.6249 / 5
• Subtask 10: 0.2678 / 5
• Subtask 11: 0.3125 / 5
• Subtask 12: 0.1042 / 5