Submission #1311939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311939		Cyanberry	Triple Peaks (IOI25_triples)	C++20	34.29 / 100	323 ms	39608 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;
	if (a < 0) return false;
	if (b < 0) return false;
	if (c < 0) return false;
	if (a == b) return false;
	if (a == c) return false;
	if (b == c) 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) {
			nums.clear();
			int j = i - H[i];
			if (j < 0) continue;
			nums.insert(j + H[j]);
			nums.insert(i - 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) {
	vector<int> ret;
	for (int i = 0; i < M; ++i) {
		ret.push_back((i%3 == 2) + 1);
	}
	return ret;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 3 / 5
• Subtask 8: 1.245 / 5
• Subtask 9: 0.4998 / 5
• Subtask 10: 0.2143 / 5
• Subtask 11: 0.25 / 5
• Subtask 12: 0.0833 / 5