제출 #241123

#제출 시각아이디문제언어결과실행 시간메모리
241123aggu_01000101Coin Collecting (JOI19_ho_t4)C++14
100 / 100
77 ms14316 KiB
#include <bits/stdc++.h>
#define int long long
#define INF 100000000
using namespace std;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int cost = 0;
    int mat[2*n+1][3];
    for(int i = 0;i<=(2*n);i++){
        for(int j = 0;j<3;j++) mat[i][j] = 0;
    }
    vector<int> coin[3], need[3];
    for(int i = 0;i<(2*n);i++){
        int x, y;
        cin>>x>>y;
        if(y<=1){
            cost+=(1 - y);
            y = 1;
        }
        else{
            cost+=(y - 2);
            y = 2;
        }
        if(x<1){
            cost += (1 - x);
            x = 1;
        }
        if(x>n){
            cost += (x - n);
            x = n;
        }
        mat[x][y]++;
    }
    for(int i = 1;i<=(2*n);i++){
        for(int j = 1;j<=2;j++){
            if(mat[i][j] == 0) need[j].push_back(i);
            while(mat[i][j] > 1){
                coin[j].push_back(i);
                mat[i][j]--;
            }
            while(need[j].size() && coin[j].size()){
                cost+=(abs(need[j].back() - coin[j].back()));
                need[j].pop_back(); coin[j].pop_back();
            }
        }
        for(int j = 1;j<=2;j++){
            int k = j^3;
            while(need[k].size() && coin[j].size()){
                cost+=(abs(need[k].back() - coin[j].back()) + 1);
                need[k].pop_back(); coin[j].pop_back();
            }
        }
        //cout<<i<<endl;
    }
    cout<<cost<<endl;

}
/*

5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3
 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...