Submission #330914

#	Time	Username	Problem	Language	Result	Execution time	Memory
330914		caoash	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	78 ms	5796 KiB

joi2019_ho_t4

/*
 * Order of moving coins doesn't matter
 *
 * Manhattan distance always optimal?
 * - Assume we've assigned each coin to their destination.
 * - Then we move all by Manhattan distance
 * - start by assigning every coin to their closest destination
 *   - assign N coins to N positions to minimize sum of manhattan distances
 *   - solve for X and Y independently
 *      - for 1 row version they only need to be on diff X's
 *      - moves for Y is fixed?
 *          - sum of a_y - 1
 *      - in 2 row version
 *          - exactly 2 of each X
 *          - N "top" and N "bottom"
 *          - Y would be sum of abs(Y_i - 2) for tops + abs(Y_i - 1) for bottoms
 *              - assign greedily
 *              - given N values, find min sum of N of them abs(x - 2) + abs(x - 1)
 *                  - assign as many <= 1 as possible to abs(x - 1)
 *                  - assign as many > 1 as possible to abs(x - 2)
 *                  - move the remaining to wherever needed?
 *          - once we assign them to their Y's, we can break them up into two instances of 1 row problem
 *              - fairly convinced this is true?
 *              - how to solve 1d problem
 *                  - assign leftmost to leftmost, second to second, etc
 *      - for 2 row version we can do greedy over Y's
 * - then any moves to a different destination still follows Manhattan
 *   - nvm its not true
 *      - wtf its true
 *      - kekw
 *   - this constrains the problem to the box
 *   - so like just do some greedy in it i guess
 */

#include <bits/stdc++.h> 
using namespace std;

using ll = long long;

using vi = vector<int>;
using vl = vector<ll>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define lb lower_bound
#define ub upper_bound

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

const int MX = 200005;
const int MOD = (int) (1e9 + 7);
const ll INF = (ll) 1e18;

int num[2][MX];

int main(){
#ifdef mikey 
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    ll ans = 0;
    for (int i = 0; i < 2 * n; i++) {
        ll x, y; cin >> x >> y;
        ll go = x - 1;
        if (go < 0) ans += abs(go), go = 0;
        if (go >= n) ans += go - n + 1, go = n - 1;
        if (y <= 1) {
            ans += abs(y - 1);
            num[0][go]++;
        } else {
            ans += abs(y - 2);
            num[1][go]++;
        }
    }
    array<int, 2> pt;
    pt[0] = 0, pt[1] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            int &need = pt[j];    
            while (need < i && num[j][i] > 1) {
                if (num[j][need] == 0) {
                    num[j][i]--;
                    num[j][need]++;
                    // dbg("MOVE", i, j, need, j);
                    ans += abs(i - need);
                }
                ++need;
            }
        }
        for (int j = 0; j < 2; j++) {
            int &need = pt[j ^ 1];
            while (need < i && num[j][i] > 1) {
                if (num[j ^ 1][need] == 0) {
                    num[j][i]--;
                    num[j ^ 1][need]++;
                    // dbg("MOVE", i, j, need, j ^ 1);
                    ans += 1 + abs(i - need);
                }
                ++need;
            }
            if (num[j][i] > 1 && num[j ^ 1][i] == 0) {
                ++ans;
                num[j][i]--;
                num[j ^ 1][i]++;
                // dbg("MOVE", i, j, i, j ^ 1);
            }
            if (num[j][i] > 1 && i + 1 < n) {
                num[j][i + 1] += (num[j][i] - 1);
                ans += num[j][i] - 1;
                num[j][i] = 1;
                // dbg("MOVE", i, j, i + 1, j);
            }
        }
    }
    for (int j = 0; j < 2; j++)
    for (int i = 0; i < n; i++) {
        assert(num[j][i] == 1);
    }
    cout << ans << '\n';
}

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