Submission #51301

#	Time	Username	Problem	Language	Result	Execution time	Memory
51301		mareksom	Park (BOI16_park)	C++17	100 / 100	399 ms	33572 KiB

park

#ifndef LOCAL
#pragma GCC optimize ("O3")
#endif

#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return {i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (c it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(x...) " [" #x ": " << (x) << "] "

using ld = long double;
using ll = long long;

constexpr int mod = 1000 * 1000 * 1000 + 7;
constexpr int odw2 = (mod + 1) / 2;

void OdejmijOd(int& a, int b) { a -= b; if (a < 0) a += mod; }
int Odejmij(int a, int b) { OdejmijOd(a, b); return a; }
void DodajDo(int& a, int b) { a += b; if (a >= mod) a -= mod; }
int Dodaj(int a, int b) { DodajDo(a, b); return a; }
int Mnoz(int a, int b) { return (ll) a * b % mod; }
void MnozDo(int& a, int b) { a = Mnoz(a, b); }
int Pot(int a, int b) { int res = 1; while (b) { if (b % 2 == 1) MnozDo(res, a); a = Mnoz(a, a); b /= 2; } return res; }
int Odw(int a) { return Pot(a, mod - 2); }
void PodzielDo(int& a, int b) { MnozDo(a, Odw(b)); }
int Podziel(int a, int b) { return Mnoz(a, Odw(b)); }
int Moduluj(ll x) { x %= mod; if (x < 0) x += mod; return x; }

template <typename T> T Maxi(T& a, T b) { return a = max(a, b); }
template <typename T> T Mini(T& a, T b) { return a = min(a, b); }

//#define int long long

constexpr int nax = 2000 + 105;

ll Kwa(ll x) {
  return x * x;
}

int SufPier(ll x) {
  assert(x >= 0);
  int res = (int) sqrt(x) + 1;
  while ((ll) res * res > x) res--;
  return res;
}

int n, m, N;
int W, H;

tuple<int, int, int> drzewo[nax];

int fut[nax];

int fuf(int w) {
  if (fut[w] == w) return w;
  return fut[w] = fuf(fut[w]);
}

void fuu(int u, int v) {
  fut[fuf(u)] = fuf(v);
}

vector<pair<int, pair<int, int>>> kraw;

void UstawGraf(int a, int b, int odl) {
  kraw.emplace_back(odl, make_pair(a, b));
}

vector<pair<int, int>> graf[nax];

int Odl(int u, int v) {
  auto Polaczone = [u, v](int threshold) -> bool {
    for (int i = 0; i < N; i++) {
      fut[i] = i;
    }
    for (int i = 0; i < N; i++) {
      for (auto& it : graf[i]) {
        if (it.first <= threshold) {
          fuu(i, it.second);
        }
      }
    }
    return fuf(u) == fuf(v);
  };
  int a = numeric_limits<int>::min();
  int b = numeric_limits<int>::max();
  while (a < b) {
    const int c = (((ll) a + b) >> 1);
    //debug() << imie(a) imie(b) imie(c);
    if (Polaczone(c)) {
      b = c;
    } else {
      a = c + 1;
    }
  }
  assert(Polaczone(a));
  return a;
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> W >> H;
  N = n + 4;
  for (int i = 0; i < n; i++) {
    int x, y, r;
    cin >> x >> y >> r;
    drzewo[i] = make_tuple(x, y, r);
    UstawGraf(i, n + 0, y - r);
    UstawGraf(i, n + 1, W - x - r);
    UstawGraf(i, n + 2, H - y - r);
    UstawGraf(i, n + 3, x - r);
    for (int j = 0; j < i; j++) {
      const int x1 = get<0>(drzewo[j]);
      const int y1 = get<1>(drzewo[j]);
      const int r1 = get<2>(drzewo[j]);
      UstawGraf(i, j, SufPier(Kwa(x - x1) + Kwa(y - y1)) - r - r1);
    }
  }

  sort(kraw.begin(), kraw.end());
  for (int i = 0; i < N; i++) fut[i] = i;

  for (auto& it : kraw) {
    const int o = it.first;
    const int a = it.second.first;
    const int b = it.second.second;
    if (fuf(a) != fuf(b)) {
      graf[a].emplace_back(o, b);
      graf[b].emplace_back(o, a);
      fuu(a, b);
      debug() << imie(a) imie(b) imie(o);
    }
  }

  int odl[4][4];
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      odl[i][j] = Odl(n + i, n + j);
      if (i < j) {
        debug() << "odl[" << i << "][" << j << "] = " << odl[i][j];
      }
    }
  }

  while (m--) {
    int r, e;
    cin >> r >> e;
    r *= 2;
    e--;

    auto Pol = [&](int a, int b) -> bool {
      return odl[(a + e) % 4][(b + e) % 4] < r;
    };

    bool zak[4] = {false, false, false, false};
    zak[0] = false;
    zak[1] = Pol(0, 1) or Pol(0, 2) or Pol(0, 3);
    zak[2] = Pol(0, 2) or Pol(0, 3) or Pol(1, 2) or Pol(1, 3);
    zak[3] = Pol(3, 0) or Pol(3, 1) or Pol(3, 2);

    for (int i = 0; i < 4; i++) {
      if (!zak[(i - e + 4) % 4]) {
        cout << i + 1;
      }
    }
    cout << '\n';
  }
  return 0;
}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42