QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#512046 | #9177. String and Nails | ucup-team055# | WA | 235ms | 47268kb | C++23 | 12.0kb | 2024-08-10 13:21:58 | 2024-08-10 13:21:59 |
Judging History
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