Submission #762307

#TimeUsernameProblemLanguageResultExecution timeMemory
762307sysiaCoin Collecting (JOI19_ho_t4)C++17
100 / 100
50 ms15420 KiB
//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long typedef pair<int, int> T; const int oo = 1e18, oo2 = 1e9+7, K = 30; const int mod = 998244353; void solve(){ int n; cin >> n; int N = 2*n; int ans = 0; vector<T>a(N); vector cnt(n+2, vector<int>(3)); for (auto &[x, y] : a){ cin >> x >> y; if (x < 1) { ans += (1-x); x = 1; } if (x > n){ ans += (x - n); x = n; } if (y < 1){ ans += (1 - y); y = 1; } if (y > 2){ ans += (y - 2); y = 2; } cnt[x][y-1]++; } debug(ans); // for (int j = 1; j>=0; j--){ // for (int i = 1; i<=n; i++){ // cerr << cnt[i][j] << " "; // } // cerr << "\n"; // } vector<int>leave(2), mv(2); for (int what = 0; what < 2; what++){ vector<int>ord; int sgn; if (!what) { for (int i = 1; i<=n; i++) ord.emplace_back(i); sgn = 1; } else { for (int i = n; i>=1; i--) ord.emplace_back(i); sgn = -1; } for (auto i: ord){ debug(i, ans, cnt[i][0], cnt[i][1]); int d = cnt[i][0] + cnt[i][1]; if (d < 2){ //musimy znalezc cos zeby przyciagnac for (int rep = 0; rep < 2; rep++){ if (!cnt[i][rep]){ leave[rep]++; } } continue; } //d >= 2 mv[0] = 0; mv[1] = 0; for (int rep = 0; rep < 2; rep++){ int t = min(leave[rep], max(0ll, cnt[i][rep]-1)); //t zostaje w miejscu, przesuwamy je pozniej w lewo na tym samym lvl leave[rep] -= t; ans += t; cnt[i-sgn][rep] += t; cnt[i][rep] -= t; mv[rep] = max(0ll, cnt[i][rep]-1); } debug(cnt[i][0], cnt[i][1]); debug(mv); for (int rep = 0; rep < 2; rep++){ if (leave[rep]){ int t = min(mv[rep^1], leave[rep]); //tyle mozemy ukrasc i przesunac w pionie, by potem miec na lewo ans += 2*t; cnt[i-sgn][rep] += t; cnt[i][rep^1] -= t; leave[rep] -= t; } } d = cnt[i][0] + cnt[i][1]; if (d < 2){ for (int rep = 0; rep < 2; rep++){ if (!cnt[i][rep]){ leave[rep]++; } } continue; } for (int rep = 0; rep < 2; rep++){ if (!cnt[i][rep] && mv[rep^1]){ ans++; cnt[i][rep]++; cnt[i][rep^1]--; } } for (int rep = 0; rep < 2; rep++){ cnt[i+sgn][rep] += (cnt[i][rep]-1); ans += (cnt[i][rep]-1); cnt[i][rep] = 1; } debug(cnt[i][0], cnt[i][1]); } // for (int j = 1; j>=0; j--){ // for (int i = 1; i<=n; i++){ // cerr << cnt[i][j] << " "; // } // cerr << "\n"; // } // debug(ans); // return; } cout << ans << "\n"; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...