CODE FESTIVAL 2016 Exhibition

Submission #1301006

Source codeソースコード

#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

Task問題 A - Distance Pairs
User nameユーザ名 -XraY-
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 TLE
Score得点 0
Source lengthソースコード長 4320 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./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]);
^

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
All 0 / 1500 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt TLE
01-02.txt TLE
01-03.txt TLE
01-04.txt TLE
01-05.txt TLE
01-06.txt TLE
01-07.txt TLE
01-08.txt TLE
01-09.txt TLE
01-10.txt TLE
01-11.txt TLE
01-12.txt TLE
01-13.txt TLE
01-14.txt TLE
01-15.txt TLE
01-16.txt TLE
01-17.txt TLE
01-18.txt TLE
01-19.txt TLE
01-20.txt TLE
01-21.txt TLE
01-22.txt TLE
01-23.txt TLE
01-24.txt TLE
01-25.txt TLE
01-26.txt TLE
01-27.txt TLE
01-28.txt TLE
01-29.txt TLE
01-30.txt TLE
01-31.txt TLE
sample-01.txt TLE
sample-02.txt TLE