oj.uz

Submission #209239

# Submission time Handle Problem Language Result Execution time Memory
209239 2020-03-13T13:10:21 Z ffao Coin Collecting (JOI19_ho_t4) C++14
0 / 100
 5 ms 256 KB 
#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]));

    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) {
            while (coins[x][y] > 1) {
                if (!fr[y].empty() && fr[y].back() <= x) {
                    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]--;
                        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 b[y].push_back(x);

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

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

int main() {

    solve();
}

Compilation message

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
0 / 8.0

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

Subtask #2
0 / 29.0

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

Subtask #3
0 / 63.0

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