//#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") //#pragma warning(disable : 4996) #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i, n) for(int i = 0;i < n;++i) #define REPR(i, n) for(int i = n-1;i >= 0;--i) #define FOR(i, m, n) for(int i = m;i < n;++i) #define FORR(i, m, n) for(int i = m-1;i >= n;--i) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define REVERSE(v,n) reverse(v,v+n); #define VREVERSE(v) reverse(v.begin(), v.end()) #define ll long long #define print(x) cout<<(x)<<'\n' #define pe(x) cout<<(x)<<" " #define DEBUG(x) cout<<#x<<": "< inline void chmin(T1 & a, T2 b) { if (a > b) a = b; } template inline void chmax(T1& a, T2 b) { if (a < b) a = b; } typedef pairpii; typedef array arr3; std::random_device rd; std::mt19937 mt(rd()); constexpr ll MOD = 1e9 + 7; constexpr int MAX = 2000020; const double pi = acos(-1); constexpr double EPS = 1e-8; constexpr ll INF = 1e18; void yes(bool c) { if (c)print("Yes"); else print("No"); }; //const int mod = 1000000007; const int mod = 998244353; struct mint { ll x; // typedef long long ll; mint(ll x = 0) :x((x%mod + mod) % mod) {} mint operator-() const { return mint(-x); } mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint a) { if ((x += mod - a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint a) const { return mint(*this) += a; } mint operator-(const mint a) const { return mint(*this) -= a; } mint operator*(const mint a) const { return mint(*this) *= a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t >> 1); a *= a; if (t & 1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod - 2); } mint& operator/=(const mint a) { return *this *= a.inv(); } mint operator/(const mint a) const { return mint(*this) /= a; } }; istream& operator>>(istream& is, const mint& a) { return is >> a.x; } ostream& operator<<(ostream& os, const mint& a) { return os << a.x; } int A[1010][1010]; void solve() { int N; cin >> N; //vectorans(N); vector>X(N),Y(N); REP(i, N) { REP(j, N) { int a; cin >> a; a--; X[a].push_back(i); Y[a].push_back(j); } } ll ans = 0; REP(i, N) { int l = 0, r = N; int ret = 1e9; while (r - l > 10) { int m1 = (l * 2 + r) / 3, m2 = (l + r * 2); int res1 = 0, res2 = 0; REP(j, N) { res1 += Y[i][j]; int x1 = m1 + Y[i][j],x2= m1 - Y[i][j]; if (X[i][j] > x1)res1 += X[i][j] - x1; else if (X[i][j] < x2)res1 += x2 - X[i][j]; } REP(j, N) { res1 += Y[i][j]; int x1 = m2 + Y[i][j], x2 = m2 - Y[i][j]; if (X[i][j] > x1)res1 += X[i][j] - x1; else if (X[i][j] < x2)res1 += x2 - X[i][j]; } if (res1 < res2)r = m2; else l = m1; ret = min({ ret,res1,res2 }); } FOR(m, l, r + 1) { int res1 = 0; REP(j, N) { res1 += Y[i][j]; int x1 = m + Y[i][j], x2 = m - Y[i][j]; if (X[i][j] > x1)res1 += X[i][j] - x1; else if (X[i][j] < x2)res1 += x2 - X[i][j]; } ret = min(ret, res1); } ans += ret; } print(ans); } signed main() { cin.tie(0); ios::sync_with_stdio(false); //int q; cin >> q; //while (q--) solve(); }