Submission #241123

#	Time	Username	Problem	Language	Result	Execution time	Memory
241123		aggu_01000101	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	77 ms	14316 KiB

joi2019_ho_t4

#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
 */

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