Table of Contents

ExplanationImplementation

Official Editorial (C++)

Explanation

Use binary search to determine the maximum number of times the subarray tt can be cut out from the original array. Once it is calculated, construct the resulting array by including elements in proportion to their contributions.

Implementation

Time Complexity: O(MAX_Nlog⁡(N))\mathcal{O} (MAX\_N \log(N))

C++

#include <iostream>
#include <vector>


const int MAX_N = 200000;


int main() {
	int n, k;
	std::cin >> n >> k;
	std::vector<int> freq(MAX_N + 1);
	for (int i = 0; i < n; i++) {

Java

import java.io.*;
import java.util.*;


public class CuttingOut {
	private final static int MAX_N = 200000;
	public static void main(String[] args) {
		Kattio io = new Kattio();


		int n = io.nextInt();
		int k = io.nextInt();

Python

MAX_N = 200000


freq = [0] * (MAX_N + 1)
n, k = map(int, input().split())
for x in input().split():
	freq[int(x)] += 1




def can(x: int) -> bool:
	ele_num = 0

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum