Submission #1301007
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);
void precalc() {
}
const int maxn = (int) 1e5 + 10;
int ds[2][maxn];
int n;
int read() {
if (scanf("%d", &n) < 1) {
return 0;
}
for (int i = 0; i < n; ++i) {
scanf("%d%d", &ds[0][i], &ds[1][i]);
}
return 1;
}
int res;
void solve() {
if (ds[0][0] || ds[1][1]) {
printf("-1\n");
return;
}
int d = ds[0][1];
if (ds[1][0] != d) {
printf("-1\n");
return;
}
vector<int> big(d + 1, 0);
vector<int> vs[2][d + 1];
for (int v = 0; v < n; ++v) {
int left = ds[0][v] + ds[1][v] - d;
if (left < 0 || abs(ds[0][v] - ds[1][v]) > d) {
printf("-1\n");
return;
}
if (left > 0) {
vs[left & 1][(ds[0][v] - ds[1][v] + d) / 2].pb((left + 1) / 2);
} else {
big[ds[0][v]] += 1;
}
}
res = 0;
for (int odd = 0; odd < 2; ++odd) {
vector<int> cool;
for (int i = 0; i <= d - odd; ++i) {
auto &cur = vs[odd][i];
sort(cur.begin(), cur.end());
int last = 0;
for (int i = 0; i < sz(cur);) {
int i0 = i;
while (i < sz(cur) && cur[i] == cur[i0]) {
++i;
}
//eprintf("%dx %d\n", i - i0, cur[i0]);
if (cur[i0] != last + 1) {
printf("-1\n");
return;
}
res += i - i0;
if (odd && cur[i0] == 1) {
cool.pb(i - i0);
}
++last;
}
if (sz(cool) == i) {
cool.pb(0);
}
}
if (odd) {
for (int i = 0; i < sz(cool); ++i) {
while (cool[i]) {
int j = i;
while (j < sz(cool) && cool[j]) {
--cool[j];
++j;
}
++res;
}
}
}
}
if (big[0] != 1 || big[d] != 1) {
printf("-1\n");
return;
}
for (int i = 1; i < d; ++i) {
if (big[i] == 0) {
printf("-1\n");
return;
}
}
for (int i = 0; i < d; ++i) {
res += max(big[i], big[i + 1]);
}
if (0) {
printf("%d\n", res);
}
}
void gen() {
vector<vector<int> > es;
vector<pair<int, int> > edges;
int m;
while (1) {
beg:;
n = rnd(20) + 2;
es = vector<vector<int> >(n);
edges.clear();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
edges.pb(mp(i, j));
}
}
random_shuffle(edges.begin(), edges.end(), rnd);
m = rnd(sz(edges) + 1);
edges.resize(m);
for (auto cur : edges) {
int i = cur.first, j = cur.second;
es[i].pb(j), es[j].pb(i);
}
for (int i = 0; i < 2; ++i) {
auto &dist = ds[i];
for (int v = 0; v < n; ++v) {
dist[v] = inf;
}
vector<int> st;
st.pb(i);
dist[i] = 0;
for (int l = 0; l < sz(st); ++l) {
int v = st[l];
for (int u : es[v]) {
if (dist[u] > dist[v] + 1) {
st.pb(u);
dist[u] = dist[v] + 1;
}
}
}
if (sz(st) < n) {
goto beg;
}
}
break;
}
solve();
if (res == -1 || res > m) {
eprintf("n = %d\n", n);
for (int i = 0; i < sz(edges); ++i) {
eprintf("%d %d\n", edges[i].first + 1, edges[i].second + 1);
}
eprintf("%d\n", n);
for (int i = 0; i < n; ++i) {
eprintf("%d %d\n", ds[0][i], ds[1][i]);
}
exit(1);
}
}
int main() {
precalc();
#ifdef LOCAL
freopen(TASK ".out", "w", stdout);
assert(freopen(TASK ".in", "r", stdin));
#endif
if (0) {
int cnt = 0;
while (1) {
if (++cnt % 1000 == 0) {
eprintf("Ok %d\n", cnt);
}
gen();
}
}
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-21 10:12:24+0900
Task
A - Distance Pairs
User
XraY
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
4320 Byte
Status
WA
Exec Time
25 ms
Memory
7024 KB
Compile Error
./Main.cpp: In function ‘int read()’:
./Main.cpp:45:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &ds[0][i], &ds[1][i]);
^
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
19 ms
5632 KB
01-02.txt
AC
14 ms
1024 KB
01-03.txt
WA
1 ms
256 KB
01-04.txt
WA
1 ms
256 KB
01-05.txt
WA
1 ms
256 KB
01-06.txt
WA
10 ms
1152 KB
01-07.txt
WA
16 ms
1536 KB
01-08.txt
WA
16 ms
1664 KB
01-09.txt
WA
15 ms
1536 KB
01-10.txt
WA
17 ms
1664 KB
01-11.txt
WA
19 ms
1536 KB
01-12.txt
WA
20 ms
1636 KB
01-13.txt
WA
24 ms
2044 KB
01-14.txt
WA
22 ms
7024 KB
01-15.txt
WA
24 ms
1660 KB
01-16.txt
WA
16 ms
1660 KB
01-17.txt
WA
14 ms
1024 KB
01-18.txt
WA
16 ms
1660 KB
01-19.txt
WA
23 ms
3328 KB
01-20.txt
WA
25 ms
3968 KB
01-21.txt
WA
25 ms
3968 KB
01-22.txt
WA
22 ms
2816 KB
01-23.txt
AC
16 ms
1664 KB
01-24.txt
AC
15 ms
1664 KB
01-25.txt
AC
14 ms
1024 KB
01-26.txt
AC
15 ms
1024 KB
01-27.txt
AC
15 ms
1536 KB
01-28.txt
AC
16 ms
1664 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
WA
1 ms
256 KB
sample-02.txt
AC
1 ms
256 KB