Submission #1327943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1327943		adiyer	Triple Peaks (IOI25_triples)	C++20	25.21 / 100	2095 ms	3532 KiB

triples

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

using namespace std;

typedef long long ll;

const int N = 200000;

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 i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(a[i] == j - i || a[j] == j - i){
                ll d = (a[i] == j - i ? a[j] : a[i]);
                ans += check(i, j, j + d);
                if(i + d > j) ans += check(i, j, i + d);
            }
            else if(i + max(a[i], a[j]) == j + min(a[i], a[j])){
                ll k = i + max(a[i], a[j]);
                ans += check(i, j, k);
            }
        }
    }
    return ans;
}

vector < int > construct_range(int n, int k){    
    vector < int > v;
    n /= 5;
    while(n--) v.push_back(1), v.push_back(1), v.push_back(2), v.push_back(2), v.push_back(3);
    return v;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 6
• Subtask 3: 10 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 4 / 5
• Subtask 8: 1.74 / 5
• Subtask 9: 0.6996 / 5
• Subtask 10: 0.3 / 5
• Subtask 11: 0.35 / 5
• Subtask 12: 0.1167 / 5