Submission #1254873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254873		PenguinsAreCute	Triple Peaks (IOI25_triples)	C++20	93.83 / 100	96 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};
	if(M == 500)
		return {1,1,2,3,4,1,2,1,3,3,6,5,4,7,10,9,8,11,2,3,4,1,2,1,6,3,2,5,4,7,2,9,8,11,6,13,4,37,6,35,2,33,2,39,4,29,2,27,26,25,50,23,48,21,46,31,52,17,42,15,40,39,38,63,36,61,34,59,44,65,30,55,28,53,2,51,39,57,56,55,58,57,60,55,62,53,82,13,80,49,86,47,76,45,74,73,72,97,70,95,26,93,28,99,30,89,32,87,86,85,88,83,90,13,92,91,94,17,96,19,98,47,100,83,102,81,2,79,2,85,4,83,6,89,60,91,2,89,4,95,66,93,68,43,70,45,72,47,74,49,76,17,78,15,80,13,30,57,32,59,34,61,24,63,30,65,28,67,2,145,36,143,34,141,40,151,38,137,44,135,42,13,44,15,50,17,48,19,2,21,4,23,2,25,2,27,6,29,4,31,6,33,8,199,10,197,12,107,14,193,4,191,2,189,8,187,10,185,4,195,6,181,4,179,2,201,88,199,6,197,4,207,2,193,2,191,50,189,164,199,166,73,168,75,170,77,172,79,174,81,176,151,230,229,60,227,182,225,56,235,54,221,52,163,138,217,48,259,134,169,132,255,42,253,40,251,150,249,204,247,146,257,144,243,142,117,152,119,150,121,148,191,154,125,108,127,106,129,104,131,226,133,100,135,98,137,120,139,94,141,116,303,90,213,88,299,110,297,84,295,106,293,116,291,102,157,100,287,98,285,96,299,194,289,104,295,102,293,144,291,142,341,140,339,270,337,136,179,134,333,132,331,130,329,128,339,126,257,44,335,166,333,164,331,162,265,160,327,158,325,56,339,154,329,152,335,62,333,304,347,146,337,56,343,310,341,386,339,384,383,382,291,318,389,378,387,376,297,84,383,326,381,6,379,278,305,4,375,274,385,272,371,10,313,12,383,278,377,212,379,106,377,208,349,286,257,4,259,354,261,296,263,6,417,248,415,336,413,244,271,254,341,40,419,250,417,236,415,234,323,244,411,230,319,28,317,238,457,236,455,234,453,248,459,62,449,244,447,242,445,302,443,238,441,252,307,50,437,248,293,246,291,44,289,298,287,296,285,294,283,292,281,290,279,420,277,286,275,184,273};
	int N;
	if(M == 5000)
		N = 6000;
	if(M == 30000)
		N = 44444;
	if(M == 100000)
		N = 150000;
	if(M == 200000)
		N = 400000;
	mt19937 rng(69);
	vector<int> v;
	for(int i=0;i<N;i++) {
		bool ok = 1;
		for(int j=i;j;j/=3)
			if((j%3)==1)
				ok=0;
		if(ok)
			v.push_back(i);
	}
	vector<int> ans(M);
	for(int i=0;i<M;i++)
		ans[i] = (i%3?1:2);
	shuffle(v.begin(),v.end(),rng);
	for(auto i: v)
		for(auto j: v)
			if(i+j<2*M && i!=j)
				ans[(i+j)/2] = abs(j-i)/2;
	return ans;
}

• 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: 4.555 / 5
• Subtask 9: 3.8961 / 5
• Subtask 10: 3.1024 / 5
• Subtask 11: 5 / 5
• Subtask 12: 2.2726 / 5