Submission #995840


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);
typedef pair<int, int> pii;

map<pii, int> a;

void ass(bool ex) {
    if (!ex) {
        cout << -1 << '\n';
        exit(0);
    }
}

pii operator+(pii a, pii b) {
    return pii{a.first + b.first, a.second + b.second};
}

pii operator-(pii a, pii b) {
    return pii{a.first - b.first, a.second - b.second};
}

pii nx(pii a) {
    return a + pii{1, -1};
}

int main() {
    #ifdef LOCAL
    assert(freopen("a.in", "r", stdin));
    #else
    #endif
    int n;
    cin >> n;
    int d;
    forn (i, n) {
        int x, y;
        cin >> x >> y;
        if (i == 0) {
            ass(x == 0);
            d = y;
        }
        if (i == 1)
            ass(y == 0 && d == x);
        ass(x + y >= d);
        ass(x >= 0 && y >= 0);
        if (i != 0)
            ass(x != 0);
        if (i != 1)
            ass(y != 0);
        a[pii(x, y)]++;
    }
    for (auto p: a) {
        auto c = p.first;
        if (c.second != 0)
            ass(a.count(c + pii(0, -1)) || a.count(c + pii(-1, -1)) || a.count(c + pii(1, -1)));
        if (c.first != 0)
            ass(a.count(c + pii(-1, 0)) || a.count(c + pii(-1, -1)) || a.count(c + pii(-1, 1)));
    }
    //cerr << "YES\n";
    vector<pair<pii, int>> v;
    for (auto A: a)
        v.push_back(A);
    sort(v.begin(), v.end(), [](pair<pii, int> a, pair<pii, int> b) {
                int sa = a.first.first + a.first.second;
                int sb = b.first.first + b.first.second;
                if (sa != sb)
                    return sa < sb;
                return a.first < b.first;
            });
    int res = 2 * n - 2;

    int carry = 0;
    forn (ii, sz(v)) {
        auto c = v[ii].first;
        int cnt = v[ii].second;
        carry = min(carry, cnt);
        if (a.count(c + pii{-1, -1})) {
            int k = cnt - carry;
            res -= k;
            cnt -= k;
        }
        res -= carry;
        if (ii + 1 < sz(v) && v[ii + 1].first == nx(c))
            carry = cnt;
        else
            carry = 0;
    }
    cout << res << '\n';
}

Submission Info

Submission Time
Task A - Distance Pairs
User zemen
Language C++14 (GCC 5.4.1)
Score 1500
Code Size 2390 Byte
Status AC
Exec Time 145 ms
Memory 8184 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 1500 / 1500
Status
AC × 2
AC × 33
Set Name Test Cases
sample sample-01.txt, sample-02.txt
All sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt
Case Name Status Exec Time Memory
01-01.txt AC 2 ms 256 KB
01-02.txt AC 2 ms 256 KB
01-03.txt AC 2 ms 256 KB
01-04.txt AC 2 ms 256 KB
01-05.txt AC 3 ms 256 KB
01-06.txt AC 21 ms 256 KB
01-07.txt AC 54 ms 640 KB
01-08.txt AC 52 ms 768 KB
01-09.txt AC 44 ms 384 KB
01-10.txt AC 37 ms 256 KB
01-11.txt AC 50 ms 512 KB
01-12.txt AC 50 ms 384 KB
01-13.txt AC 145 ms 8184 KB
01-14.txt AC 143 ms 8184 KB
01-15.txt AC 135 ms 8184 KB
01-16.txt AC 32 ms 256 KB
01-17.txt AC 32 ms 256 KB
01-18.txt AC 33 ms 256 KB
01-19.txt AC 145 ms 8184 KB
01-20.txt AC 129 ms 6904 KB
01-21.txt AC 132 ms 7032 KB
01-22.txt AC 97 ms 3836 KB
01-23.txt AC 51 ms 512 KB
01-24.txt AC 50 ms 512 KB
01-25.txt AC 2 ms 256 KB
01-26.txt AC 2 ms 256 KB
01-27.txt AC 30 ms 512 KB
01-28.txt AC 25 ms 512 KB
01-29.txt AC 2 ms 256 KB
01-30.txt AC 2 ms 256 KB
01-31.txt AC 2 ms 256 KB
sample-01.txt AC 2 ms 256 KB
sample-02.txt AC 2 ms 256 KB