Submission #8044692


Source Code Expand

Copy
#include <bits/stdc++.h>

int main()
{
	int N;
	scanf("%d", &N);
	std::map<int, int> cards;
	for (int i{}; i < N; i++)
	{
		int A;
		scanf("%d", &A);
		cards[A]++;
	}
	int size{(int)cards.size()};
	std::vector<int64_t> table(size + 1);
	{
		int index{};
		for (auto iter{cards.begin()}; iter != cards.end(); iter++, index++)
			table[index] = iter->second;
	}
	table.back() = 1ll << 60;
	std::sort(table.rbegin(), table.rend());
	std::vector<int64_t> sum(table);
	sum.front() = 0;
	for (int i{1}; i <= size; i++)
		sum[i] += sum[i - 1];
	
	// for (auto& e: table) std::cout << e << ' ';
	// std::cout << std::endl;
	// for (auto& e: sum) std::cout << e << ' ';
	// std::cout << std::endl;

	for (int K{1}; K <= N; K++)
	{
		if (K > size)
		{
			puts("0");
			continue;
		}
		int64_t rest{sum[size] - sum[K]};
		int ok{}, ng{K};
		while (ng - ok > 1)
		{
			int mid{(ok + ng) >> 1};
			if ((sum[K] - sum[mid] + rest) / (K - mid) <= table[mid])
				ok = mid;
			else
				ng = mid;
		}
		printf("%lld\n", (sum[size] - sum[ok]) / (K - ok));
	}

	return 0;
}

Submission Info

Submission Time
Task F - Distinct Numbers
User TanakaTaroh
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1106 Byte
Status AC
Exec Time 367 ms
Memory 18944 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:50:52: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long int> >::value_type {aka long int}’ [-Wformat=]
   printf("%lld\n", (sum[size] - sum[ok]) / (K - ok));
                                                    ^
./Main.cpp:6:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:11:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A);
                  ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 40
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-small-01.txt, 01-small-02.txt, 01-small-03.txt, 01-small-04.txt, 01-small-05.txt, 01-small-06.txt, 01-small-07.txt, 01-small-08.txt, 01-small-09.txt, 01-small-10.txt, 02-medium-01.txt, 02-medium-02.txt, 02-medium-03.txt, 02-medium-04.txt, 02-medium-05.txt, 02-medium-06.txt, 02-medium-07.txt, 02-medium-08.txt, 02-medium-09.txt, 02-medium-10.txt, 11-large-01.txt, 11-large-02.txt, 11-large-03.txt, 21-biased-01.txt, 21-biased-02.txt, 21-biased-03.txt, 31-uni-01.txt, 31-uni-02.txt, 31-uni-03.txt, 41-distinct-01.txt, 41-distinct-02.txt, 41-distinct-03.txt, 51-min-01.txt, 52-max-01.txt, 52-max-02.txt, 52-max-03.txt, 61-sqrt-01.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 1 ms 256 KB
00-sample-02.txt AC 1 ms 256 KB
00-sample-03.txt AC 1 ms 256 KB
01-small-01.txt AC 1 ms 256 KB
01-small-02.txt AC 1 ms 256 KB
01-small-03.txt AC 1 ms 256 KB
01-small-04.txt AC 1 ms 256 KB
01-small-05.txt AC 1 ms 256 KB
01-small-06.txt AC 1 ms 256 KB
01-small-07.txt AC 1 ms 256 KB
01-small-08.txt AC 1 ms 256 KB
01-small-09.txt AC 1 ms 256 KB
01-small-10.txt AC 1 ms 256 KB
02-medium-01.txt AC 1 ms 256 KB
02-medium-02.txt AC 1 ms 256 KB
02-medium-03.txt AC 1 ms 256 KB
02-medium-04.txt AC 1 ms 256 KB
02-medium-05.txt AC 1 ms 256 KB
02-medium-06.txt AC 1 ms 256 KB
02-medium-07.txt AC 1 ms 256 KB
02-medium-08.txt AC 1 ms 256 KB
02-medium-09.txt AC 1 ms 256 KB
02-medium-10.txt AC 1 ms 256 KB
11-large-01.txt AC 139 ms 7936 KB
11-large-02.txt AC 150 ms 8320 KB
11-large-03.txt AC 206 ms 9984 KB
21-biased-01.txt AC 155 ms 7680 KB
21-biased-02.txt AC 153 ms 8192 KB
21-biased-03.txt AC 95 ms 5248 KB
31-uni-01.txt AC 30 ms 768 KB
31-uni-02.txt AC 31 ms 768 KB
31-uni-03.txt AC 36 ms 768 KB
41-distinct-01.txt AC 239 ms 13824 KB
41-distinct-02.txt AC 288 ms 15616 KB
41-distinct-03.txt AC 367 ms 18944 KB
51-min-01.txt AC 1 ms 256 KB
52-max-01.txt AC 249 ms 12672 KB
52-max-02.txt AC 280 ms 12672 KB
52-max-03.txt AC 267 ms 12672 KB
61-sqrt-01.txt AC 48 ms 896 KB