Submission #672721

#	Time	Username	Problem	Language	Result	Execution time	Memory
672721		ghostwriter	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	53 ms	6540 KiB

joi2019_ho_t4

// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
    #include <debug.h>
#else
    #define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
// #define int long long
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { T d2 = (a | b) & -(a | b); a /= d2; b /= d2; WHILE(b) { a = a % b; swap(a, b); } return a * d2; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
void _assert(bool statement) { if (statement) return; cerr << "\n>> Assertion failed!\n"; exit(0); }
void _assert(bool statement, const str &message) { if (statement) return; cerr << "\n>> Assertion failed: " << message << '\n'; exit(0); }
void _error(const str &message) { cerr << "\n>> Error: " << message << '\n'; exit(0); }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    GOAT
----------------------------------------------------------------
*/
const int N = 2e5 + 5;
int n;
pi a[N];
void input(int test_id) {
	cin >> n;
	FOR(i, 1, n << 1) cin >> a[i].st >> a[i].nd;
}
ll cost(const pi &a, const pi &b) { return 1LL * abs(a.st - b.st) + abs(a.nd - b.nd); }
namespace subtask12 {
    const ll oo = 1e18;
    const int N = 2005;
    ll d[N][N];
    void solve() {
        n <<= 1;
        sort(a + 1, a + 1 + n);
        FOS(i, n, 1)
        FOS(j, n >> 1, 0) {
            d[i][j] = oo;
            if (j < n / 2) d[i][j] = min(d[i][j], d[i + 1][j + 1] + cost(a[i], {j + 1, 1}));
            if (i - 1 - j < n / 2) d[i][j] = min(d[i][j], d[i + 1][j] + cost(a[i], {i - j, 2}));
        }
        cout << d[1][0];
    }
}
namespace subtask3 {
    /*
        Interesting problem :v. The main idea is to match every coin with a grid coordinate. We can transform every coin that lie outside the box
        to a coin that lie inside the box and create a new problem that is so much easier!

        I guess it isn't that easy >:(. Been thinking about this for almost a day, after transform every coin into the box, the next step is to think of
        a prefix sum algorithm (the very important idea). Suppose we have cnt1 coins is runing in row 1 (or spaces)
        and cnt2 coins is runing in row2 (or spaces), when we encounter
        a column i, if a coin meet a space, match it immediately (we can easily prove this with some cases). After that, if cnt1 and cnt2 have difference
        sign (we can match them from top to bottom), we match it immediately (and still, we can easily prove this with some other cases).
    */
    int d[N][3];
    void solve() {
        ll rs = 0;
        FOR(i, 1, n << 1) {
            if (a[i].st < 1) {
                rs += 1 - a[i].st;
                a[i].st = 1;
            }
            if (a[i].st > n) {
                rs += a[i].st - n;
                a[i].st = n;
            }
            if (a[i].nd < 1) {
                rs += 1 - a[i].nd;
                a[i].nd = 1;
            }
            if (a[i].nd > 2) {
                rs += a[i].nd - 2;
                a[i].nd = 2;
            }
            ++d[a[i].st][a[i].nd];
        }
        int cnt1 = 0, cnt2 = 0;
        FOR(i, 1, n) {
            cnt1 += d[i][1] - 1;
            cnt2 += d[i][2] - 1;
            WHILE(cnt1 < 0 && cnt2 > 0) {
                ++cnt1;
                --cnt2;
                ++rs;
            }
            WHILE(cnt1 > 0 && cnt2 < 0) {
                --cnt1;
                ++cnt2;
                ++rs;
            }
            rs += abs(cnt1) + abs(cnt2);
        }
        cout << rs;
    }
}
void solve(int test_id) {
    // if (n <= 1000) {
    //     subtask12::solve();
    //     return;
    // }
    subtask3::solve();
}
void reinit(int test_id) {

}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    int test_num = 1;
    // cin >> test_num; // comment if the problem does not requires multitest
    FOR(i, 1, test_num) {
        input(i); // input in noninteractive problems for case #i
        solve(i); // main function to solve case #i
        reinit(i); // reinit global data to default used in case #i
    }
    #ifdef LOCAL
        cerr << "\nTime: " << setprecision(5) << fixed << (ldb)clock() / CLOCKS_PER_SEC << "ms.\n";
    #endif
    return 0;
}
/*
----------------------------------------------------------------
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/

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