Submission #1302182
Source Code Expand
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{} ());
int rnd(int x) {
return mrand() % x;
}
typedef long double ld;
typedef long long ll;
#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif
#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"
const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);
const int mod = (int) 1e9 + 7;
void add(int &x, int y) {
if ((x += y) >= mod) {
x -= mod;
}
}
int mult(int x, int y) {
return (long long) x * y % mod;
}
int power(int x, int pw) {
int res = 1;
for (; pw; pw >>= 1) {
if (pw & 1) {
res = mult(res, x);
}
x = mult(x, x);
}
return res;
}
void precalc() {
}
const int maxn = (int) 1e5 + 10;
pair<int, int> tosort[maxn];
int n;
int read() {
if (scanf("%d", &n) < 1) {
return 0;
}
for (int i = 0; i < n; ++i) {
int x, y;
scanf("%d%d", &x, &y);
tosort[i] = mp(x, y);
}
return 1;
}
void solve() {
if (tosort[0].first || tosort[1].second) {
printf("-1\n");
return;
}
map<pair<int, int>, int> cnt;
for (int i = 0; i < n; ++i) {
int x = tosort[i].first;
int y = tosort[i].second;
if (i != 0 && !x) {
printf("-1\n");
return;
}
if (i != 1 && !y) {
printf("-1\n");
return;
}
cnt[{x, y}] += 1;
tosort[i] = {x + y, x};
}
sort(tosort, tosort + n);
int res = 2 * n - 2;
for (int i = 0; i < n;) {
int i0 = i;
while (i < n && tosort[i].first == tosort[i0].first) {
int x = tosort[i].first, y = tosort[i].second;
x -= y;
for (int iter = 0; iter < 2; ++iter) {
auto &cur = (!iter ? x : y);
if (!cur) {
continue;
}
auto &cury = (iter ? x : y);
--cur;
bool ok = 0;
for (int dx = -1; dx <= 1; ++dx) {
cury += dx;
if (cnt.count({x, y})) {
ok = 1;
}
cury -= dx;
}
++cur;
if (!ok) {
printf("-1\n");
return;
}
}
++i;
}
int last = 0, left = 0;
for (int j = i0; j < i;) {
int j0 = j;
while (j < i && tosort[j].second == tosort[j0].second) {
++j;
}
int now = j - j0;
int del = 0;
if (last + 1 == tosort[j0].second) {
del = min(now, left);
res -= del;
}
if (cnt.count({tosort[j0].first - tosort[j0].second - 1, tosort[j0].second - 1})) {
res -= now - del;
now = del;
}
left = now;
last = tosort[j0].second;
}
}
printf("%d\n", res);
}
int main() {
precalc();
#ifdef LOCAL
freopen(TASK ".out", "w", stdout);
assert(freopen(TASK ".in", "r", stdin));
#endif
while (1) {
if (!read()) {
break;
}
solve();
#ifdef DEBUG
eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
}
return 0;
}
Submission Info
Submission Time
2017-05-22 06:35:28+0900
Task
A - Distance Pairs
User
XraY
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
3217 Byte
Status
WA
Exec Time
103 ms
Memory
7424 KB
Compile Error
./Main.cpp: In function ‘int read()’:
./Main.cpp:71:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
^
Judge Result
Set Name
sample
All
Score / Max Score
0 / 0
0 / 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, sample-01.txt, sample-02.txt
Case Name
Status
Exec Time
Memory
01-01.txt
AC
57 ms
7424 KB
01-02.txt
AC
24 ms
1024 KB
01-03.txt
AC
1 ms
256 KB
01-04.txt
AC
1 ms
256 KB
01-05.txt
WA
1 ms
256 KB
01-06.txt
WA
12 ms
768 KB
01-07.txt
WA
32 ms
1280 KB
01-08.txt
WA
32 ms
1408 KB
01-09.txt
WA
26 ms
1152 KB
01-10.txt
WA
21 ms
1024 KB
01-11.txt
WA
29 ms
1152 KB
01-12.txt
WA
28 ms
1152 KB
01-13.txt
WA
102 ms
7296 KB
01-14.txt
AC
98 ms
7296 KB
01-15.txt
WA
55 ms
7296 KB
01-16.txt
AC
22 ms
1024 KB
01-17.txt
AC
21 ms
1024 KB
01-18.txt
AC
21 ms
1024 KB
01-19.txt
AC
103 ms
7296 KB
01-20.txt
WA
101 ms
6144 KB
01-21.txt
WA
103 ms
6144 KB
01-22.txt
WA
78 ms
3712 KB
01-23.txt
AC
32 ms
1408 KB
01-24.txt
AC
31 ms
1408 KB
01-25.txt
AC
14 ms
1024 KB
01-26.txt
AC
15 ms
1024 KB
01-27.txt
AC
20 ms
1280 KB
01-28.txt
AC
19 ms
1280 KB
01-29.txt
AC
1 ms
256 KB
01-30.txt
AC
1 ms
256 KB
01-31.txt
AC
1 ms
256 KB
sample-01.txt
AC
1 ms
256 KB
sample-02.txt
AC
1 ms
256 KB