test/yukicoder/1028.test.cpp

View this file on GitHub
Last update: 2020-04-18 20:15:36+09:00
Problem: https://yukicoder.me/problems/no/1028

Depends on

src/Helper/TernarySearch.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/1028"

#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef _MY_DEBUG
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sat Apr 18 15:55:11 JST 2020
 **/

#define CALL_FROM_TEST
#include "../../src/Helper/TernarySearch.hpp"
#undef CALL_FROM_TEST

using pii = std::pair<Int, Int>;
signed main() {
    Int n;
    std::cin >> n;
    std::vector<std::vector<pii>> ps(n);
    REP(i, n) REP(j, n) {
        Int x;
        std::cin >> x;
        ps[x - 1].push_back({i, j});
    }
    Int ans = 0;
    REP(idx, n) {
        auto f = [&](Int mid) {
            Int ret = 0;
            for (pii& p : ps[idx]) {
                ret += std::max(std::abs(mid - p.first), p.second);
            }
            return ret;
        };

        Int mi_idx = ternary_search(0LL, n, f, false);
        ans += f(mi_idx);
    }
    std::cout << ans << std::endl;
}

#line 1 "test/yukicoder/1028.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1028"

#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef _MY_DEBUG
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sat Apr 18 15:55:11 JST 2020
 **/

#define CALL_FROM_TEST
#line 1 "src/Helper/TernarySearch.hpp"
/// @docs src/Helper/TernarySearch.md
template <class F, class T = long long> T ternary_search(T l, T r, F f, bool is_max = true) {
    auto g = [&f, &is_max](T x) { return is_max ? f(x) : -f(x); };
    while (std::abs(l - r) > 2) {
        T m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
        if (g(m1) < g(m2))
            l = m1;
        else
            r = m2;
    }
    // 極値のindexは[l, r)の範囲で、abs(l - r) <= 2になっている
    if (l + 1 < r && g(l + 1) > g(l)) l = l + 1;
    return l;
}
#line 19 "test/yukicoder/1028.test.cpp"
#undef CALL_FROM_TEST

using pii = std::pair<Int, Int>;
signed main() {
    Int n;
    std::cin >> n;
    std::vector<std::vector<pii>> ps(n);
    REP(i, n) REP(j, n) {
        Int x;
        std::cin >> x;
        ps[x - 1].push_back({i, j});
    }
    Int ans = 0;
    REP(idx, n) {
        auto f = [&](Int mid) {
            Int ret = 0;
            for (pii& p : ps[idx]) {
                ret += std::max(std::abs(mid - p.first), p.second);
            }
            return ret;
        };

        Int mi_idx = ternary_search(0LL, n, f, false);
        ans += f(mi_idx);
    }
    std::cout << ans << std::endl;
}