Submission #330899

# Submission time Handle Problem Language Result Execution time Memory
330899 2020-11-26T20:57:41 Z caoash Coin Collecting (JOI19_ho_t4) C++17
0 / 100
1 ms 364 KB
/*
 * 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
 *   - 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);
        if (go >= n) ans += go - n + 1;
        go = max(go, 0LL);
        go = min(go, (ll) 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]++;
                    ans += abs(i - need);
                }
                ++need;
            }
            need = pt[j ^ 1];
            while (need < i && num[j][i] > 1) {
                if (num[j ^ 1][need] == 0) {
                    num[j][i]--;
                    num[j ^ 1][need]++;
                    ans += 1 + abs(i - need);
                }
                ++need;
            }
            if (num[j][i] > 1 && i + 1 < n) {
                num[j][i + 1] += (num[j][i] - 1);
                num[j][i] = 1;
                ++ans;
            }
        }
    }
    for (int i = 0; i < 2; i++) {
        if (num[i][n - 1] == 0) {
            ++ans;
            num[i][n - 1]++;
            num[i ^ 1][n - 1]--;
        }
    }
    cout << ans << '\n';
}

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -