Submission #142793

#TimeUsernameProblemLanguageResultExecution timeMemory
142793DrumpfTheGodEmperorCoin Collecting (JOI19_ho_t4)C++14
100 / 100
68 ms9208 KiB
#include <bits/stdc++.h> #define int long long #define bp __builtin_popcountll #define pb push_back #define in(s) freopen(s, "r", stdin); #define out(s) freopen(s, "w", stdout); #define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\ freopen((string(s) + "." + end2).c_str(), "w", stdout); #define fi first #define se second #define bw(i, r, l) for (int i = r - 1; i >= l; i--) #define fw(i, l, r) for (int i = l; i < r; i++) #define fa(i, x) for (auto i: x) using namespace std; const int mod = 1e9 + 7, inf = 1061109567; const long long infll = 4557430888798830399; const int N = 2e5 + 5; int n, x[N], y[N], ans = 0, cnt[N][3]; signed main() { #ifdef BLU in("blu.inp"); // out("ans1.out"); #endif ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; fw (i, 0, n * 2) cin >> x[i] >> y[i]; //x and y are NOT independent (same y same x case) fw (i, 0, n * 2) { if (x[i] < 1) { ans += (1 - x[i]); x[i] = 1; } else if (x[i] > n) { ans += (x[i] - n); x[i] = n; } if (y[i] < 1) { ans += (1 - y[i]); y[i] = 1; } else if (y[i] > 2) { ans += (y[i] - 2); y[i] = 2; } cnt[x[i]][y[i]]++; // cout << "cnt[" << x[i] << "][" << y[i] << "] = " << cnt[x[i]][y[i]] << "\n"; } int prf[3]; prf[1] = prf[2] = 0; fw (i, 1, n + 1) { fw (j, 1, 3) { prf[j] += cnt[i][j] - 1; //Leave 1 coin at current position. //If there are no coins to be placed prf[j] is negative. } fw (j, 1, 3) { int other = 2; if (j == 2) other = 1; if (prf[j] > 0 && prf[other] < 0) { //Transfer across columns int transferred = min(prf[j], -prf[other]); prf[j] -= transferred; prf[other] += transferred; ans += transferred; } } fw (j, 1, 3) { //If prf is negative it needs to be transferred from the right. Add by abs ans += abs(prf[j]); } } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...