Submission #1063984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063984		_8_8_	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	34 ms	6236 KiB

joi2019_ho_t4

#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();
    }
}  

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63