Submission #1139470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139470		DeathIsAwe	Coin Collecting (JOI19_ho_t4)	C++20	100 / 100	103 ms	1972 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ll long long
int grid[100000][2];



int main() {
    for (int i=0;i<100000;i++) {
        grid[i][0] = 0; grid[i][1] = 0;
    }
    ll ans = 0, d1, d2;
    int n; cin >> n;
    
    for (int i=0;i<2*n;i++) {
        cin >> d1 >> d2;
        d1 -= 1; d2 -= 1;
        if (d1 <= 0 && d2 <= 0) {
            grid[0][0] += 1;
            ans += -d1 - d2;
        } else if (d1 <= 0 && d2 >= 1) {
            grid[0][1] += 1;
            ans += -d1 + d2 - 1;
        } else if (d1 >= n-1 && d2 >= 1) {
            grid[n-1][1] += 1;
            ans += d1 + d2 - (n - 1) - 1; 
        } else if (d1 >= n-1 && d2 <= 0) {
            grid[n-1][0] += 1;
            ans += d1 - d2 - (n - 1);
        } else if (d2 >= 1) {
            grid[d1][1] += 1;
            ans +=  d2 - 1;
        } else  if (d2 <= 0) {
            grid[d1][0] += 1;
            ans += -d2;
        }
    }
    //for (int i=0;i<n;i++) {
    //    cout << grid[i][1] << ' ';
    //} cout << '\n';
    //for (int i=0;i<n;i++) {
    //    cout << grid[i][0] << ' ';
    //} cout << '\n';
    //cout << ans << '\n' << '\n';

    deque<int> toprow0, botrow0;
    deque<pair<int,int>> toprowmore, botrowmore;
    for (int i=0;i<n;i++) {
        if (grid[i][0] == 0) {
            botrow0.push_back(i);
        } else if (grid[i][0] > 1) {
            botrowmore.push_back(mp(i, grid[i][0] - 1));
        }
        if (grid[i][1] == 0) {
            toprow0.push_back(i);
        } else if (grid[i][1] > 1) {
            toprowmore.push_back(mp(i, grid[i][1] - 1));
        }

        while (botrow0.size() > 0 && botrowmore.size() > 0) {
            ans += abs(botrow0[0] - botrowmore[0].ff);
            botrowmore[0].ss -= 1;
            if (botrowmore[0].ss == 0) {
                botrowmore.pop_front();
            }
            botrow0.pop_front();
        }
        while (toprow0.size() > 0 && toprowmore.size() > 0) {
            ans += abs(toprow0[0] - toprowmore[0].ff);
            toprowmore[0].ss -= 1;
            if (toprowmore[0].ss == 0) {
                toprowmore.pop_front();
            }
            toprow0.pop_front();
        }

        while (toprow0.size() > 0 && botrowmore.size() > 0) {
            ans += abs(toprow0[0] - botrowmore[0].ff) + 1;
            botrowmore[0].ss -= 1;
            if (botrowmore[0].ss == 0) {
                botrowmore.pop_front();
            }
            toprow0.pop_front();
        }
        while (botrow0.size() > 0 && toprowmore.size() > 0) {
            ans += abs(botrow0[0] - toprowmore[0].ff) + 1;
            toprowmore[0].ss -= 1;
            if (toprowmore[0].ss == 0) {
                toprowmore.pop_front();
            }
            botrow0.pop_front();
        }
    }
    cout << ans;
}

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