QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#512046#9177. String and Nailsucup-team055#WA 235ms47268kbC++2312.0kb2024-08-10 13:21:582024-08-10 13:21:59

Judging History

你现在查看的是最新测评结果

  • [2024-08-10 13:21:59]
  • 评测
  • 测评结果:WA
  • 用时:235ms
  • 内存:47268kb
  • [2024-08-10 13:21:58]
  • 提交

answer

// https://judge.yosupo.jp/submission/210846
#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << p.first << " " << p.second;
  return os;
}

template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
  is >> p.first >> p.second;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &in : v) is >> in;
  return is;
}

template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
  return a < b && (a = b, true);
}

template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  return a > b && (a = b, true);
}

template<typename T = int64>
vector<T> make_v(size_t a) {
  return vector<T>(a);
}

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) {
  t = v;
}

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) {
  for (auto &e : t) fill_v(e, v);
}

template<typename F>
struct FixPoint : F {
  explicit FixPoint(F &&f) : F(forward<F>(f)) {}

  template<typename... Args>
  decltype(auto) operator()(Args &&...args) const {
    return F::operator()(*this, forward<Args>(args)...);
  }
};

template<typename F>
inline decltype(auto) MFP(F &&f) {
  return FixPoint<F>{forward<F>(f)};
}

template<typename T, typename T2>
struct DecrementalUpperHull {
 private:
  using Point = pair<T, T>;

  static constexpr T2 cross(const Point &a, const Point &b) {
    return T2(a.first) * b.second - T2(a.second) * b.first;
  }

  static constexpr int ccw(const Point &a, const Point &b) {
    T2 x = cross(a, b);
    return (x > 0) - (x < 0);
  }

  static constexpr Point sub(const Point &a, const Point &b) {
    return {a.first - b.first, a.second - b.second};
  }

  static constexpr int ccw(Point const &a, Point const &b, Point const &c) {
    return ccw(sub(b, a), sub(c, a));
  }

  struct Link {
    Point p;
    Link *prev, *next;
    int id;
  };
  using LP = Link *;

  struct Node {
    LP chain, chain_back, tangent;
    int lch, rch;
  };

  size_t n, sz;
  vector<bool> alive;
  vector<Node> seg;
  vector<Link> links;

  pair<LP, LP> find_bridge(LP l, LP r) {
    while (l->next or r->next) {
      if (not r->next or (l->next and ccw(sub(l->next->p, l->p), sub(r->next->p, r->p)) <= 0)) {
        if (ccw(l->p, l->next->p, r->p) <= 0) {
          l = l->next;
        } else {
          break;
        }
      } else {
        if (ccw(l->p, r->p, r->next->p) > 0) {
          r = r->next;
        } else {
          break;
        }
      }
    }
    return {l, r};
  }

  pair<LP, LP> find_bridge_rev(LP l, LP r) {
    while (r->prev or l->prev) {
      if (not l->prev or (r->prev and ccw(sub(r->prev->p, r->p), sub(l->prev->p, l->p)) >= 0)) {
        if (ccw(r->p, r->prev->p, l->p) >= 0) {
          r = r->prev;
        } else {
          break;
        }
      } else {
        if (ccw(r->p, l->p, l->prev->p) < 0) {
          l = l->prev;
        } else {
          break;
        }
      }
    }
    return {r, l};
  }

  template<bool rev>
  void fix_chain(int u, LP l, LP r) {
    if (rev) tie(r, l) = find_bridge_rev(l, r);
    else tie(l, r) = find_bridge(l, r);

    Node &l_node = seg[seg[u].lch];
    Node &r_node = seg[seg[u].rch];

    seg[u].tangent = l;
    seg[u].chain = l_node.chain;
    seg[u].chain_back = r_node.chain_back;
    l_node.chain = l->next;
    r_node.chain_back = r->prev;

    if (l->next) l->next->prev = nullptr;
    else l_node.chain_back = nullptr;
    if (r->prev) r->prev->next = nullptr;
    else r_node.chain = nullptr;

    l->next = r;
    r->prev = l;
  }

  void rob(int u, int v) {
    seg[u].chain = seg[v].chain;
    seg[v].chain = nullptr;
    seg[u].chain_back = seg[v].chain_back;
    seg[v].chain_back = nullptr;
  }

