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 |
|
|
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 |