Submission #1354123

#TimeUsernameProblemLanguageResultExecution timeMemory
1354123guardianecCoin Collecting (JOI19_ho_t4)C++20
100 / 100
28 ms8944 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin >> n;
    vector<pair<ll,ll>> a(2*n+1);
    for (int i=1; i<=2*n; i++) {
        cin >> a[i].first >> a[i].second;
    }

    vector<vector<ll>> freq(n+1, vector<ll>(2));
    ll res = 0;
    for (int i=1; i<=2*n; i++) {
        if (a[i].first>0 && a[i].first<=n) {
            if (a[i].second<1) {freq[a[i].first][0]++; res+=abs(a[i].second)+1;}
            else if (a[i].second>2) {freq[a[i].first][1]++; res+=abs(a[i].second)-2;}
            else freq[a[i].first][a[i].second-1]++;
        } else if (a[i].first<1) {
            if (a[i].second<1) {freq[1][0]++; res+=(abs(a[i].second)+1+abs(a[i].first)+1);}
            else if (a[i].second>2) {freq[1][1]++; res+=(abs(a[i].second)-2+abs(a[i].first)+1);}
            else {freq[1][a[i].second-1]++; res+=abs(a[i].first)+1;}
        } else {
            if (a[i].second<1) {freq[n][0]++; res+=(abs(a[i].first-n)+abs(a[i].second)+1);}
            else if (a[i].second>2) {freq[n][1]++; res+=(abs(a[i].first-n)+abs(a[i].second)-2);}
            else {freq[n][a[i].second-1]++; res+=abs(a[i].first-n);}
        }
    }

    ll s1 = 0;
    ll s2 = 0;
    for (int i=1; i<=n; i++) {
        if (freq[i][0]==0) s1--;
        else s1+=freq[i][0]-1;
        if (freq[i][1]==0) s2--;
        else s2+=freq[i][1]-1;

        if (s1<0 && s2>0) {
            ll m = min(abs(s1), s2);
            res+=m;
            s1+=m;
            s2-=m;
        } else if (s1>0 && s2<0) {
            ll m = min(s1, abs(s2));
            res+=m;
            s2+=m;
            s1-=m;
        }
        res+=abs(s1)+abs(s2);
    }

    cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...