結果

問題 No.3063 Circle Balancing
ユーザー rin204
提出日時 2024-07-07 16:48:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,516 bytes
コンパイル時間 3,128 ms
コンパイル使用メモリ 251,004 KB
実行使用メモリ 7,040 KB
最終ジャッジ日時 2024-07-07 16:48:56
合計ジャッジ時間 23,460 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 頻度配列 top K だけ見る
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    assert(1 <= n and n <= 300000);
    vector<int> C(n);
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        assert(1 <= A[i] and A[i] <= n);
        A[i]--;
        C[A[i]]++;
    }
    vector<int> ind(n);
    iota(ind.begin(), ind.end(), 0);

    sort(ind.begin(), ind.end(), [&](int i, int j) { return C[i] > C[j]; });
    int ans = 1 << 30;

    int b = min(n, 1000);

    for (int i = 0; i < b; i++) {
        int p = ind[i];
        int s = -1;
        for (int j = 0; j < n; j++) {
            if (A[j] == p) {
                s = j;
                break;
            }
        }
        if (s == -1) break;
        int dp0 = 0;
        int dp1 = 0;
        int tot = 0;
        s       = (s + 1) % n;
        for (int _ = 0; _ < n; _++) {
            if (A[s] == p) {
                tot += min(dp0, dp1);
                dp0 = 0;
                dp1 = 0;
            } else {
                tot++;
                int ndp0, ndp1;
                if (A[s] > p) {
                    ndp0 = dp0;
                    ndp1 = min(dp0, dp1) + 1;
                } else {
                    ndp0 = dp0 + 1;
                    ndp1 = min(dp0, dp1);
                }
                dp0 = ndp0;
                dp1 = ndp1;
            }
            s++;
            if (s == n) s = 0;
        }
        ans = min(ans, tot);
    }
    cout << ans << endl;
}
0