34215번 - Triple Peaks 서브태스크점수다국어언어 제한함수 구현

문제

The Cordillera Oriental is a mountain range in the Andes that stretches across Bolivia. It consists of a sequence of $N$ mountain peaks, numbered from 0ドル$ to $N - 1$. The height of peak $i$ (0ドル \leq i < N$) is $H[i],ドル which is an integer between 1ドル$ and $N - 1,ドル inclusive.

For any two peaks $i$ and $j$ where 0ドル \leq i < j < N,ドル the distance between them is defined as $d(i, j) = j - i$.

According to ancient Inca legends, a triple of peaks is mythical if it has the following special property: the heights of the three peaks match their pairwise distances ignoring the order.

Formally, a triple of indices $(i, j, k)$ is mythical if

• 0ドル \leq i < j < k < N,ドル and
• the heights $(H[i], H[j], H[k])$ match the pairwise distances $(d(i,j), d(i,k), d(j,k))$ ignoring the order. For example, for indices 0,ドル 1, 2$ the pairwise distances are $(1, 2, 1),ドル so the heights $(H[0],H[1],H[2]) = (1,1,2),ドル $(H[0],H[1],H[2]) = (1,2,1),ドル and $(H[0],H[1],H[2]) = (2,1,1)$ all match them, but the heights $(H[0], H[1], H[2])=(1,2,2)$ do not match them.

This problem consists of two parts, with each subtask associated with either Part I or Part II. You may solve the subtasks in any order. In particular, you are not required to complete all of Part I before attempting Part II.

Part I

Given a description of the mountain range, your task is to count the number of mythical triples.

구현 상세

You should implement the following procedure.

long long count_triples(std::vector<int> H)

• $H$: array of length $N,ドル representing the heights of the peaks.
• This procedure is called exactly once for each test case.

The procedure should return an integer $T,ドル the number of mythical triples in the mountain range.

제한

• 3ドル \leq N \leq 200,000円$
• 1ドル \leq H[i] \leq N - 1$ for each $i$ such that 0ドル \leq i < N$.

서브태스크

Part I is worth a total of 70ドル$ points.

예제

Consider the following call.

count_triples([4, 1, 4, 3, 2, 6, 1])

There are 3ドル$ mythical triples in the mountain range:

• For $(i,j,k)=(1,3,4),ドル the heights $(1,3,2)$ match the pairwise distances $(2,3,1)$.
• For $(i,j,k)=(2,3,6),ドル the heights $(4,3,1)$ match the pairwise distances $(1,4,3)$.
• For $(i,j,k)=(3,4,6),ドル the heights $(3,2,1)$ match the pairwise distances $(1,3,2)$.

Hence, the procedure should return 3ドル$.

Note that the indices $(0, 2, 4)$ do not form a mythical triple, as the heights $(4,4,2)$ do not match the pairwise distances $(2,4,2)$.

입력

출력

제한

Part II

Your task is to construct mountain ranges with many mythical triples. This part consists of 6ドル$ output-only subtasks with partial scoring.

In each subtask, you are given two positive integers $M$ and $K,ドル and you should construct a mountain range with at most$M$ peaks. If your solution contains at least $K$ mythical triples, you will receive the full score for this subtask. Otherwise, your score will be proportional to the number of mythical triples your solution contains.

Note that your solution must consist of a valid mountain range. Specifically, suppose your solution has $N$ peaks ($N$ must satisfy 3ドル \leq N \leq M$). Then, the height of peak $i$ (0ドル \leq i < N$), denoted by $H[i],ドル must be an integer between 1ドル$ and $N - 1,ドル inclusive.

구현 상세

There is one method to submit your solution, and you may use it for each subtask:

• Procedure call

To submit your solution via a procedure call, you should implement the following procedure.

std::vector<int> construct_range(int M, int K)

• $M$: the maximum number of peaks.
• $K$: the desired number of mythical triples.
• This procedure is called exactly once for each subtask.

The procedure should return an array $H$ of length $N,ドル representing the heights of the peaks.

서브태스크

Part II is worth a total of 30ドル$ points. For each subtask, the values of $M$ and $K$ are fixed and given in the following table:

For each subtask, if your solution does not form a valid mountain range, your score will be 0ドル$ (reported as Output isn't correct in CMS).

Otherwise, let $T$ denote the number of mythical triples in your solution. Then, your score for the subtask is: $5ドル \cdot \min\left(1,\frac{T}{K}\right).$$

서브태스크

힌트

샘플 그레이더

Parts I and II use the same sample grader program, with the distinction between the two parts determined by the first line of the input.

Input format for Part I:

1
N
H[0] H[1] ... H[N-1]

Output format for Part I:

T

Input format for Part II:

2
M K

Output format for Part II:

N
H[0] H[1] ... H[N-1]

Note that the output of the sample grader matches the required format for the output file in Part II.

첨부

• triples.zip