Submission #1301006


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 (1) {
    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
Task A - Distance Pairs
User XraY
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4320 Byte
Status TLE
Exec Time 2103 ms
Memory 256 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
TLE × 2
TLE × 35
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 TLE 2103 ms 256 KB
01-02.txt TLE 2103 ms 256 KB
01-03.txt TLE 2103 ms 256 KB
01-04.txt TLE 2103 ms 256 KB
01-05.txt TLE 2103 ms 256 KB
01-06.txt TLE 2103 ms 256 KB
01-07.txt TLE 2103 ms 256 KB
01-08.txt TLE 2103 ms 256 KB
01-09.txt TLE 2103 ms 256 KB
01-10.txt TLE 2103 ms 256 KB
01-11.txt TLE 2103 ms 256 KB
01-12.txt TLE 2103 ms 256 KB
01-13.txt TLE 2103 ms 256 KB
01-14.txt TLE 2103 ms 256 KB
01-15.txt TLE 2103 ms 256 KB
01-16.txt TLE 2103 ms 256 KB
01-17.txt TLE 2103 ms 256 KB
01-18.txt TLE 2103 ms 256 KB
01-19.txt TLE 2103 ms 256 KB
01-20.txt TLE 2103 ms 256 KB
01-21.txt TLE 2103 ms 256 KB
01-22.txt TLE 2103 ms 256 KB
01-23.txt TLE 2103 ms 256 KB
01-24.txt TLE 2103 ms 256 KB
01-25.txt TLE 2103 ms 256 KB
01-26.txt TLE 2103 ms 256 KB
01-27.txt TLE 2103 ms 256 KB
01-28.txt TLE 2103 ms 256 KB
01-29.txt TLE 2103 ms 256 KB
01-30.txt TLE 2103 ms 256 KB
01-31.txt TLE 2103 ms 256 KB
sample-01.txt TLE 2103 ms 256 KB
sample-02.txt TLE 2103 ms 256 KB