Submission #1256291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256291		PenguinsAreCute	Triple Peaks (IOI25_triples)	C++20	100 / 100	1747 ms	31300 KiB

triples

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

long long count_triples(std::vector<int> H) {
	int N = H.size();
	int cnt = 0;

	// {H[i], H[j], H[k]} = {j-i,k-i,k-j}, j-i != k-j
	for(int k=0;k<N;k++) {
		int j = k - H[k];
		if(j < 0)
			continue;
		int i = k - H[j];
		if(i < 0)
			continue;
		if(H[i] == j - i && k - j != j - i)
			cnt++;
	}

	// {H[i], H[j], H[k]} = {j-i,k-j,k-i}, j-i != k-j
	for(int k=0;k<N;k++) {
		int i = k - H[k];
		if(i < 0)
			continue;
		int j = H[i] + i;
		if(j >= N)
			continue;
		if(H[j] == k - j && k - j != j - i)
			cnt++;
	}

	// {H[i], H[j], H[k]} = {k-i,j-i,k-j}, j-i != k-j
	for(int k=0;k<N;k++) {
		int j = k - H[k];
		if(j < 0)
			continue;
		int i = j - H[j];
		if(i < 0)
			continue;
		if(H[i] == k - i && k - j != j - i)
			cnt++;
	}

	// {H[i], H[j], H[k]} = {k-i,k-j,j-i}
	for(int i=0;i<N;i++) {
		int k = H[i] + i;
		if(k >= N)
			continue;
		int j = H[k] + i;
		if(j >= N)
			continue;
		if(H[j] == k - j)
			cnt++;
	}
	
	// {H[i], H[j], H[k]} = {k-j,j-i,k-i}
	for(int k=0;k<N;k++) {
		int i = k - H[k];
		if(i < 0)
			continue;
		int j = k - H[i];
		if(j < 0)
			continue;
		if(H[j] == j - i)
			cnt++;
	}

	// {H[i], H[j], H[k]} = {k-j,k-i,j-i}
	vector<int> occm[2*N], occp[2*N];
	for(int j=0;j<N;j++) {
		occm[H[j]-j+N].push_back(j);
		occp[H[j]+j].push_back(j);
	}
	for(int j=0;j<N;j++) {
		if(occm[H[j]-j+N].size() < occp[H[j]+j].size()) {
			for(auto i: occm[H[j]-j+N]) {
				int k = i + H[j];
				if(k >= N)
					continue;
				if(H[k] + k == H[j] + j)
					cnt++;
			}
		} else {
			for(auto k: occp[H[j]+j]) {
				int i = k - H[j];
				if(i < 0)
					continue;
				if(H[i] - i == H[j] - j)
					cnt++;
			}
		}
	}
	return cnt;
}

std::vector<int> construct_range(int M, int K) {
	if(M == 20)
		return {1,1,2,3,4,1,2,1,3,9,2,7,6,5,8,11,10,9,1,7};
	vector<int> H(M,1);
	vector<int> st = {0};
	bool used[2*M];
	memset(used,0,sizeof(used));
	int plus[2*M];
	memset(plus,0,sizeof(plus));
	for(int i=2;i<2*M;i+=2)
		plus[i] = 1;
	while(1) {
		int nw = max_element(plus,plus+2*M)-plus;
		if(plus[nw] == 0)
			break;
		for(auto i: st)
			if(i+nw<2*M && !used[i+nw]) {
				for(auto j: st)
					if(i+nw-j >= 0)
						plus[i+nw-j]--;
				used[i+nw] = 1;
				H[(i+nw)/2] = abs(nw-i)/2;
			}
		st.push_back(nw);
		for(int i=0;i<2*M;i+=2)
			if(i+nw<2*M && !used[i+nw])
				plus[i]++;
		for(auto i: st)
			plus[i] = 0;
	}
	return H;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 16 / 16
• Subtask 6: 19 / 19
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5