#1190773 (C++23(gcc16)) No.366 ロボットソート

• 問題: No.366 ロボットソート
• ユーザー: C
• 提出日時: 2026-09-30 00:04:10
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 3,836 bytes
• コンパイル時間: 7,047 ms
• コンパイル使用メモリ: 412,052 KB
• 実行使用メモリ: 9,836 KB
• 最終ジャッジ日時: 2026-09-30 00:04:22
• 合計ジャッジ時間: 8,749 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
other	AC * 23

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace atcoder;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using pll=pair<ll,ll>;

// using mint=modint;

// template<class K,class V>
// using ordered_map=tree<K,V,less<K>,rb_tree_tag,tree_order_statistics_node_update>;

#line 2 "dp/inversion-counting.hpp"

#line 2 "data-structure/binary-indexed-tree.hpp"

template <typename T>
struct BinaryIndexedTree {
  int N;
  vector<T> data;

  BinaryIndexedTree() = default;

  BinaryIndexedTree(int size) { init(size); }

  void init(int size) {
    N = size + 2;
    data.assign(N + 1, {});
  }

  // get sum of [0,k]
  T sum(int k) const {
    if (k < 0) return T{};  // return 0 if k < 0
    T ret{};
    for (++k; k > 0; k -= k & -k) ret += data[k];
    return ret;
  }

  // getsum of [l,r]
  inline T sum(int l, int r) const { return sum(r) - sum(l - 1); }

  // get value of k
  inline T operator[](int k) const { return sum(k) - sum(k - 1); }

  // data[k] += x
  void add(int k, T x) {
    for (++k; k < N; k += k & -k) data[k] += x;
  }

  // range add x to [l,r]
  void imos(int l, int r, T x) {
    add(l, x);
    add(r + 1, -x);
  }

  // minimize i s.t. sum(i) >= w
  int lower_bound(T w) {
    if (w <= 0) return 0;
    int x = 0;
    for (int k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] < w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }

  // minimize i s.t. sum(i) > w
  int upper_bound(T w) {
    if (w < 0) return 0;
    int x = 0;
    for (int k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] <= w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }
};

/**
 * @brief Binary Indexed Tree(Fenwick Tree)
 */
#line 4 "dp/inversion-counting.hpp"

// 転倒数
template <typename T>
long long inversion_counting(const vector<T>& v) {
  vector<T> xs{v};
  sort(begin(xs), end(xs));
  xs.erase(unique(begin(xs), end(xs)), end(xs));
  int s = xs.size();
  BinaryIndexedTree<long long> bit(s + 1);
  long long ans = 0;
  for (auto& x : v) {
    int i = lower_bound(begin(xs), end(xs), x) - begin(xs);
    if (i + 1 != s) ans += bit.sum(i + 1, s - 1);
    bit.add(i, 1);
  }
  return ans;
}

// 隣接 swap によって v を w に変えるのにかかる手数 (不可能 : -1)
template <typename T>
long long swap_distance(const vector<T>& v, const vector<T>& w) {
  if (v.size() != w.size()) return -1;
  int N = v.size();
  vector<pair<T, int>> vv(N), ww(N);
  for (int i = 0; i < N; i++) {
    vv[i] = make_pair(v[i], i);
    ww[i] = make_pair(w[i], i);
  }
  sort(begin(vv), end(vv));
  sort(begin(ww), end(ww));
  for (int i = 0; i < N; i++) {
    if (vv[i].first != ww[i].first) return -1;
  }
  vector<int> order(N);
  for (int i = 0; i < N; i++) {
    order[vv[i].second] = ww[i].second;
  }
  return inversion_counting(order);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    /*
    添字をKで割ったあまりでグループを作る、ソートはグループの中のみ行います、それだけで列全体をソートできるかの問題です。できれば、グループごとに転倒数を求めればいい。
    */

    ll N,K;
    cin>>N>>K;
    vll a(N);
    for(int i=0;i<N;++i)cin>>a[i];
    vll b=a;
    sort(b.begin(),b.end());

    ll ans=0;
    for(int r=0;r<K;++r){
        //グループ r
        vll now,goal;
        for(int i=r;i<N;i+=K){
            now.push_back(a[i]);
            goal.push_back(b[i]);
        }
        ll d=swap_distance(now,goal);
        if(d==-1){
            cout<<-1<<endl;
            return 0;
        }
        ans+=d;
    }

    cout<<ans<<endl;

}