結果
問題 | No.1838 Modulo Straight |
ユーザー | satashun |
提出日時 | 2022-02-11 22:23:29 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 300 ms / 2,000 ms |
コード長 | 4,965 bytes |
コンパイル時間 | 2,331 ms |
コンパイル使用メモリ | 214,052 KB |
実行使用メモリ | 56,304 KB |
最終ジャッジ日時 | 2024-06-27 19:44:05 |
合計ジャッジ時間 | 8,315 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 3 ms
5,376 KB |
testcase_11 | AC | 300 ms
56,204 KB |
testcase_12 | AC | 282 ms
56,304 KB |
testcase_13 | AC | 286 ms
56,204 KB |
testcase_14 | AC | 284 ms
56,076 KB |
testcase_15 | AC | 278 ms
55,948 KB |
testcase_16 | AC | 193 ms
31,888 KB |
testcase_17 | AC | 194 ms
31,756 KB |
testcase_18 | AC | 191 ms
31,756 KB |
testcase_19 | AC | 160 ms
23,960 KB |
testcase_20 | AC | 168 ms
23,956 KB |
testcase_21 | AC | 161 ms
23,964 KB |
testcase_22 | AC | 58 ms
10,308 KB |
testcase_23 | AC | 59 ms
10,052 KB |
testcase_24 | AC | 54 ms
10,064 KB |
testcase_25 | AC | 64 ms
10,112 KB |
testcase_26 | AC | 68 ms
10,240 KB |
testcase_27 | AC | 81 ms
10,972 KB |
testcase_28 | AC | 84 ms
10,144 KB |
testcase_29 | AC | 91 ms
11,056 KB |
testcase_30 | AC | 96 ms
11,536 KB |
testcase_31 | AC | 107 ms
12,536 KB |
testcase_32 | AC | 122 ms
15,232 KB |
testcase_33 | AC | 198 ms
31,636 KB |
testcase_34 | AC | 189 ms
31,764 KB |
testcase_35 | AC | 130 ms
18,936 KB |
testcase_36 | AC | 119 ms
14,352 KB |
testcase_37 | AC | 98 ms
10,872 KB |
testcase_38 | AC | 84 ms
10,128 KB |
testcase_39 | AC | 44 ms
19,084 KB |
testcase_40 | AC | 2 ms
5,376 KB |
ソースコード
//#pragma GCC optimize("Ofast")//#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using pii = pair<int, int>;template <class T>using V = vector<T>;template <class T>using VV = V<V<T>>;template <class T>V<T> make_vec(size_t a) {return V<T>(a);}template <class T, class... Ts>auto make_vec(size_t a, Ts... ts) {return V<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));}#define pb push_back#define eb emplace_back#define mp make_pair#define fi first#define se second#define rep(i, n) rep2(i, 0, n)#define rep2(i, m, n) for (int i = m; i < (n); i++)#define per(i, b) per2(i, 0, b)#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)#define ALL(c) (c).begin(), (c).end()#define SZ(x) ((int)(x).size())constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }template <class T, class U>void chmin(T& t, const U& u) {if (t > u) t = u;}template <class T, class U>void chmax(T& t, const U& u) {if (t < u) t = u;}template <class T>void mkuni(vector<T>& v) {sort(ALL(v));v.erase(unique(ALL(v)), end(v));}template <class T>vector<int> sort_by(const vector<T>& v) {vector<int> res(v.size());iota(res.begin(), res.end(), 0);sort(res.begin(), res.end(), [&](int i, int j) { return v[i] < v[j]; });return res;}template <class T, class U>istream& operator>>(istream& is, pair<T, U>& p) {is >> p.first >> p.second;return is;}template <class T, class U>ostream& operator<<(ostream& os, const pair<T, U>& p) {os << "(" << p.first << "," << p.second << ")";return os;}template <class T>istream& operator>>(istream& is, vector<T>& v) {for (auto& x : v) {is >> x;}return is;}template <class T>ostream& operator<<(ostream& os, const vector<T>& v) {os << "{";rep(i, v.size()) {if (i) os << ",";os << v[i];}os << "}";return os;}#ifdef LOCALvoid debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {cerr << " " << H;debug_out(T...);}#define debug(...) \cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl#else#define debug(...) (void(0))#define dump(x) (void(0))#endiftemplate <class T>void scan(vector<T>& v, T offset = T(0)) {for (auto& x : v) {cin >> x;x += offset;}}template <class T>void print(T x, int suc = 1) {cout << x;if (suc == 1)cout << "\n";else if (suc == 2)cout << " ";}template <class T>void print(const vector<T>& v, int suc = 1) {for (int i = 0; i < v.size(); ++i)print(v[i], i == int(v.size()) - 1 ? suc : 2);}struct prepare_io {prepare_io() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(10);}} prep_io;template <class T>struct BIT {int n;vector<T> bit;BIT(int _n = 0) : n(_n), bit(n + 1) {}// sum of [0, i), 0 <= i <= nT sum(int i) {T s = 0;while (i > 0) {s += bit[i];i -= i & -i;}return s;}// 0 <= i < nvoid add(int i, T x) {++i;while (i <= n) {bit[i] += x;i += i & -i;}}//[l, r) 0 <= l < r < nT sum(int l, int r) { return sum(r) - sum(l); }// verify!!!!// smallest i, sum(i) >= w, none -> n + 1int lower_bound(T w) {if (w <= 0) return 0;int x = 0, l = 1;while (l * 2 <= n) l *= 2;for (int k = l; k > 0; k /= 2) {if (x + k <= n && bit[x + k] < w) {w -= bit[x + k];x += k;}}return x + 1;}};template <class T>ll inversion(const V<T>& vec) {int n = vec.size();BIT<int> bit(n + 10);ll res = 0;rep(i, n) {res += i - bit.sum(vec[i] + 1);bit.add(vec[i], 1);}return res;}void slv() {int M, K;cin >> M >> K;int N = M * K;V<int> A(N);cin >> A;VV<int> vp(M);rep(i, N) vp[A[i]].pb(i);V<int> to(N);rep(i, M) {rep(j, K) { to[vp[i][j]] = i + j * M; }}debug(to);ll cur = inversion(to);ll ans = cur;debug(cur);auto pos = make_vec<int>(M, K);rep(j, K) {V<pii> vec;rep(i, M) { vec.eb(vp[i][j], i); }sort(ALL(vec));rep(i, M) { pos[vec[i].se][j] = i; }}rep(i, M - 1) {rep(j, K) {ll ch = (M - 1 - pos[i][j]) - pos[i][j];cur += ch;}debug(i + 1, cur);chmin(ans, cur);}print(ans);}int main() {int cases = 1;// cin >> cases;rep(i, cases) slv();return 0;}