QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#74286 | #5443. Security at Museums | japan022022 | AC ✓ | 554ms | 5708kb | C++20 | 31.5kb | 2023-01-31 14:08:57 | 2023-01-31 14:08:58 |
Judging History
answer
#line 1 "library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vv(type, name, h, ...) \
vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) \
vector<vector<vector<type>>> name( \
h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name( \
a, vector<vector<vector<type>>>( \
b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_subset(t, s) \
for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define stoi stoll
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template <typename T, typename U>
T ceil(T x, U y) {
return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U>
T floor(T x, U y) {
return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T, typename U>
pair<T, T> divmod(T x, U y) {
T q = floor(x, y);
return {q, x - q * y};
}
template <typename T, typename U>
T SUM(const vector<U> &A) {
T sum = 0;
for (auto &&a: A) sum += a;
return sum;
}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) \
sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
template <typename T>
T POP(deque<T> &que) {
T a = que.front();
que.pop_front();
return a;
}
template <typename T>
T POP(pq<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(pqg<T> &que) {
assert(!que.empty());
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(vc<T> &que) {
assert(!que.empty());
T a = que.back();
que.pop_back();
return a;
}
template <typename F>
ll binary_search(F check, ll ok, ll ng) {
assert(check(ok));
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
}
return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
FOR(iter) {
double x = (ok + ng) / 2;
tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
}
return (ok + ng) / 2;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
vc<int> A(S.size());
FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
return A;
}
template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
int N = A.size();
vector<T> B(N + 1);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
if (off == 0) B.erase(B.begin());
return B;
}
// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
vector<int> ids(len(A));
iota(all(ids), 0);
sort(all(ids),
[&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
return ids;
}
// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
vc<T> B(len(I));
FOR(i, len(I)) B[i] = A[I[i]];
return B;
}
#endif
#line 1 "library/other/io.hpp"
// based on yosupo's fastio
#include <unistd.h>
namespace fastio {
#define FASTIO
// クラスが read(), print() を持っているかを判定するメタ関数
struct has_write_impl {
template <class T>
static auto check(T &&x) -> decltype(x.write(), std::true_type{});
template <class T>
static auto check(...) -> std::false_type;
};
template <class T>
class has_write : public decltype(has_write_impl::check<T>(std::declval<T>())) {
};
struct has_read_impl {
template <class T>
static auto check(T &&x) -> decltype(x.read(), std::true_type{});
template <class T>
static auto check(...) -> std::false_type;
};
template <class T>
class has_read : public decltype(has_read_impl::check<T>(std::declval<T>())) {};
struct Scanner {
FILE *fp;
char line[(1 << 15) + 1];
size_t st = 0, ed = 0;
void reread() {
memmove(line, line + st, ed - st);
ed -= st;
st = 0;
ed += fread(line + ed, 1, (1 << 15) - ed, fp);
line[ed] = '\0';
}
bool succ() {
while (true) {
if (st == ed) {
reread();
if (st == ed) return false;
}
while (st != ed && isspace(line[st])) st++;
if (st != ed) break;
}
if (ed - st <= 50) {
bool sep = false;
for (size_t i = st; i < ed; i++) {
if (isspace(line[i])) {
sep = true;
break;
}
}
if (!sep) reread();
}
return true;
}
template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
bool read_single(T &ref) {
if (!succ()) return false;
while (true) {
size_t sz = 0;
while (st + sz < ed && !isspace(line[st + sz])) sz++;
ref.append(line + st, sz);
st += sz;
if (!sz || st != ed) break;
reread();
}
return true;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
bool read_single(T &ref) {
if (!succ()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
ref = T(0);
while (isdigit(line[st])) { ref = 10 * ref + (line[st++] & 0xf); }
if (neg) ref = -ref;
return true;
}
template <typename T,
typename enable_if<has_read<T>::value>::type * = nullptr>
inline bool read_single(T &x) {
x.read();
return true;
}
bool read_single(double &ref) {
string s;
if (!read_single(s)) return false;
ref = std::stod(s);
return true;
}
bool read_single(char &ref) {
string s;
if (!read_single(s) || s.size() != 1) return false;
ref = s[0];
return true;
}
template <class T>
bool read_single(vector<T> &ref) {
for (auto &d: ref) {
if (!read_single(d)) return false;
}
return true;
}
template <class T, class U>
bool read_single(pair<T, U> &p) {
return (read_single(p.first) && read_single(p.second));
}
template <size_t N = 0, typename T>
void read_single_tuple(T &t) {
if constexpr (N < std::tuple_size<T>::value) {
auto &x = std::get<N>(t);
read_single(x);
read_single_tuple<N + 1>(t);
}
}
template <class... T>
bool read_single(tuple<T...> &tpl) {
read_single_tuple(tpl);
return true;
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
Scanner(FILE *fp) : fp(fp) {}
};
struct Printer {
Printer(FILE *_fp) : fp(_fp) {}
~Printer() { flush(); }
static constexpr size_t SIZE = 1 << 15;
FILE *fp;
char line[SIZE], small[50];
size_t pos = 0;
void flush() {
fwrite(line, 1, pos, fp);
pos = 0;
}
void write(const char val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
void write(T val) {
if (pos > (1 << 15) - 50) flush();
if (val == 0) {
write('0');
return;
}
if (val < 0) {
write('-');
val = -val; // todo min
}
size_t len = 0;
while (val) {
small[len++] = char(0x30 | (val % 10));
val /= 10;
}
for (size_t i = 0; i < len; i++) { line[pos + i] = small[len - 1 - i]; }
pos += len;
}
void write(const string s) {
for (char c: s) write(c);
}
void write(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) write(s[i]);
}
void write(const double x) {
ostringstream oss;
oss << fixed << setprecision(15) << x;
string s = oss.str();
write(s);
}
void write(const long double x) {
ostringstream oss;
oss << fixed << setprecision(15) << x;
string s = oss.str();
write(s);
}
template <typename T,
typename enable_if<has_write<T>::value>::type * = nullptr>
inline void write(T x) {
x.write();
}
template <class T>
void write(const vector<T> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write(' ');
write(val[i]);
}
}
template <class T, class U>
void write(const pair<T, U> val) {
write(val.first);
write(' ');
write(val.second);
}
template <size_t N = 0, typename T>
void write_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) { write(' '); }
const auto x = std::get<N>(t);
write(x);
write_tuple<N + 1>(t);
}
}
template <class... T>
bool write(tuple<T...> tpl) {
write_tuple(tpl);
return true;
}
template <class T, size_t S>
void write(const array<T, S> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write(' ');
write(val[i]);
}
}
void write(i128 val) {
string s;
bool negative = 0;
if (val < 0) {
negative = 1;
val = -val;
}
while (val) {
s += '0' + int(val % 10);
val /= 10;
}
if (negative) s += "-";
reverse(all(s));
if (len(s) == 0) s = "0";
write(s);
}
};
Scanner scanner = Scanner(stdin);
Printer printer = Printer(stdout);
void flush() { printer.flush(); }
void print() { printer.write('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
printer.write(head);
if (sizeof...(Tail)) printer.write(' ');
print(forward<Tail>(tail)...);
}
void read() {}
template <class Head, class... Tail>
void read(Head &head, Tail &... tail) {
scanner.read(head);
read(tail...);
}
} // namespace fastio
using fastio::print;
using fastio::flush;
using fastio::read;
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
read(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
read(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
read(name)
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
read(name)
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 2 "library/geo/base.hpp"
template <typename T>
struct Point {
T x, y;
Point() = default;
template <typename A, typename B>
Point(A x, B y) : x(x), y(y) {}
template <typename A, typename B>
Point(pair<A, B> p) : x(p.fi), y(p.se) {}
Point operator+(Point p) const { return {x + p.x, y + p.y}; }
Point operator-(Point p) const { return {x - p.x, y - p.y}; }
bool operator==(Point p) const { return x == p.x && y == p.y; }
Point operator-() const { return {-x, -y}; }
bool operator<(Point p) const {
if (x != p.x) return x < p.x;
return y < p.y;
}
T dot(Point other) { return x * other.x + y * other.y; }
T det(Point other) { return x * other.y - y * other.x; }
void read() { fastio::read(x), fastio::read(y); }
void write() { fastio::printer.write(pair<T, T>({x, y})); }
};
template <typename T>
int ccw(Point<T> A, Point<T> B, Point<T> C) {
T x = (B - A).det(C - A);
if (x > 0) return 1;
if (x < 0) return -1;
return 0;
}
template <typename REAL, typename T>
REAL dist(Point<T> A, Point<T> B) {
A = A - B;
T p = A.dot(A);
return sqrt(REAL(p));
}
template <typename T>
struct Line {
T a, b, c;
Line(T a, T b, T c) : a(a), b(b), c(c) {}
Line(Point<T> A, Point<T> B) {
a = A.y - B.y;
b = B.x - A.x;
c = A.x * B.y - A.y * B.x;
}
Line(T x1, T y1, T x2, T y2) : Line(Point<T>(x1, y1), Point<T>(x2, y2)) {}
template <typename U>
U eval(Point<U> P) {
return a * P.x + b * P.y + c;
}
template <typename U>
T eval(U x, U y) {
return a * x + b * y + c;
}
bool is_parallel(Line other) { return a * other.b - b * other.a == 0; }
bool is_orthogonal(Line other) { return a * other.a + b * other.b == 0; }
};
template <typename T>
struct Segment {
Point<T> A, B;
Segment(Point<T> A, Point<T> B) : A(A), B(B) {}
Segment(T x1, T y1, T x2, T y2)
: Segment(Point<T>(x1, y1), Point<T>(x2, y2)) {}
template <enable_if_t<is_integral<T>::value, int> = 0>
bool contain(Point<T> C) {
T det = (C - A).det(B - A);
if (det != 0) return 0;
return (C - A).dot(B - A) >= 0 && (C - B).dot(A - B) >= 0;
}
Line<T> to_Line() { return Line(A, B); }
};
template <typename T>
struct Circle {
Point<T> O;
T r;
Circle(Point<T> O, T r) : O(O), r(r) {}
Circle(T x, T y, T r) : O(Point<T>(x, y)), r(r) {}
};
template <typename T>
struct Polygon {
vc<Point<T>> points;
T a;
template <typename A, typename B>
Polygon(vc<pair<A, B>> pairs) {
for (auto&& [a, b]: pairs) points.eb(Point<T>(a, b));
build();
}
Polygon(vc<Point<T>> points) : points(points) { build(); }
int size() { return len(points); }
template <typename REAL>
REAL area() {
return a * 0.5;
}
template <enable_if_t<is_integral<T>::value, int> = 0>
T area_2() {
return a;
}
bool is_convex() {
FOR(j, len(points)) {
int i = (j == 0 ? len(points) - 1 : j - 1);
int k = (j == len(points) - 1 ? 0 : j + 1);
if ((points[j] - points[i]).det(points[k] - points[j]) < 0) return false;
}
return true;
}
private:
void build() {
a = 0;
FOR(i, len(points)) {
int j = (i + 1 == len(points) ? 0 : i + 1);
a += points[i].det(points[j]);
}
if (a < 0) {
a = -a;
reverse(all(points));
}
}
};
#line 2 "library/geo/cross_point.hpp"
// 平行でないことを仮定
template <typename REAL, typename T>
Point<REAL> cross_point(const Line<T> L1, const Line<T> L2) {
T det = L1.a * L2.b - L1.b * L2.a;
assert(det != 0);
REAL x = -REAL(L1.c) * L2.b + REAL(L1.b) * L2.c;
REAL y = -REAL(L1.a) * L2.c + REAL(L1.c) * L2.a;
return Point<REAL>(x / det, y / det);
}
// 0: 交点なし
// 1: 一意な交点
// 2:2 つ以上の交点(整数型を利用して厳密にやる)
template <typename T, enable_if_t<is_integral<T>::value, int> = 0>
int count_cross(Segment<T> S1, Segment<T> S2, bool include_ends) {
Line<T> L1 = S1.to_Line();
Line<T> L2 = S2.to_Line();
if (L1.is_parallel(L2)) {
if (L1.eval(S2.A) != 0) return 0;
// 4 点とも同一直線上にある
T a1 = S1.A.x, b1 = S1.B.x;
T a2 = S2.A.x, b2 = S2.B.x;
if (a1 == b1) {
a1 = S1.A.y, b1 = S1.B.y;
a2 = S2.A.y, b2 = S2.B.y;
}
if (a1 > b1) swap(a1, b1);
if (a2 > b2) swap(a2, b2);
T a = max(a1, a2);
T b = min(b1, b2);
if (a < b) return 2;
if (a > b) return 0;
return (include_ends ? 1 : 0);
}
// 平行でない場合
T a1 = L2.eval(S1.A), b1 = L2.eval(S1.B);
T a2 = L1.eval(S2.A), b2 = L1.eval(S2.B);
if (a1 > b1) swap(a1, b1);
if (a2 > b2) swap(a2, b2);
bool ok1 = 0, ok2 = 0;
if (include_ends) {
ok1 = (a1 <= 0) && (0 <= b1);
ok2 = (a2 <= 0) && (0 <= b2);
} else {
ok1 = (a1 < 0) && (0 < b1);
ok2 = (a2 < 0) && (0 < b2);
}
return (ok1 && ok2 ? 1 : 0);
}
// 0 または 1
// real だと誤差によっては間違った答を返す可能性あり。
/*
template <typename T>
int count_cross(Segment<T> S1, Segment<T> S2) {
Line<T> L1 = S1.to_Line();
Line<T> L2 = S2.to_Line();
T a1 = L2.eval(S1.A), b1 = L2.eval(S1.B);
T a2 = L1.eval(S2.A), b2 = L1.eval(S2.B);
if (a1 > b1) swap(a1, b1);
if (a2 > b2) swap(a2, b2);
bool ok1 = 0, ok2 = 0;
ok1 = (a1 <= 0) && (0 <= b1);
ok2 = (a2 <= 0) && (0 <= b2);
return (ok1 && ok2 ? 1 : 0);
}
*/
// 唯一の交点を持つことを仮定
template <typename REAL, typename T>
Point<REAL> cross_point(Segment<T> S1, Segment<T> S2) {
Line<T> L1 = S1.to_Line();
Line<T> L2 = S2.to_Line();
return cross_point<REAL, T>(L1, L2);
}
#line 2 "library/mod/modint.hpp"
template <int mod>
struct modint {
int val;
constexpr modint(ll x = 0) noexcept {
if (0 <= x && x < mod)
val = x;
else {
x %= mod;
val = (x < 0 ? x + mod : x);
}
}
bool operator<(const modint &other) const {
return val < other.val;
} // To use std::map
modint &operator+=(const modint &p) {
if ((val += p.val) >= mod) val -= mod;
return *this;
}
modint &operator-=(const modint &p) {
if ((val += mod - p.val) >= mod) val -= mod;
return *this;
}
modint &operator*=(const modint &p) {
val = (int)(1LL * val * p.val % mod);
return *this;
}
modint &operator/=(const modint &p) {
*this *= p.inverse();
return *this;
}
modint operator-() const { return modint(-val); }
modint operator+(const modint &p) const { return modint(*this) += p; }
modint operator-(const modint &p) const { return modint(*this) -= p; }
modint operator*(const modint &p) const { return modint(*this) *= p; }
modint operator/(const modint &p) const { return modint(*this) /= p; }
bool operator==(const modint &p) const { return val == p.val; }
bool operator!=(const modint &p) const { return val != p.val; }
modint inverse() const {
int a = val, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b), swap(u -= t * v, v);
}
return modint(u);
}
modint pow(int64_t n) const {
modint ret(1), mul(val);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
#ifdef FASTIO
void write() { fastio::printer.write(val); }
void read() {
ll x;
fastio::scanner.read(x);
if (x < 0 || x >= mod) x %= mod;
if (x < 0) x += mod;
val += x;
}
#endif
static constexpr int get_mod() { return mod; }
};
struct ArbitraryModInt {
static constexpr bool is_modint = true;
int val;
ArbitraryModInt() : val(0) {}
ArbitraryModInt(int64_t y)
: val(y >= 0 ? y % get_mod()
: (get_mod() - (-y) % get_mod()) % get_mod()) {}
bool operator<(const ArbitraryModInt &other) const {
return val < other.val;
} // To use std::map<ArbitraryModInt, T>
static int &get_mod() {
static int mod = 0;
return mod;
}
static void set_mod(int md) { get_mod() = md; }
ArbitraryModInt &operator+=(const ArbitraryModInt &p) {
if ((val += p.val) >= get_mod()) val -= get_mod();
return *this;
}
ArbitraryModInt &operator-=(const ArbitraryModInt &p) {
if ((val += get_mod() - p.val) >= get_mod()) val -= get_mod();
return *this;
}
ArbitraryModInt &operator*=(const ArbitraryModInt &p) {
long long a = (long long)val * p.val;
int xh = (int)(a >> 32), xl = (int)a, d, m;
asm("divl %4; \n\t" : "=a"(d), "=d"(m) : "d"(xh), "a"(xl), "r"(get_mod()));
val = m;
return *this;
}
ArbitraryModInt &operator/=(const ArbitraryModInt &p) {
*this *= p.inverse();
return *this;
}
ArbitraryModInt operator-() const { return ArbitraryModInt(get_mod() - val); }
ArbitraryModInt operator+(const ArbitraryModInt &p) const {
return ArbitraryModInt(*this) += p;
}
ArbitraryModInt operator-(const ArbitraryModInt &p) const {
return ArbitraryModInt(*this) -= p;
}
ArbitraryModInt operator*(const ArbitraryModInt &p) const {
return ArbitraryModInt(*this) *= p;
}
ArbitraryModInt operator/(const ArbitraryModInt &p) const {
return ArbitraryModInt(*this) /= p;
}
bool operator==(const ArbitraryModInt &p) const { return val == p.val; }
bool operator!=(const ArbitraryModInt &p) const { return val != p.val; }
ArbitraryModInt inverse() const {
int a = val, b = get_mod(), u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b), swap(u -= t * v, v);
}
return ArbitraryModInt(u);
}
ArbitraryModInt pow(int64_t n) const {
ArbitraryModInt ret(1), mul(val);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
#ifdef FASTIO
void write() { fastio::printer.write(val); }
void read() { fastio::scanner.read(val); }
#endif
};
template <typename mint>
mint inv(int n) {
static const int mod = mint::get_mod();
static vector<mint> dat = {0, 1};
assert(0 <= n);
if (n >= mod) n %= mod;
while (int(dat.size()) <= n) {
int k = dat.size();
auto q = (mod + k - 1) / k;
int r = k * q - mod;
dat.emplace_back(dat[r] * mint(q));
}
return dat[n];
}
template <typename mint>
mint fact(int n) {
static const int mod = mint::get_mod();
static vector<mint> dat = {1, 1};
assert(0 <= n);
if (n >= mod) return 0;
while (int(dat.size()) <= n) {
int k = dat.size();
dat.emplace_back(dat[k - 1] * mint(k));
}
return dat[n];
}
template <typename mint>
mint fact_inv(int n) {
static const int mod = mint::get_mod();
static vector<mint> dat = {1, 1};
assert(-1 <= n && n < mod);
if (n == -1) return mint(0);
while (int(dat.size()) <= n) {
int k = dat.size();
dat.emplace_back(dat[k - 1] * inv<mint>(k));
}
return dat[n];
}
template <class mint, class... Ts>
mint fact_invs(Ts... xs) {
return (mint(1) * ... * fact_inv<mint>(xs));
}
template <typename mint, class Head, class... Tail>
mint multinomial(Head &&head, Tail &&... tail) {
return fact<mint>(head) * fact_invs<mint>(std::forward<Tail>(tail)...);
}
template <typename mint>
mint C_dense(int n, int k) {
static vvc<mint> C;
static int H = 0, W = 0;
auto calc = [&](int i, int j) -> mint {
if (i == 0) return (j == 0 ? mint(1) : mint(0));
return C[i - 1][j] + (j ? C[i - 1][j - 1] : 0);
};
if (W <= k) {
FOR(i, H) {
C[i].resize(k + 1);
FOR(j, W, k + 1) { C[i][j] = calc(i, j); }
}
W = k + 1;
}
if (H <= n) {
C.resize(n + 1);
FOR(i, H, n + 1) {
C[i].resize(W);
FOR(j, W) { C[i][j] = calc(i, j); }
}
H = n + 1;
}
return C[n][k];
}
template <typename mint, bool large = false, bool dense = false>
mint C(ll n, ll k) {
assert(n >= 0);
if (k < 0 || n < k) return 0;
if (dense) return C_dense<mint>(n, k);
if (!large) return fact<mint>(n) * fact_inv<mint>(k) * fact_inv<mint>(n - k);
k = min(k, n - k);
mint x(1);
FOR(i, k) { x *= mint(n - i); }
x *= fact_inv<mint>(k);
return x;
}
template <typename mint, bool large = false>
mint C_inv(ll n, ll k) {
assert(n >= 0);
assert(0 <= k && k <= n);
if (!large) return fact_inv<mint>(n) * fact<mint>(k) * fact<mint>(n - k);
return mint(1) / C<mint, 1>(n, k);
}
// [x^d] (1-x) ^ {-n} の計算
template <typename mint, bool large = false, bool dense = false>
mint C_negative(ll n, ll d) {
assert(n >= 0);
if (d < 0) return mint(0);
if (n == 0) { return (d == 0 ? mint(1) : mint(0)); }
return C<mint, large, dense>(n + d - 1, d);
}
using modint107 = modint<1000000007>;
using modint998 = modint<998244353>;
using amint = ArbitraryModInt;
#line 2 "library/nt/primetable.hpp"
template <typename T = long long>
vc<T> primetable(int LIM) {
++LIM;
const int S = 32768;
static int done = 2;
static vc<T> primes = {2}, sieve(S + 1);
if (done < LIM) {
done = LIM;
primes = {2}, sieve.assign(S + 1, 0);
const int R = LIM / 2;
primes.reserve(int(LIM / log(LIM) * 1.1));
vc<pair<int, int>> cp;
for (int i = 3; i <= S; i += 2) {
if (!sieve[i]) {
cp.eb(i, i * i / 2);
for (int j = i * i; j <= S; j += 2 * i) sieve[j] = 1;
}
}
for (int L = 1; L <= R; L += S) {
array<bool, S> block{};
for (auto& [p, idx]: cp)
for (int i = idx; i < S + L; idx = (i += p)) block[i - L] = 1;
FOR(i, min(S, R - L)) if (!block[i]) primes.eb((L + i) * 2 + 1);
}
}
int k = LB(primes, LIM + 1);
return {primes.begin(), primes.begin() + k};
}
#line 3 "library/mod/powertable.hpp"
// a^0, ..., a^N
template <typename mint>
vc<mint> powertable_1(mint a, ll N) {
// table of a^i
vc<mint> f(N + 1, 1);
FOR(i, N) f[i + 1] = a * f[i];
return f;
}
// 0^e, ..., N^e
template <typename mint>
vc<mint> powertable_2(ll e, ll N) {
auto primes = primetable(N);
vc<mint> f(N + 1, 1);
f[0] = mint(0).pow(e);
for (auto&& p: primes) {
if (p > N) break;
mint xp = mint(p).pow(e);
ll pp = p;
while (pp <= N) {
ll i = pp;
while (i <= N) {
f[i] *= xp;
i += pp;
}
pp *= p;
}
}
return f;
}
#line 2 "library/geo/angle_sort.hpp"
#line 4 "library/geo/angle_sort.hpp"
// 偏角ソートに対する argsort
template <typename T>
vector<int> angle_argsort(vector<Point<T>>& P) {
vector<int> lower, origin, upper;
const Point<T> O = {0, 0};
FOR(i, len(P)) {
if (P[i] == O) origin.eb(i);
elif ((P[i].y < 0) || (P[i].y == 0 && P[i].x > 0)) lower.eb(i);
else upper.eb(i);
}
sort(all(lower), [&](auto& i, auto& j) { return P[i].det(P[j]) > 0; });
sort(all(upper), [&](auto& i, auto& j) { return P[i].det(P[j]) > 0; });
auto& I = lower;
I.insert(I.end(), all(origin));
I.insert(I.end(), all(upper));
return I;
}
// 偏角ソートに対する argsort
template <typename T>
vector<int> angle_argsort(vector<pair<T, T>>& P) {
vc<Point<T>> tmp(len(P));
FOR(i, len(P)) tmp[i] = Point<T>(P[i]);
return angle_argsort<T>(tmp);
}
// inplace に偏角ソートする
// index が欲しい場合は angle_argsort
template <typename T>
void angle_sort(vector<Point<T>>& P) {
auto I = angle_argsort<T>(P);
P = rearrange(P, I);
}
// inplace に偏角ソートする
// index が欲しい場合は angle_argsort
template <typename T>
void angle_sort(vector<pair<T, T>>& P) {
auto I = angle_argsort<T>(P);
P = rearrange(P, I);
}
#line 1 "library/geo/inside_polygon.hpp"
// https://qoj.ac/problem/5443
// 線分上に頂点や辺が来ることは許容
template <typename T>
bool inside_polygon(Segment<T> S, vc<Point<T>>& dat) {
using P = Point<T>;
int N = len(dat);
int cnt = 0;
P A = S.A, B = S.B;
auto PREV = [&](int i) -> int { return (i == 0 ? N : i) - 1; };
auto NEXT = [&](int i) -> int { return (i == N - 1 ? 0 : i + 1); };
FOR(i, N) {
P p = dat[i], q = dat[NEXT(i)], r = dat[PREV(i)];
int a = ccw(A, B, p);
int b = ccw(A, B, q);
int c = ccw(A, B, r);
if (a * b == -1) {
Segment pq(p, q);
auto L = pq.to_Line();
T x = L.eval(A), y = L.eval(B);
if (x < y) { x = -x, y = -y; }
if (x <= 0) ++cnt;
if (0 < x && x < x - y) return 0;
}
if (a == 0) {
if (b != c && (b * c < 0 || ccw(p, q, r) > 0)) {
T t = (p - A).dot(B - A), x = (B - A).dot(B - A);
if (t <= 0) ++cnt;
if (0 < t && t < x) return 0;
}
}
}
return cnt % 2 == 1;
}
#line 9 "main.cpp"
using P = Point<ll>;
using mint = modint998;
/*
凸多角形を作る dp。
・正の角まわる移動だけを考える。間の点があれば 2^n かける。
・「2 角形」はあとで処理する
*/
void solve() {
LL(N);
VEC(P, dat, N);
vv(bool, CAN, N, N);
vv(int, CNT, N, N);
FOR(a, N) FOR(b, N) {
if (a == b) continue;
P A = dat[a], B = dat[b];
Segment<ll> AB(A, B);
vc<bool> ON(N);
FOR(c, N) {
if (AB.contain(dat[c])) ON[c] = 1;
}
CNT[a][b] = SUM<int>(ON) - 2;
CAN[a][b] = inside_polygon(AB, dat);
}
/*
FOR(a, N) print(CAN[a]);
*/
FOR(a, N) FOR(b, N) assert(CAN[a][b] == CAN[b][a]);
FOR(a, N) FOR(b, N) assert(CNT[a][b] == CNT[b][a]);
mint ANS = 0;
vc<mint> POW = powertable_1<mint>(2, N);
// 凸包が線分
FOR(a, N) FOR(b, a) {
if (CAN[a][b]) ANS += POW[CNT[a][b]];
}
// angle sort
vc<pi> edge;
vc<P> dir;
FOR(a, N) FOR(b, N) {
if (CAN[a][b]) {
edge.eb(a, b);
dir.eb(dat[b] - dat[a]);
}
}
auto I = angle_argsort(dir);
edge = rearrange(edge, I);
dir = rearrange(dir, I);
FOR(s, N) {
// s スタート
// [0][v]:1 回だけ進んだ
// [1][v]:2 回以上進んだ
vv(mint, dp, 2, N);
// 同じ向きの線分での遷移をまとめて更新するようにする
auto SAME = [&](int i, int j) -> bool {
return (dir[i].det(dir[j]) == 0 && dir[i].dot(dir[j]) > 0);
};
int L = 0;
while (L < len(edge)) {
int R = L;
while (R < len(edge) && SAME(L, R)) ++R;
vc<tuple<int, int, mint>> upd;
FOR(e, L, R) {
auto [frm, to] = edge[e];
mint cf = POW[CNT[frm][to]];
if (frm == s) {
upd.eb(0, to, cf);
} else {
if (to != s) upd.eb(1, to, dp[0][frm] * cf);
upd.eb(1, to, dp[1][frm] * cf);
}
}
L = R;
for (auto&& [a, b, c]: upd) dp[a][b] += c;
}
ANS += dp[1][s];
}
print(ANS);
}
signed main() {
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3496kb
input:
7 0 20 40 0 40 20 70 50 50 70 30 50 0 50
output:
56
result:
ok 1 number(s): "56"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3448kb
input:
3 0 2022 -2022 -2022 2022 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
3 4 0 0 3 0 0
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3444kb
input:
3 -10 0 10 0 0 18
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
4 0 0 -10 0 -10 -10 0 -10
output:
11
result:
ok 1 number(s): "11"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
4 -100 0 0 -100 100 0 0 100
output:
11
result:
ok 1 number(s): "11"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3428kb
input:
4 0 0 10 5 20 0 10 10
output:
7
result:
ok 1 number(s): "7"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
4 0 0 20 0 30 10 10 10
output:
11
result:
ok 1 number(s): "11"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
4 -100 -10 100 -10 100 10 -100 10
output:
11
result:
ok 1 number(s): "11"
Test #10:
score: 0
Accepted
time: 2ms
memory: 3360kb
input:
4 0 0 100 0 60 30 0 30
output:
11
result:
ok 1 number(s): "11"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
4 0 0 100 0 60 30 40 30
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
7 0 0 10 10 20 0 30 11 20 22 10 11 0 22
output:
44
result:
ok 1 number(s): "44"
Test #13:
score: 0
Accepted
time: 2ms
memory: 3284kb
input:
10 0 0 10 10 20 0 30 10 40 0 40 21 30 11 20 21 10 11 0 21
output:
93
result:
ok 1 number(s): "93"
Test #14:
score: 0
Accepted
time: 2ms
memory: 3480kb
input:
7 0 0 50 50 80 20 110 50 70 90 40 60 0 100
output:
44
result:
ok 1 number(s): "44"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3508kb
input:
16 0 0 20 0 20 10 40 10 40 20 60 20 60 30 70 30 70 40 50 40 50 30 30 30 30 20 10 20 10 10 0 10
output:
407
result:
ok 1 number(s): "407"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
12 0 0 400 0 400 500 0 500 0 200 200 200 200 300 100 300 100 400 300 400 300 100 0 100
output:
51
result:
ok 1 number(s): "51"
Test #17:
score: 0
Accepted
time: 2ms
memory: 3444kb
input:
10 0 500 -10 20 -350 350 -20 0 -350 -350 0 -20 350 -350 20 0 350 350 10 20
output:
93
result:
ok 1 number(s): "93"
Test #18:
score: 0
Accepted
time: 2ms
memory: 3444kb
input:
16 0 0 10 -5 20 0 30 15 40 0 45 10 40 20 25 30 40 40 30 45 20 40 10 25 0 40 -5 30 0 20 15 10
output:
247
result:
ok 1 number(s): "247"
Test #19:
score: 0
Accepted
time: 2ms
memory: 3324kb
input:
8 100 90 90 100 -90 100 -100 90 -100 -90 -90 -100 90 -100 100 -90
output:
247
result:
ok 1 number(s): "247"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3340kb
input:
8 0 0 10 100 90 100 100 0 100 201 90 101 10 101 0 201
output:
31
result:
ok 1 number(s): "31"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3368kb
input:
8 0 0 100 100 900 100 1000 0 1000 210 900 110 100 110 0 210
output:
31
result:
ok 1 number(s): "31"
Test #22:
score: 0
Accepted
time: 2ms
memory: 3476kb
input:
3 1000000 -1000000 1000000 1000000 -1000000 -1000000
output:
4
result:
ok 1 number(s): "4"
Test #23:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
4 1000000 -1000000 1000000 1000000 1 0 -1000000 -1000000
output:
7
result:
ok 1 number(s): "7"
Test #24:
score: 0
Accepted
time: 2ms
memory: 3440kb
input:
4 1000000 -1000000 1000000 1000000 0 1 -1000000 -1000000
output:
11
result:
ok 1 number(s): "11"
Test #25:
score: 0
Accepted
time: 554ms
memory: 5708kb
input:
200 -28269 899556 -52917 898443 -82904 896173 -112799 892903 -139901 889060 -167758 884227 -196328 878325 -220331 872613 -248497 865014 -277258 856229 -302321 847703 -331311 836799 -354953 827048 -381571 815109 -407788 802314 -431209 789973 -455810 776039 -479961 761338 -503639 745887 -529006 728115...
output:
982924531
result:
ok 1 number(s): "982924531"
Test #26:
score: 0
Accepted
time: 532ms
memory: 5560kb
input:
200 -28269 899556 -52917 898443 -82904 896173 -112799 892903 -139901 889060 -167758 884227 -196328 878325 -220331 872613 -248497 865014 -277258 856229 -302321 847703 -331311 836799 -354953 827048 -381571 815109 -407788 802314 -431209 789973 -455810 776039 -479961 761338 -503639 745887 -529006 728115...
output:
491462169
result:
ok 1 number(s): "491462169"
Test #27:
score: 0
Accepted
time: 95ms
memory: 4024kb
input:
200 -1000000 0 -984589 0 -959090 -1000000 -939997 0 -920698 -1000000 -903689 0 -878269 -1000000 -856526 0 -835872 -1000000 -824921 0 -802874 -1000000 -775273 0 -762503 -1000000 -736648 0 -723628 -1000000 -700062 0 -677324 -1000000 -655520 0 -638093 -1000000 -616069 0 -596730 -1000000 -578522 0 -5610...
output:
766756066
result:
ok 1 number(s): "766756066"
Test #28:
score: 0
Accepted
time: 127ms
memory: 4412kb
input:
200 -982632 0 -969103 -1000000 -940842 0 -921682 0 -906001 -1000000 -879789 0 -865042 0 -845192 -1000000 -816404 0 -802606 0 -787373 -1000000 -753645 0 -737956 0 -725228 -1000000 -692298 0 -681026 0 -651636 -1000000 -636348 0 -619790 0 -587407 -1000000 -573321 0 -558772 0 -527808 -1000000 -513494 0 ...
output:
399992829
result:
ok 1 number(s): "399992829"
Test #29:
score: 0
Accepted
time: 2ms
memory: 3332kb
input:
7 30 0 30 20 60 40 90 40 90 60 20 50 0 0
output:
40
result:
ok 1 number(s): "40"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
9 30 0 30 20 20 30 50 50 60 40 90 40 90 60 20 50 0 0
output:
30
result:
ok 1 number(s): "30"
Test #31:
score: 0
Accepted
time: 2ms
memory: 3452kb
input:
10 0 0 400 0 400 200 300 200 300 100 100 100 100 300 400 300 400 400 0 400
output:
41
result:
ok 1 number(s): "41"
Test #32:
score: 0
Accepted
time: 2ms
memory: 3428kb
input:
10 0 -400 400 -400 400 -300 100 -300 100 -100 300 -100 300 -200 400 -200 400 0 0 0
output:
41
result:
ok 1 number(s): "41"
Test #33:
score: 0
Accepted
time: 2ms
memory: 3412kb
input:
20 -2 11 -6 3 -4 2 -1 8 9 3 3 -9 -5 -5 -4 -3 2 -6 6 2 0 5 -2 1 0 0 1 2 3 1 1 -3 -5 0 -8 -6 4 -12 12 4
output:
91
result:
ok 1 number(s): "91"
Test #34:
score: 0
Accepted
time: 56ms
memory: 3636kb
input:
200 -153811 101954 -110538 -13951 -21156 16822 20793 -224637 -105318 -28386 -184845 -25122 -55966 -252174 -65073 -240349 -402588 -55614 -319429 351875 -479382 92012 -213699 555429 112299 348899 687998 510477 379335 468944 157461 420548 102219 458523 148907 488400 610913 530181 430304 566961 821268 5...
output:
1687
result:
ok 1 number(s): "1687"
Test #35:
score: 0
Accepted
time: 61ms
memory: 3744kb
input:
200 122301 113556 338694 233402 368238 131577 446030 331311 535103 535679 781548 843294 666909 875595 442356 427784 374568 306449 -26086 6336 356963 370926 75420 132096 109676 185484 392958 553349 511233 697425 -105084 -25122 16287 361251 338613 501111 251648 493356 589628 908975 16500 972309 535022...
output:
1663
result:
ok 1 number(s): "1663"
Test #36:
score: 0
Accepted
time: 56ms
memory: 3808kb
input:
200 421640 547713 650121 928769 547442 928833 346206 886544 -452730 992357 102138 855965 111368 905793 366936 808814 97664 687998 306486 711903 22692 663762 -57963 885504 -55792 734234 -463485 989088 -157192 737144 -241500 603149 -444462 699033 -203932 580725 37067 568415 339672 708146 497484 744522...
output:
1599
result:
ok 1 number(s): "1599"
Test #37:
score: 0
Accepted
time: 51ms
memory: 3632kb
input:
200 207543 18138 233654 136908 700845 -843115 765038 -961705 480771 -367522 784833 -913671 931941 -853932 718884 -558630 197457 373259 426012 6606 359594 164931 795933 -587514 362999 173610 635496 -231358 517028 -17575 653370 -224637 779784 -468309 814878 -651810 970226 -830284 897312 -690219 653588...
output:
1403
result:
ok 1 number(s): "1403"
Test #38:
score: 0
Accepted
time: 54ms
memory: 3696kb
input:
200 384246 119904 515880 90069 537210 144074 706626 62156 434349 603996 378143 465476 443127 317247 164931 198306 533444 341568 239054 104826 37271 27579 161283 99692 -13462 22109 497481 748134 753303 786567 441458 667358 736625 725172 466416 609863 638721 590361 679778 436017 624801 526664 704712 1...
output:
1703
result:
ok 1 number(s): "1703"
Test #39:
score: 0
Accepted
time: 54ms
memory: 3764kb
input:
200 290300 170277 240567 128495 339132 87891 177572 360968 480771 164259 512115 17961 405629 5648 333267 87849 346164 -61209 737469 -277905 699884 -331989 552159 -233661 67764 13977 51210 -31561 624573 -303696 365547 -415143 596037 -320155 382416 -471408 455414 -430867 473946 -409309 653883 -416259 ...
output:
1723
result:
ok 1 number(s): "1723"
Test #40:
score: 0
Accepted
time: 54ms
memory: 3652kb
input:
200 -55665 353610 -95883 490124 132390 -66873 58841 248211 516981 -547989 507597 -169864 509958 -216196 522693 -268425 681047 -280795 494694 -143556 266337 -45390 313914 -52921 223239 1950 194649 346206 384276 367670 369288 321381 762722 -204108 497747 152082 716706 205593 526883 280884 795998 34640...
output:
1959
result:
ok 1 number(s): "1959"
Test #41:
score: 0
Accepted
time: 57ms
memory: 3768kb
input:
200 283343 271859 383730 322703 365793 322247 450695 405629 434937 311613 486618 479943 358449 -12483 67130 -122775 416790 227442 -16551 -180451 295266 -315165 383364 28503 502124 440735 527090 528342 456162 243552 444408 -165328 648036 -459271 561377 -12972 539900 87975 597287 63161 566952 304059 7...
output:
1703
result:
ok 1 number(s): "1703"
Test #42:
score: 0
Accepted
time: 55ms
memory: 3536kb
input:
200 5009 71481 -20981 20885 -12 -30222 -99838 189696 103887 126708 351540 380079 242496 299244 527678 785484 336098 539408 101865 137745 64338 267396 147075 359897 524 197672 520671 794027 -45390 774477 408812 806877 32813 864956 -594379 939110 -400881 862851 -841240 825276 -623754 795456 -233265 84...
output:
1579
result:
ok 1 number(s): "1579"
Test #43:
score: 0
Accepted
time: 58ms
memory: 3640kb
input:
200 635384 485892 765764 574319 336258 334347 465048 520794 519375 558921 682283 607704 982737 801953 564318 664179 209807 405618 419262 582690 -7986 577806 -441678 673641 171933 603149 261948 582564 129839 653445 374771 807498 499641 893376 916239 999597 -190753 742980 162081 984042 -325008 701442 ...
output:
1731
result:
ok 1 number(s): "1731"
Test #44:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
6 0 0 110828 157796 232685 157796 232685 331295 214662 305634 0 305634
output:
29
result:
ok 1 number(s): "29"
Test #45:
score: 0
Accepted
time: 1ms
memory: 3496kb
input:
10 0 0 110828 157796 233685 157796 233685 341295 232685 341295 232685 331295 214662 305634 -1000 305634 -1000 -10000 0 -10000
output:
49
result:
ok 1 number(s): "49"
Test #46:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
6 0 220492 -741872 220492 -750260 222985 -750260 205257 -690612 205257 0 0
output:
29
result:
ok 1 number(s): "29"
Test #47:
score: 0
Accepted
time: 2ms
memory: 3420kb
input:
10 0 -3000 10000 -3000 10000 220492 -741872 220492 -750260 222985 -750260 225985 -760260 225985 -760260 205257 -690612 205257 0 0
output:
49
result:
ok 1 number(s): "49"
Test #48:
score: 0
Accepted
time: 2ms
memory: 3364kb
input:
6 -999999 -1000000 1000000 999999 -999999 999999 -999999 -999999 -1000000 -999999 -1000000 -1000000
output:
25
result:
ok 1 number(s): "25"
Test #49:
score: 0
Accepted
time: 2ms
memory: 3476kb
input:
6 -999999 -1000000 -999999 -999999 1000000 -999999 1000000 999999 999998 999999 -1000000 -1000000
output:
17
result:
ok 1 number(s): "17"
Test #50:
score: 0
Accepted
time: 2ms
memory: 3324kb
input:
6 -999999 -1000000 -999998 -999999 1000000 -999999 1000000 999999 999998 999999 -1000000 -1000000
output:
33
result:
ok 1 number(s): "33"
Test #51:
score: 0
Accepted
time: 86ms
memory: 4044kb
input:
200 1000000 -999941 -999956 -999940 -998042 -997864 -998053 -997864 -994830 -994360 -994841 -994360 -990958 -990136 -990969 -990136 -983566 -982072 -983577 -982072 -978319 -976348 -978330 -976348 -976768 -974656 -976779 -974656 -975228 -972976 -975239 -972976 -973116 -970672 -973127 -970672 -972808 ...
output:
441250450
result:
ok 1 number(s): "441250450"
Test #52:
score: 0
Accepted
time: 87ms
memory: 4052kb
input:
200 1000000 -998489 -999630 -998488 -992008 -959932 -992082 -959932 -989862 -948970 -989936 -948970 -989344 -946324 -989418 -946324 -978688 -891892 -978762 -891892 -967292 -833680 -967366 -833680 -966182 -828010 -966256 -828010 -965146 -822718 -965220 -822718 -964850 -821206 -964924 -821206 -964480 ...
output:
441250450
result:
ok 1 number(s): "441250450"
Test #53:
score: 0
Accepted
time: 85ms
memory: 4052kb
input:
200 -1000000 999787 998030 999786 958630 978600 959024 978600 946810 972180 947204 972180 940112 968542 940506 968542 837278 912688 837672 912688 817972 902202 818366 902202 814426 900276 814820 900276 809698 897708 810092 897708 798272 891502 798666 891502 788028 885938 788422 885938 785270 884440 ...
output:
441250450
result:
ok 1 number(s): "441250450"
Test #54:
score: 0
Accepted
time: 87ms
memory: 3976kb
input:
200 -1000000 997586 999374 997585 897023 840127 897336 840127 789977 674941 790290 674941 783091 664315 783404 664315 759616 628090 759929 628090 708597 549361 708910 549361 704215 542599 704528 542599 702963 540667 703276 540667 700459 536803 700772 536803 699520 535354 699833 535354 624400 419434 ...
output:
441250450
result:
ok 1 number(s): "441250450"
Test #55:
score: 0
Accepted
time: 85ms
memory: 3952kb
input:
200 1000000 -999485 975920 -982198 965600 -974200 965256 -974200 964224 -973168 963880 -973168 962504 -971878 962160 -971878 961816 -971362 961472 -971362 961128 -970846 960784 -970846 948744 -961558 948400 -961558 931200 -948400 930856 -948400 906088 -929566 905744 -929566 881320 -910990 880976 -91...
output:
441250454
result:
ok 1 number(s): "441250454"
Test #56:
score: 0
Accepted
time: 79ms
memory: 3976kb
input:
200 1000000 -999175 975085 -976872 963760 -966134 963307 -966134 918460 -924834 918007 -924834 714157 -738571 713704 -738571 638959 -670013 638506 -670013 460477 -507291 460024 -507291 360364 -416018 359911 -416018 359458 -415192 359005 -415192 355381 -411475 354928 -411475 341338 -398672 340885 -39...
output:
441250454
result:
ok 1 number(s): "441250454"
Test #57:
score: 0
Accepted
time: 82ms
memory: 3836kb
input:
200 -1000000 998441 -996730 995710 -994441 992590 -994114 992590 -985285 981670 -984958 981670 -971878 965680 -971551 965680 -967627 960610 -967300 960610 -947026 936040 -946699 936040 -925771 910690 -925444 910690 -797587 757810 -797260 757810 -791374 750400 -791047 750400 -712240 656020 -711913 65...
output:
441250450
result:
ok 1 number(s): "441250450"
Test #58:
score: 0
Accepted
time: 85ms
memory: 3992kb
input:
200 -1000000 998176 -999748 997810 -999496 996350 -999412 996350 -999160 994890 -999076 994890 -982360 921890 -982276 921890 -981352 917510 -981268 917510 -975136 890500 -975052 890500 -850144 347380 -850060 347380 -817216 204300 -817132 204300 -800920 133490 -800836 133490 -787816 76550 -787732 765...
output:
441250450
result:
ok 1 number(s): "441250450"
Test #59:
score: 0
Accepted
time: 85ms
memory: 3992kb
input:
200 100000 -999633 239 -999632 3094 -999448 239 -999448 7467 -999264 239 -999264 4608 -998896 239 -998896 649 -998712 239 -998712 2980 -998528 239 -998528 1563 -998344 239 -998344 7731 -989788 239 -989788 744 -927504 239 -927504 2244 -838724 239 -838724 8203 -807628 239 -807628 4217 -780304 239 -780...
output:
441250450
result:
ok 1 number(s): "441250450"
Test #60:
score: 0
Accepted
time: 2ms
memory: 3476kb
input:
4 -899998 -900000 0 0 450000 450001 449998 449999
output:
7
result:
ok 1 number(s): "7"
Test #61:
score: 0
Accepted
time: 2ms
memory: 3420kb
input:
4 -1000000 -1000000 0 -1 999999 999997 -1 0
output:
7
result:
ok 1 number(s): "7"
Test #62:
score: 0
Accepted
time: 2ms
memory: 3480kb
input:
5 1000000 -1000000 1000000 999999 999999 0 999999 999998 -1000000 -1000000
output:
10
result:
ok 1 number(s): "10"
Test #63:
score: 0
Accepted
time: 2ms
memory: 3500kb
input:
10 -800000 -799999 199991 199997 799987 799996 999985 999995 599988 599996 199990 199996 -200006 -200002 -600003 -600001 -800001 -800000 -1000000 -1000000
output:
73
result:
ok 1 number(s): "73"
Test #64:
score: 0
Accepted
time: 63ms
memory: 3788kb
input:
200 -677343 996088 -731021 806109 -703638 644867 -694433 455591 -698504 132249 -745640 -209598 -859170 -239875 -874703 -116547 -922684 -350844 -920583 296332 -867486 433468 -860134 490879 -849686 -2551 -813758 684881 -777869 965896 -905744 958941 -983905 544305 -996951 494366 -982454 -386675 -977004...
output:
5283
result:
ok 1 number(s): "5283"
Test #65:
score: 0
Accepted
time: 42ms
memory: 3760kb
input:
191 2 3 2 2 1 2 0 1 3 2 5 4 5 3 4 2 6 2 8 4 9 4 9 5 8 5 7 4 7 6 6 5 6 3 5 5 4 4 3 4 5 6 6 6 6 7 8 9 7 9 3 5 2 5 4 7 2 6 1 6 1 7 2 7 2 8 1 10 2 9 1 11 3 9 4 10 3 10 2 11 3 11 3 12 1 12 1 13 3 13 1 14 1 15 2 14 3 15 4 15 3 14 4 13 6 13 4 14 5 14 7 13 6 14 8 13 8 12 4 12 4 11 9 11 7 10 5 10 3 8 3 7 5 9...
output:
55064
result:
ok 1 number(s): "55064"
Test #66:
score: 0
Accepted
time: 41ms
memory: 3756kb
input:
183 3 4 2 8 2 7 1 7 1 8 0 12 0 6 1 6 1 4 0 5 0 0 1 3 1 0 2 6 2 3 3 2 2 2 3 1 2 1 2 0 12 0 12 1 13 0 15 0 13 1 14 1 16 0 16 3 15 1 13 3 14 3 13 4 15 3 15 2 16 4 16 8 15 6 15 4 14 4 12 5 13 5 12 6 12 8 13 7 13 8 12 9 13 9 14 7 14 8 15 8 14 6 13 6 14 5 16 9 16 10 15 12 16 11 16 16 12 16 13 15 13 14 14 ...
output:
5564
result:
ok 1 number(s): "5564"
Test #67:
score: 0
Accepted
time: 47ms
memory: 3660kb
input:
195 14 11 13 11 13 10 14 9 14 7 15 10 15 8 14 6 13 7 13 9 12 11 12 12 11 12 11 13 10 12 10 13 9 14 9 12 8 14 7 15 6 15 8 13 7 13 8 12 7 11 8 10 8 9 6 12 7 12 6 13 4 14 6 14 5 15 8 16 5 16 4 15 4 16 0 16 0 15 3 15 1 14 1 13 0 14 0 11 1 12 1 9 2 8 1 8 0 10 0 2 1 2 2 1 0 1 0 0 12 0 10 1 11 1 10 2 7 2 6...
output:
8148
result:
ok 1 number(s): "8148"
Test #68:
score: 0
Accepted
time: 43ms
memory: 3744kb
input:
186 13 16 12 15 12 14 13 15 15 15 15 14 14 14 13 13 14 13 14 12 13 12 12 13 13 14 11 13 9 13 8 14 11 14 11 15 12 16 6 16 10 15 7 15 5 16 2 16 5 15 6 15 7 14 6 14 4 15 3 15 4 14 4 13 2 11 1 14 1 15 2 12 2 14 3 13 3 14 1 16 0 16 0 8 1 10 1 13 2 7 2 10 3 11 3 9 5 11 6 11 7 12 5 12 4 11 4 12 5 13 6 13 5...
output:
9369
result:
ok 1 number(s): "9369"
Test #69:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
38 1 95 2 94 2 129 1 96 1 152 2 130 2 156 1 153 1 165 2 157 2 174 1 173 1 189 2 175 2 190 1 190 1 195 2 191 2 199 1 199 1 196 0 199 0 159 1 172 1 166 0 158 0 47 1 83 1 45 0 46 0 0 2 0 2 4 1 1 1 44 2 5 2 93 1 84
output:
263261
result:
ok 1 number(s): "263261"
Test #70:
score: 0
Accepted
time: 2ms
memory: 3512kb
input:
57 192 0 170 1 188 1 193 0 195 0 189 1 198 1 196 0 199 0 199 2 164 2 169 1 152 1 163 2 115 2 117 1 106 1 114 2 82 2 105 1 93 1 81 2 62 2 49 1 41 1 61 2 5 2 25 1 11 1 4 2 0 2 0 1 6 1 0 0 4 0 7 1 10 1 5 0 17 0 26 1 40 1 18 0 55 0 50 1 73 1 56 0 97 0 74 1 92 1 98 0 127 0 118 1 128 0 153 0 119 1 151 1 1...
output:
134218614
result:
ok 1 number(s): "134218614"
Test #71:
score: 0
Accepted
time: 4ms
memory: 3700kb
input:
71 2 970 1 939 1 966 2 971 2 998 1 967 1 991 2 999 1 992 1 999 0 999 0 825 1 938 1 854 0 824 0 790 1 853 1 820 0 789 0 776 1 801 1 733 0 775 0 729 1 732 1 690 0 728 0 638 1 689 1 620 0 637 0 361 1 583 1 414 0 360 0 221 1 288 1 156 0 220 0 12 1 22 1 10 0 11 0 0 1 0 1 1 2 0 2 13 1 2 1 9 2 14 2 71 1 23...
output:
838862656
result:
ok 1 number(s): "838862656"
Test #72:
score: 0
Accepted
time: 8ms
memory: 3540kb
input:
80 427 0 435 1 495 1 428 0 467 0 496 1 553 1 468 0 566 0 554 1 655 1 567 0 748 0 656 1 740 1 749 0 797 0 741 1 761 1 798 0 887 0 762 1 825 1 888 0 926 0 826 1 891 1 927 0 965 0 892 1 951 1 966 0 999 0 970 1 999 1 999 2 986 2 969 1 952 1 985 2 492 2 434 1 354 1 491 2 293 2 353 1 217 1 292 2 161 2 216...
output:
445383386
result:
ok 1 number(s): "445383386"
Test #73:
score: 0
Accepted
time: 6ms
memory: 3568kb
input:
91 0 4 1 18 1 44 2 76 2 32 1 17 1 10 2 31 2 29 1 9 1 6 2 21 2 13 1 4 1 5 0 3 0 1 1 3 1 2 2 12 2 3 1 1 0 0 1 0 2 1 2 0 3 0 3 4 2 2 3 5 3 19 2 22 2 28 3 20 3 61 2 77 2 78 1 45 1 69 2 79 2 92 3 62 3 122 2 93 2 99 3 123 3 135 2 100 2 165 3 136 3 191 2 166 2 178 3 192 3 195 2 188 2 179 1 184 1 196 2 193 ...
output:
688776
result:
ok 1 number(s): "688776"
Test #74:
score: 0
Accepted
time: 6ms
memory: 3636kb
input:
80 52 2 66 1 32 1 16 0 41 0 67 1 75 1 42 0 114 0 122 1 135 1 140 2 187 2 136 1 159 1 115 0 125 0 160 1 166 1 126 0 196 0 186 1 195 1 195 2 196 1 197 1 197 0 199 0 198 1 199 1 199 2 198 2 199 3 196 3 197 2 196 2 195 3 194 3 189 2 194 2 185 1 167 1 188 2 193 3 133 3 139 2 131 2 132 3 20 3 80 2 130 2 1...
output:
3019
result:
ok 1 number(s): "3019"
Test #75:
score: 0
Accepted
time: 23ms
memory: 3624kb
input:
142 3 368 2 351 2 420 3 369 3 459 2 421 2 446 3 460 3 469 2 447 2 465 1 447 1 487 2 468 2 466 3 470 3 512 2 469 2 515 3 513 3 616 2 516 2 564 3 617 3 625 2 565 2 591 3 626 3 635 2 592 2 607 3 636 3 717 2 658 2 635 1 656 1 693 2 717 2 659 3 718 3 742 2 731 2 718 1 694 1 739 2 735 2 732 3 743 3 749 2 ...
output:
128369
result:
ok 1 number(s): "128369"
Test #76:
score: 0
Accepted
time: 21ms
memory: 3664kb
input:
134 552 1 527 0 702 0 633 1 679 1 703 0 714 0 680 1 700 1 699 2 716 2 722 1 701 1 715 0 734 0 736 1 737 1 735 0 739 0 738 1 743 1 740 0 749 0 744 1 749 1 749 3 746 3 748 2 746 2 745 3 744 3 745 2 741 2 735 1 723 1 720 2 740 2 743 3 737 3 719 2 717 2 736 3 680 3 698 2 663 2 679 3 631 3 662 2 605 2 63...
output:
334697
result:
ok 1 number(s): "334697"
Test #77:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
20 0 0 10 0 10 10 9 10 9 9 8 9 8 10 7 10 7 7 6 7 6 10 5 10 5 5 4 5 4 10 3 10 3 3 2 3 2 10 0 10
output:
199
result:
ok 1 number(s): "199"
Test #78:
score: 0
Accepted
time: 57ms
memory: 3768kb
input:
200 0 0 100 0 100 100 99 100 99 99 98 99 98 100 97 100 97 97 96 97 96 100 95 100 95 95 94 95 94 100 93 100 93 93 92 93 92 100 91 100 91 91 90 91 90 100 89 100 89 89 88 89 88 100 87 100 87 87 86 87 86 100 85 100 85 85 84 85 84 100 83 100 83 83 82 83 82 100 81 100 81 81 80 81 80 100 79 100 79 79 78 79...
output:
263924743
result:
ok 1 number(s): "263924743"
Test #79:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
26 0 0 5 3 6 2 20 11 20 12 25 15 27 14 40 23 40 24 45 27 50 26 60 30 59 36 55 33 50 30 48 32 35 22 35 21 30 18 26 20 15 10 15 9 10 6 8 7 -3 2 0 -1
output:
4349
result:
ok 1 number(s): "4349"
Test #80:
score: 0
Accepted
time: 1ms
memory: 3376kb
input:
8 0 0 20 -10 40 0 40 5 60 0 60 -5 80 0 40 20
output:
39
result:
ok 1 number(s): "39"
Test #81:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
10 0 0 20 -10 40 0 45 0 40 5 60 0 65 0 60 -5 80 0 40 20
output:
61
result:
ok 1 number(s): "61"
Test #82:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
4 0 0 50 -20 100 0 50 20
output:
11
result:
ok 1 number(s): "11"
Test #83:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
8 0 0 0 10 -10 0 50 -20 110 0 100 10 100 0 50 -10
output:
27
result:
ok 1 number(s): "27"