Submission #1063984

#TimeUsernameProblemLanguageResultExecution timeMemory
1063984_8_8_Coin Collecting (JOI19_ho_t4)C++17
100 / 100
34 ms6236 KiB
#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 1e6 + 12, MOD = (int)1e9 + 7;
#define int ll
int n;
int c[N][3],a[N];
int dist(int x,int y,int x1,int y1) {
    return abs(x - x1) + abs(y - y1);
}
ll ans = 0;
void test() {
    cin >> n;
    for(int i = 1;i <= n + n;i++) {
        int a,b;
        cin >> a >> b;
        int x = 1,y = 1;
        auto upd = [&](int x1,int y1) {
            if(dist(x1,y1,a,b) < dist(x,y,a,b)) {
                x = x1;
                y = y1;
            }
        };
        upd(1,2);
        upd(n,1);
        upd(n,2);
        if(a >= 1 && a <= n) {
            upd(a,1);
            upd(a,2);
        }
        if(b >= 1 && b <= 2) {
            upd(1,b);
            upd(n,b);
        }
        c[x][y]++;
        ans += dist(x,y,a,b);
    }
    int x = 0,y = 0;
    for(int i = 1;i <= n;i++) { 
        x += (c[i][1] - 1);
        y += (c[i][2] - 1);
        if(x < 0 && y > 0) {
            int c = min(abs(x),abs(y));
            ans += c;
            x += c;
            y -=c ;
        } else if(x > 0 && y < 0) {
            int c = min(abs(x),abs(y));
            ans += c;
            x -= c;
            y +=c ;
        }
        ans += abs(x);
        ans += abs(y);
    }
    cout << ans;
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}  
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...