  void erase(int u, int a, int b, int i) {
    if (i < a or i >= b or u == -1) return;
    int m = (a + b) / 2;
    int v = i < m ? seg[u].lch : seg[u].rch;
    if (!seg[u].tangent) {
      seg[v].chain = seg[u].chain;
      seg[v].chain_back = seg[u].chain_back;
      if (i < m) erase(v, a, m, i);
      else erase(v, m, b, i);
      rob(u, v);
      return;
    }

    auto l = seg[u].tangent, r = l->next;
    Node &l_node = seg[seg[u].lch];
    Node &r_node = seg[seg[u].rch];

    l->next = l_node.chain;
    if (l_node.chain) l_node.chain->prev = l;
    else l_node.chain_back = l;
    l_node.chain = seg[u].chain;

    r->prev = r_node.chain_back;
    if (r_node.chain_back) r_node.chain_back->next = r;
    else r_node.chain = r;
    r_node.chain_back = seg[u].chain_back;

    if (seg[v].chain == seg[v].chain_back and seg[v].chain->id == i) {
      seg[v].chain = seg[v].chain_back = nullptr;
      rob(u, i < m ? seg[u].rch : seg[u].lch);
      seg[u].tangent = nullptr;
    } else if (i < m) {
      if (l->id == i) l = l->next;
      erase(v, a, m, i);
      if (not l) l = l_node.chain_back;
      fix_chain<true>(u, l, r);
    } else {
      if (r->id == i) r = r->prev;
      erase(v, m, b, i);
      if (not r) r = r_node.chain;
      fix_chain<false>(u, l, r);
    }
  }

  size_t build(size_t &k, int l, int r) {
    if (r - l == 1) return l + n;
    int m = (l + r) / 2;
    size_t res = k++;
    seg[res].lch = build(k, l, m);
    seg[res].rch = build(k, m, r);
    fix_chain<false>(res, seg[seg[res].lch].chain, seg[seg[res].rch].chain);
    return res;
  }

 public:
  explicit DecrementalUpperHull(const vector<Point> &ps) : n(ps.size()), seg(2 * n), sz(n), alive(n) {
    assert(is_sorted(ps.begin(), ps.end()));
    links.reserve(n);
    for (int k = 0; k < n; ++k) {
        links.push_back({ps[k], nullptr, nullptr, k});
    }
    for (int k = 0; k < n; k++) {
      seg[k + n] = {&links[k], &links[k], nullptr, -1, -1};
    }
    if (ps.size() == 1) seg[0] = seg[1];
    size_t u = 0;
    build(u, 0, n);
  }

  size_t size() const {
    return sz;
  }

  bool empty() const {
    return sz == 0;
  }

  bool erase(int k) {
    assert(0 <= k and k < n);
    if (alive[k]) return false;
    alive[k] = true;
    --sz;
    if (seg[0].chain == seg[0].chain_back) {
      seg[0].chain = seg[0].chain_back = nullptr;
    } else {
      erase(0, 0, n, k);
    }
    return true;
  }

  vector<int> get_hull() const {
    vector<int> ret;
    for (LP u = seg[0].chain; u; u = u->next) {
      ret.push_back(u->id);
    }
    return ret;
  }
};

template<typename T, typename T2>
vector<int> convex_layers(const vector<pair<T, T> > &ps) {
  int n = (int) ps.size();
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int a, int b) {
    return ps[a] < ps[b];
  });
  vector<pair<T, T> > us(n);
  for (int i = 0; i < n; i++) {
    us[i] = ps[ord[i]];
  }
  DecrementalUpperHull<T, T2> upper_hull(us);
  vector<pair<T, T> > ds(n);
  for (int i = 0; i < n; i++) {
    ds[i] = {-us[n - i - 1].first, -us[n - i - 1].second};
  }
  DecrementalUpperHull<T, T2> lower_hull(ds);
  vector<int> convex_hull, res(n, -1);
  convex_hull.reserve(n);
  for (int layer = 1; not upper_hull.empty(); layer++) {
    for (auto &p : upper_hull.get_hull()) {
      res[ord[p]] = layer;
      convex_hull.push_back(p);
    }
    for (auto &p : lower_hull.get_hull()) {
      p = n - p - 1;
      if (res[ord[p]] == -1) {
        res[ord[p]] = layer;
        convex_hull.push_back(p);
      }
    }
    for (auto &p : convex_hull) {
      upper_hull.erase(p);
      lower_hull.erase(n - p - 1);
    }
    convex_hull.clear();
  }
  return res;
}

#line 1 "other/scanner.hpp"
/**
 * @brief Scanner(高速入力)
 */
struct Scanner {
 public:
  explicit Scanner(FILE *fp) : fp(fp) {}

  template <typename T, typename... E>
  void read(T &t, E &...e) {
    read_single(t);
    read(e...);
  }

