Submission #1311941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311941		Cyanberry	3개의 봉우리 (IOI25_triples)	C++20	20.98 / 100	2095 ms	27856 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 > 50000) {
			nums.clear();
			int j = i - H[i];
			if (j >= 0) {
				if (H[j] < H[i]) {
					if (checkTriple(i, j+H[j], j, H)) {
						++ret; 
						cout<<i<<' '<<j+H[j]<<' '<<j<<'\n';
					}
					if (checkTriple(i, i-H[j], j, H)) {
						++ret; 
						cout<<i<<' '<<i-H[j]<<' '<<j<<'\n';
					}
				} else {
					if (checkTriple(i, i-H[j], j, H)) {
						++ret; 
						cout<<i<<' '<<i-H[j]<<' '<<j<<'\n';
					}
				}
			} 
			j = i + H[i];
			if (j < H.size()) {
				if (H[j] < H[i]) {
					if (checkTriple(i, j-H[j], j, H)) {
						++ret; 
						cout<<i<<' '<<j-H[j]<<' '<<j<<'\n';
					}
					if (checkTriple(i, i+H[j], j, H)) {
						++ret; 
						cout<<i<<' '<<i+H[j]<<' '<<j<<'\n';
					}
				} else {
					if (checkTriple(i, i+H[j], j, H)) {
						++ret; 
						cout<<i<<' '<<i+H[j]<<' '<<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;
	int med = M/2-1;
	for (int i = 0; i < M; ++i) {
		if (i < med) {
			ret.push_back(2*(med - i) + 1);
		} else if (i > med + 1) {
			ret.push_back(i - med);
		} else {
			ret.push_back(1);
		}
	}
	return ret;
}

• 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: 1.8333 / 5
• Subtask 8: 0.6275 / 5
• Subtask 9: 0.2501 / 5
• Subtask 10: 0.1072 / 5
• Subtask 11: 0.125 / 5
• Subtask 12: 0.0417 / 5