結果
問題 | No.2627 Unnatural Pitch |
ユーザー |
👑 |
提出日時 | 2024-02-09 23:18:00 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 192 ms / 4,000 ms |
コード長 | 1,900 bytes |
コンパイル時間 | 193 ms |
コンパイル使用メモリ | 32,000 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-28 16:29:47 |
合計ジャッジ時間 | 2,998 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <stdio.h>void merge_sort(int n, long long x[]){static long long y[200001] = {};if (n <= 1) return;merge_sort(n / 2, &(x[0]));merge_sort((n + 1) / 2, &(x[n/2]));int i, p, q;for (i = 0, p = 0, q = n / 2; i < n; i++) {if (p >= n / 2) y[i] = x[q++];else if (q >= n) y[i] = x[p++];else y[i] = (x[p] < x[q])? x[p++]: x[q++];}for (i = 0; i < n; i++) x[i] = y[i];}void chmin(long long *a, long long b){if (*a > b) *a = b;}int main(){int i, N, K;long long L, U, A[200001];scanf("%d %d %lld %lld", &N, &K, &L, &U);for (i = 0; i < N; i++) scanf("%lld", &(A[i]));merge_sort(N, A);long long ans = 1LL << 60, tmp[2], l = 0, r = 1000000000000LL / K, m, mm;while (l < r) {m = (l + r) / 2;mm = m + 1;for (i = 0, tmp[0] = 0; i < N; i++) {if (A[i] < m * K) tmp[0] += (m * K - A[i] + K - 1) / K;else if (A[i] > m * K + U - L) tmp[0] += (A[i] - (m * K + U - L) + K - 1) / K;}for (i = 0, tmp[1] = 0; i < N; i++) {if (A[i] < mm * K) tmp[1] += (mm * K - A[i] + K - 1) / K;else if (A[i] > mm * K + U - L) tmp[1] += (A[i] - (mm * K + U - L) + K - 1) / K;}if (tmp[0] <= tmp[1]) r = m;else l = m + 1;}l--;if (l < 0) l = 0;l = l * K;r = l + K * 2;int j, jj, num[2][200001] = {};for (i = 0, tmp[0] = 0; i < N; i++) {if (A[i] < l) {num[0][A[i]%K]++;tmp[0] += (l - A[i] + K - 1) / K;} else if (A[i] > l + U - L) {num[1][A[i]%K]++;tmp[0] += (A[i] - (l + U - L) + K - 1) / K;}}chmin(&ans, tmp[0]);for (j = 0; j < N && A[j] < l; j++);for (jj = j; jj < N && A[jj] <= l + U - L; jj++);for (l++; l < r; l++) {while (j < N && A[j] == l - 1) {num[0][A[j]%K]++;j++;}tmp[0] += num[0][(l-1)%K] - num[1][(l+U-L)%K];chmin(&ans, tmp[0]);while (jj < N && A[jj] == l + U - L) {num[1][A[jj]%K]--;jj++;}}printf("%lld\n", ans);fflush(stdout);return 0;}