제출 #1299191

#제출 시각아이디문제언어결과실행 시간메모리
1299191makskusCoin Collecting (JOI19_ho_t4)C++20
100 / 100
31 ms1216 KiB
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <climits>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <functional>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <random>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0;a<b;a++)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
const int inf = 1e9;
const ll infl = 1e18;

int tab[100007][2];

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

    ll w = 0;

    rep(i, 2*n){
        ll a, b;
        cin >> a >> b;
        if(a >= 1 && a <= n){
            //cout << "sigma " << a << " " << b << "\n"; 
            if(b == 1 || b == 2){
                tab[a-1][b%2]++;
                //cout << "sigma " << a << " " << b << "\n"; 
            }
            else if(b < 1){
                tab[a-1][1]++;
                w += -b+1;
            }
            else{
                tab[a-1][0]++;
                w += b-2;
            }
        }
        else if(b == 1 || b == 2){
            if(a > n){
                tab[n-1][(b+1)%2]++;
                w += a-n;
            }
            else{
                tab[0][b%2]++;
                w += -a+1;
            }
        }
        else{
            if(a > n && b > 2){
                tab[n-1][0]++;
                w += a-n + b-2;
            }
            else if(a > n && b < 1){
                tab[n-1][1]++;
                w += a-n - b+1;
            }
            else if(a < 1 && b > 2){
                tab[0][0]++;
                w += -a+1 + b-2;
            }
            else if(a < 1 && b < 1){
                tab[0][1]++;
                w += -a+1 -b + 1;
            }
    
        }
    }

    rep(i, n-1){
        if(tab[i][0] > 0 && tab[i][1] > 0){
            w+=tab[i][0]-1;
            tab[i+1][0] += tab[i][0]-1;
            w+=tab[i][1]-1;
            tab[i+1][1] += tab[i][1]-1;
        }
        else if(tab[i][0] <= 0 && tab[i][1] <= 0){
            ll ile = abs(tab[i][0]-1);
            tab[i+1][0] -= ile;
            w+=ile;
            ile = abs(tab[i][1]-1);
            tab[i+1][1] -= ile;
            w+=ile;
        }
        else if(tab[i][0] <= 0 && tab[i][1] > 0){
            ll ile = min(tab[i][1] - 1, 1 + abs(tab[i][0]));
            tab[i][0] += ile;
            tab[i][1] -= ile;
            w += ile;
            if(tab[i][0] <= 0){
                tab[i+1][0] -= abs(tab[i][0] - 1);
                w += abs(tab[i][0] - 1);
            }
            if(tab[i][1] > 1){
                tab[i+1][1] += tab[i][1] - 1;
                w += tab[i][1] - 1;
            }
        }
        else if(tab[i][0] > 0 && tab[i][1] <= 0){
            ll ile = min(tab[i][0] - 1, 1 + abs(tab[i][1]));
            tab[i][1] += ile;
            tab[i][0] -= ile;
            w += ile;
            if(tab[i][1] <= 0){
                tab[i+1][1] -= abs(tab[i][1] - 1);
                w += abs(tab[i][1] - 1);
            }
            if(tab[i][0] > 1){
                tab[i+1][0] += tab[i][0] - 1;
                w += tab[i][0] - 1;
            }
        }
    }

    ll a = tab[n-1][0];
    ll b = tab[n-1][1];
    if(a < b){
        swap(a, b);
    }
    w += a-1;
    cout << w << "\n";
    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...