Submission #8053884


Source Code Expand

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

const int N = 3e5 + 10;

int n;
int times[N], cnt[N], times2[N];

int get(int x) {
  return times[x] + (times2[x - 1]) / x;
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    int x;
    scanf("%d", &x);
    ++cnt[x];
  }
  for (int i = 0; i <= n; ++i) {
    if (cnt[i] > 0) {
      ++times[cnt[i]];
      times2[cnt[i]] += cnt[i];
    }
  }
  for (int i = n; i >= 0; --i)
    times[i] += times[i + 1];
  for (int i = 1; i <= n; ++i)
    times2[i] += times2[i - 1];
  for (int k = 1; k <= n; ++k) {
    int low = 0, high = n + 1;
    while (low + 1 < high) {
      int mid = (low + high) / 2;
      if (get(mid) >= k)
        low = mid;
      else
        high = mid;
    }
    printf("%d\n", low);
  }
  return 0;
}

Submission Info

Submission Time
Task F - Distinct Numbers
User mini4141
Language C++14 (GCC 5.4.1)
Score 600
Code Size 823 Byte
Status
Exec Time 79 ms
Memory 4352 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:14:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:17:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
                    ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 600 / 600 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 1 ms 256 KB
00-sample-02.txt 1 ms 256 KB
00-sample-03.txt 1 ms 256 KB
01-small-01.txt 1 ms 256 KB
01-small-02.txt 1 ms 256 KB
01-small-03.txt 1 ms 256 KB
01-small-04.txt 1 ms 256 KB
01-small-05.txt 1 ms 256 KB
01-small-06.txt 1 ms 256 KB
01-small-07.txt 1 ms 256 KB
01-small-08.txt 1 ms 256 KB
01-small-09.txt 1 ms 256 KB
01-small-10.txt 1 ms 256 KB
02-medium-01.txt 1 ms 256 KB
02-medium-02.txt 1 ms 256 KB
02-medium-03.txt 1 ms 256 KB
02-medium-04.txt 1 ms 256 KB
02-medium-05.txt 1 ms 256 KB
02-medium-06.txt 1 ms 256 KB
02-medium-07.txt 1 ms 256 KB
02-medium-08.txt 1 ms 256 KB
02-medium-09.txt 1 ms 256 KB
02-medium-10.txt 1 ms 256 KB
11-large-01.txt 49 ms 2816 KB
11-large-02.txt 52 ms 2944 KB
11-large-03.txt 62 ms 3456 KB
21-biased-01.txt 57 ms 3328 KB
21-biased-02.txt 62 ms 3584 KB
21-biased-03.txt 39 ms 2304 KB
31-uni-01.txt 60 ms 2560 KB
31-uni-02.txt 63 ms 2688 KB
31-uni-03.txt 75 ms 3200 KB
41-distinct-01.txt 56 ms 3200 KB
41-distinct-02.txt 63 ms 3584 KB
41-distinct-03.txt 76 ms 4224 KB
51-min-01.txt 1 ms 256 KB
52-max-01.txt 79 ms 4352 KB
52-max-02.txt 79 ms 4352 KB
52-max-03.txt 79 ms 4352 KB
61-sqrt-01.txt 71 ms 3200 KB