Submission #1327932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1327932		adiyer	Triple Peaks (IOI25_triples)	C++20	11 / 100	14 ms	3488 KiB

triples

#include <bits/stdc++.h>
#include "triples.h"

using namespace std;

typedef long long ll;

const int N = 200005;

ll ans;

int n;
int a[N], c[N];

void print(ll x, char sep = ' '){
    cout << x << sep;
}

bool check(int i, int j, int k){
    c[k - j]++, c[j - i]++, c[k - i]++, c[a[i]]--, c[a[j]]--, c[a[k]]--;
    if(!c[k - j] && !c[j - i] && !c[k - i]) return 1;
    c[k - j] = c[j - i] = c[k - i] = c[a[i]] = c[a[j]] = c[a[k]] = 0;
    return 0;
}

ll count_triples(vector < int > h){
    n = h.size(), ans = 0;
    for(int i = 0; i < n; i++) a[i] = h[i];
    for(int j = 0, i, k; j < n; j++){
        i = j - a[j], k = -1;
        if(i >= 0){
            k = j + a[i];
            if(j < k && k < n) ans += check(i, j, k);
        }
        if(j + a[j] == k) continue;
        k = j + a[j];
        if(k < n){
            i = k - a[k];
            if(0 <= i && i < j) ans += check(i, j, k);
        }
    }
    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: 11 / 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