Submission #1311914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311914		Cyanberry	Triple Peaks (IOI25_triples)	C++20	18 / 100	1295 ms	2368 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int N;

bool checkTriple(int a, int b, int c, vector<signed>& H) {
	if (a >= N) return false;
	if (b >= N) return false;
	if (c >= N) return false;
	vector<int> d {abs(b-a), abs(c-a), abs(c-b)};
	vector<int> h = {H[a], H[b], H[c]};
	sort(d.begin(), d.end());
	sort(h.begin(), h.end());
	for (int i = 0; i < 3; ++i) {
		if (d[i] != h[i]) return false;
	}
	return true;
}

long long count_triples(std::vector<signed> H) {
	ll ret = 0;
	N = H.size();
	set<int> nums;
	for (int i = 0; i < N; ++i) {
		int curr = H[i];
		int left = i - curr, right = i + curr;
		if (N > 2000) {
			for (int j = i - 20; j < i + 20; ++j) {
				if (j < 0) continue;
				if (j >= N) break;
				nums.clear();
				nums.insert(i + H[i]);
				nums.insert(i + H[j]);
				nums.insert(j + H[i]);
				nums.insert(j + H[j]);
				for (auto k = nums.begin(); k != nums.end(); ++k) {
					if (*k < j) continue;
					if (checkTriple(i, *k, j, H)) {
						++ret; 
						// cout<<i<<' '<<*k<<' '<<j<<'\n';
					}
				};
			}
		} else {
			for (int j = i; j < N; ++j) {
				nums.clear();
				nums.insert(i + H[i]);
				nums.insert(i + H[j]);
				nums.insert(j + H[i]);
				nums.insert(j + H[j]);
				for (auto k = nums.begin(); k != nums.end(); ++k) {
					if (*k < j) continue;
					if (checkTriple(i, *k, j, H)) {
						++ret; 
						// cout<<i<<' '<<*k<<' '<<j<<'\n';
					}
				}
			}
		}
	}
	return ret;
}

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

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