Submission #376344

#	Time	Username	Problem	Language	Result	Execution time	Memory
376344		Nima_Naderi	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	80 ms	5248 KiB

joi2019_ho_t4

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 1e5 + 10;
ll n, ans, mini;
ll cnt[MXN][2];
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= 2 * n; i ++){
        ll x, y; 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] ++;
    }
    ll t0 = 0, t1 = 0;
    ll n0 = 0, n1 = 0;
    for(int i = 1; i <= n; i ++){
        t0 += cnt[i][1], t1 += cnt[i][2];
        n0 ++, n1 ++;
        if(t0 >= n0 && t1 >= n1){
            t0 -= n0; t1 -= n1;
            n0 = n1 = 0;
            ans += t0 + t1;
            continue;
        }
        if(t0 >= n0 + (n1 - t1) && t1 < n1){
            ans += (n1 - t1);
            t0 -= (n1 - t1), t1 += (n1 - t1);
            t0 -= n0; t1 -= n1;
            n0 = n1 = 0;
            ans += t0;
            continue;
        }
        if(t0 < n0 && t1 >= n1 + (n0 - t0)){
            ans += (n0 - t0);
            t1 -= (n0 - t0), t0 += (n0 - t0);
            t0 -= n0; t1 -= n1;
            n0 = n1 = 0;
            ans += t1;
            continue;
        }
        if(t0 > n0){
            ans += (t0 - n0);
            t1 += (t0 - n0), t0 -= (t0 - n0);
        }
        if(t1 > n1){
            ans += (t1 - n1);
            t0 += (t1 - n1), t1 -= (t1 - n1);
        }
        mini = min(n0, t0);
        n0 -= mini, t0 -= mini;
        mini = min(n1, t1);
        n1 -= mini, t1 -= mini;
        ans += n0 + n1;
        ans += t0 + t1;
    }
    assert(!n0 && !n1 && !t0 && !t1);
    cout << ans << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:24:40: warning: array subscript 2 is above array bounds of 'll [2]' {aka 'long long int [2]'} [-Warray-bounds]
   24 |         t0 += cnt[i][1], t1 += cnt[i][2];
      |                                ~~~~~~~~^

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