 private:
  static constexpr size_t line_size = 1 << 16;
  static constexpr size_t int_digits = 20;
  char line[line_size + 1] = {};
  FILE *fp = nullptr;
  char *st = line;
  char *ed = line;

  void read() {}

  static inline bool is_space(char c) { return c <= ' '; }

  void reread() {
    ptrdiff_t len = ed - st;
    memmove(line, st, len);
    char *tmp = line + len;
    ed = tmp + fread(tmp, 1, line_size - len, fp);
    *ed = 0;
    st = line;
  }

  void skip_space() {
    while (true) {
      if (st == ed) reread();
      while (*st && is_space(*st)) ++st;
      if (st != ed) return;
    }
  }

  template <typename T, enable_if_t<is_integral<T>::value, int> = 0>
  void read_single(T &s) {
    skip_space();
    if (st + int_digits >= ed) reread();
    bool neg = false;
    if (is_signed<T>::value && *st == '-') {
      neg = true;
      ++st;
    }
    typename make_unsigned<T>::type y = *st++ - '0';
    while (*st >= '0') {
      y = 10 * y + *st++ - '0';
    }
    s = (neg ? -y : y);
  }

  template <typename T, enable_if_t<is_same<T, string>::value, int> = 0>
  void read_single(T &s) {
    s = "";
    skip_space();
    while (true) {
      char *base = st;
      while (*st && !is_space(*st)) ++st;
      s += string(base, st);
      if (st != ed) return;
      reread();
    }
  }

  template <typename T>
  void read_single(vector<T> &s) {
    for (auto &d : s) read(d);
  }
};
#line 1 "other/printer.hpp"
/**
 * @brief Printer(高速出力)
 */
struct Printer {
 public:
  explicit Printer(FILE *fp) : fp(fp) {}

  ~Printer() { flush(); }

  template <bool f = false, typename T, typename... E>
  void write(const T &t, const E &...e) {
    if (f) write_single(' ');
    write_single(t);
    write<true>(e...);
  }

  template <typename... T>
  void writeln(const T &...t) {
    write(t...);
    write_single('\n');
  }

  void flush() {
    fwrite(line, 1, st - line, fp);
    st = line;
  }

 private:
  FILE *fp = nullptr;
  static constexpr size_t line_size = 1 << 16;
  static constexpr size_t int_digits = 20;
  char line[line_size + 1] = {};
  char *st = line;

  template <bool f = false>
  void write() {}

  void write_single(const char &t) {
    if (st + 1 >= line + line_size) flush();
    *st++ = t;
  }

  template <typename T, enable_if_t<is_integral<T>::value, int> = 0>
  void write_single(T s) {
    if (st + int_digits >= line + line_size) flush();
    st += to_chars(st, st + int_digits, s).ptr - st;
  }

  void write_single(const string &s) {
    for (auto &c : s) write_single(c);
  }

  void write_single(const char *s) {
    while (*s != 0) write_single(*s++);
  }

  template <typename T>
  void write_single(const vector<T> &s) {
    for (size_t i = 0; i < s.size(); i++) {
      if (i) write_single(' ');
      write_single(s[i]);
    }
  }
};


int main() {
  Scanner in(stdin);
  Printer out(stdout);
  int n;
  in.read(n);
  vector<pair<int, int>> ps(n);
  for (int i = 0; i < n; i++) {
    int x, y;
    in.read(x, y);
    ps[i] = {x, y};
  }
  auto A = convex_layers<int, int64>(ps);
    vector<int> ans(n);
    for(int i = 0; i < n; i++) ans[i] = i;
    ranges::sort(ans, {}, [&](int i) { return A[i]; });
    cout << "YES" << endl;
    
    ans.pop_back();
    for(int i : ans) {
        auto [x, y] = ps[i];
        cout << x << ' ' << y << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4036kb

input:

3
1 1
2 4
3 1

output:

YES
1 1
2 4

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

1
1000000000 0

output:

YES

result:

ok Everything ok

Test #3:

score: -100
Wrong Answer
time: 235ms
memory: 47268kb

input:

200000
500000000 500000000
500244009 499720246
500488018 499440492
500732027 499160738
500976036 498880984
501220045 498601230
501464054 498321476
501708063 498041722
501952072 497761968
502196081 497482214
502440090 497202460
502684099 496922706
502928108 496642952
503172117 496363198
503416126 496...

output:

YES
652346525 534856293
653465541 535832329
604907750 591503375
653185787 535588320
604627996 591259366
652906033 535344311
604348242 591015357
652626279 535100302
604068488 590771348
605187504 591747384
603788734 590527339
652066771 534612284
603508980 590283330
651787017 534368275
603229226 590039...

result:

wrong answer Wrong answer