Submission #209246

#	Time	Username	Problem	Language	Result	Execution time	Memory
209246		ffao	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	94 ms	7908 KiB

joi2019_ho_t4

#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <memory.h>
#include <cmath>
#include <array>

using namespace std;

void re(int& x);

template<class T, class... Ts> void re(T& t, Ts&... ts);

void pr(long long x);

void pr(const char *x);

void ps();
template<class T, class... Ts> void ps(const T& t, const Ts&... ts);

#ifdef FFDBG

#else
#define dbg(x...) dsfdsfsdfasd
#endif

void re(int& x) { scanf("%d", &x); }

template<class T, class... Ts> void re(T& t, Ts&... ts) { 
    re(t); re(ts...); 
}

void pr(long long x) { printf("%lld", x); }

void pr(const char *x) { printf("%s", x); }

void ps() { pr("\n"); }
template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { 
    pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); 
}

#define all(v) (v).begin(), (v).end()

#define rep(i, a, b) for(int i = a; i < (b); ++i)

int n;
int coins[100010][3];

vector< int > fr[2];
vector< int > b[2];

void solve()
{
    long long ans = 0;

    re(n);
    rep(i,0,2*n) {
        int x,y;
        re(x,y);
        if (x < 1) {
            ans += 1-x;
            x = 1;
        }
        if (x > n) {
            ans += x-n;
            x = n;
        }
        if (y < 1) {
            ans += 1-y;
            y = 1;
        }
        if (y > 2) {
            ans += y-2;
            y = 2;
        }

        x--; y--;
        //dbg(x,y);
        coins[x][y]++;
    }

    rep(x,0,n) rep(y,0,2) if (!coins[x][y]) fr[y].push_back(x);

    rep(i,0,2) sort(all(fr[i]),greater<int>());

    rep(x,0,n) {
        rep(y,0,2) if (!b[y].empty()) {
            if (coins[x][y] == 0) {
                ans += x - b[y].back();
                b[y].pop_back();
                fr[y].pop_back();
                coins[x][y]++;
            }
            
            if (coins[x][1-y] == 0 && !b[y].empty() && b[1-y].empty()) {
                ans += x - b[y].back() + 1;
                b[y].pop_back();
                fr[1-y].pop_back();
                coins[x][1-y]++;
            }
        }

        rep(y,0,2) {
            //dbg(x,y,coins[x][y]);
            while (coins[x][y] > 1) {
                if (!fr[y].empty() && fr[y].back() <= x) {
                    //dbg(x,y,"->",fr[y].back(),y);
                    ans += x - fr[y].back();
                    fr[y].pop_back();
                }
                else if (!fr[1-y].empty() && fr[1-y].back() <= x) {
                    if (coins[x][1-y] > 1) {
                        coins[x][1-y]--;
                        //dbg(x,y,"->",fr[1-y].back(),1-y);
                        ans += x - fr[1-y].back();
                        fr[1-y].pop_back();
                        continue;
                    }

                    ans += x - fr[1-y].back() + 1;
                    fr[1-y].pop_back();
                }
                else {
                    //dbg("go to b",x,y);
                    b[y].push_back(x);
                }

                coins[x][y]--;
            }
        }
    }

    //dbg(sz(b[0]), sz(b[1]));
    ps(ans);
}

int main() {

    solve();
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'void re(int&)':
joi2019_ho_t4.cpp:32:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void re(int& x) { scanf("%d", &x); }
                   ~~~~~^~~~~~~~~~

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