結果

問題 No.1838 Modulo Straight
コンテスト
ユーザー Nachia
提出日時 2022-02-11 21:52:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 313 ms / 2,000 ms
コード長 1,556 bytes
コンパイル時間 981 ms
コンパイル使用メモリ 87,512 KB
最終ジャッジ日時 2025-01-27 21:30:15
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/fenwicktree>
using namespace std;


using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned int;
#define rep(i,n) for(int i=0; i<(int)(n); i++)


i64 inversion(vector<int> P){
    int n = P.size();
    atcoder::fenwick_tree<int> G(n);
    i64 ans = 0;
    for(auto p : P){
        ans += G.sum(p+1, n);
        G.add(p, 1);
    }
    return ans;
}

vector<i64> rot_inversion(vector<int> A){
    int n = A.size();
    vector<int> X(n); rep(i,n) X[i] = i;
    sort(X.begin(), X.end(), [&](int l, int r)->bool{ return A[l] < A[r]; });
    rep(i,n) A[X[i]] = i;
    vector<i64> res;
    res.push_back(inversion(A));
    rep(i,n) res.push_back(res.back() + (n-1-2*A[i]));
    return res;
}


int main() {
    int N, P; cin >> P >> N;
    vector<int> A(N*P);
    vector<vector<int>> pos(P);
    rep(i,N*P){
        int a; cin >> a;
        A[i] = a;
        pos[a].push_back(i);
    }

    vector<int> tA(N*P);
    rep(i,P) rep(j,N) tA[pos[i][j]] = j;
    i64 off = inversion(tA);

    vector<i64> dInv(P, off);
    rep(i,N){
        vector<int> subA(P);
        rep(j,P) subA[j] = pos[j][i];
        auto tmp = rot_inversion(move(subA));
        rep(j,P) dInv[j] += tmp[j];
    }

    i64 ans = (i64)N*P*N*P;
    rep(i,P) ans = min(ans, dInv[i]);
    cout << ans << "\n";

    return 0;
}




struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0