Submission #867982

#TimeUsernameProblemLanguageResultExecution timeMemory
867982Nuraly_SerikbayCoin Collecting (JOI19_ho_t4)C++17
8 / 100
20 ms4700 KiB
//çalışan kazanır// #include "bits/stdc++.h" using namespace std; #define int long long #define pb push_back #define S second #define F first #define all(x) x.begin(),x.end() #define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0) int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}} const int N = 4e5 + 15; const int INF = 1e18; const int MOD = 1e9 + 7; const int MODD = 1070234587ll; const double eps = 0.0001; const int p = 87; int n, x[N], y[N]; int cnt[N][3], dp[2001]; void solution () { cin >> n; for (int i = 1; i <= n * 2; ++ i) cin >> x[i] >> y[i]; int res = 0; for (int i = 1; i <= n * 2; ++ i) { if (1 <= x[i] && x[i] <= n) { if (1 <= y[i] && y[i] <= 2) cnt[x[i]][y[i]] ++; if (y[i] < 1) cnt[x[i]][1] ++, res += (1 - y[i]), y[i] = 1; if (2 < y[i]) cnt[x[i]][2] ++, res += (y[i] - 2), y[i] = 2; } if (x[i] < 1) { res += 1 - x[i]; if (1 <= y[i] && y[i] <= 2) cnt[1][y[i]] ++; if (y[i] < 1) cnt[1][1] ++, res += (1 - y[i]), y[i] = 1; if (2 < y[i]) cnt[1][2] ++, res += (y[i] - 2), y[i] = 2; x[i] = 1; } if (n < x[i]) { res += x[i] - n; if (1 <= y[i] && y[i] <= 2) cnt[n][y[i]] ++; if (y[i] < 1) cnt[n][1] ++, res += (1 - y[i]), y[i] = 1; if (2 < y[i]) cnt[n][2] ++, res += (y[i] - 2), y[i] = 2; x[i] = n; } // cout << "cors -> " << x[i] << ' ' << y[i] << '\n'; } // cout << res << '\n'; n *= 2; vector <pair <int, int>> ord; for (int i = 1; i <= n; ++ i) ord.pb ({x[i], y[i]}); sort (all (ord)); int mn = INF; for (int mask = 0; mask < (1 << n); ++ mask) { if (__builtin_popcount (mask) != n / 2) continue; int t = 0, tt = 0, cur = 0; for (int i = 0; i < n; ++ i) { if (((mask >> i) & 1)) { cur += abs(ord[i].F - (++t)); if (ord[i].S != 1) cur ++; } else { cur += abs(ord[i].F - (++tt)); if (ord[i].S == 1) cur ++; } } mn = min (mn, cur); } cout << res + mn; return; } signed main() { // YOSIK(); // srand (time(0)); // freopen ("E.in", "r", stdin); // freopen ("E.out", "w", stdout); int TT = 1;// cin >> TT; for (int i = 1; i <= TT; ++ i) { // cout << "Case " << i << ": "; solution (); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...