QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#73945 | #5443. Security at Museums | yuto1115 | AC ✓ | 666ms | 5000kb | C++17 | 16.6kb | 2023-01-29 17:39:23 | 2023-01-29 17:39:24 |
Judging History
answer
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d)
#define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--)
#define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--)
#define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d)
#define rrep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SUM(a) accumulate(all(a),0LL)
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SORT(a) sort(all(a));
#define REV(a) reverse(all(a));
#define SZ(a) int(a.size())
#define popcount(x) __builtin_popcountll(x)
#define pf push_front
#define pb push_back
#define ef emplace_front
#define eb emplace_back
#define ppf pop_front
#define ppb pop_back
#ifdef __LOCAL
#define debug(...) { cout << #__VA_ARGS__; cout << ": "; print(__VA_ARGS__); cout << flush; }
#else
#define debug(...) void(0);
#endif
#define INT(...) int __VA_ARGS__;scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__)
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vp = vector<P>;
using vvp = vector<vp>;
using vlp = vector<LP>;
using vvlp = vector<vlp>;
template<class T>
using PQ = priority_queue<T>;
template<class T>
using PQrev = priority_queue<T, vector<T>, greater<T>>;
template<class S, class T>
istream &operator>>(istream &is, pair<S, T> &p) { return is >> p.first >> p.second; }
template<class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << '{' << p.first << ", " << p.second << '}'; }
template<class S, class T, class U>
istream &operator>>(istream &is, tuple<S, T, U> &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); }
template<class S, class T, class U>
ostream &operator<<(ostream &os, const tuple<S, T, U> &t) {
return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}';
}
template<class T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &t: v) { is >> t; }
return is;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
os << '[';
rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", ");
return os << ']';
}
template<class T>
ostream &operator<<(ostream &os, const deque<T> &v) {
os << '[';
rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", ");
return os << ']';
}
template<class T>
ostream &operator<<(ostream &os, const set<T> &st) {
os << '{';
auto it = st.begin();
while (it != st.end()) {
os << (it == st.begin() ? "" : ", ") << *it;
it++;
}
return os << '}';
}
template<class T>
ostream &operator<<(ostream &os, const multiset<T> &st) {
os << '{';
auto it = st.begin();
while (it != st.end()) {
os << (it == st.begin() ? "" : ", ") << *it;
it++;
}
return os << '}';
}
template<class T, class U>
ostream &operator<<(ostream &os, const map<T, U> &mp) {
os << '{';
auto it = mp.begin();
while (it != mp.end()) {
os << (it == mp.begin() ? "" : ", ") << *it;
it++;
}
return os << '}';
}
template<class T>
void vecout(const vector<T> &v, char div = '\n') {
rep(i, v.size()) cout << v[i] << (i == int(v.size() - 1) ? '\n' : div);
}
template<class T>
bool constexpr chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool constexpr chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
void scan() {}
template<class Head, class... Tail>
void scan(Head &head, Tail &... tail) {
cin >> head;
scan(tail...);
}
template<class T>
void print(const T &t) { cout << t << '\n'; }
template<class Head, class... Tail>
void print(const Head &head, const Tail &... tail) {
cout << head << ' ';
print(tail...);
}
template<class... T>
void fin(const T &... a) {
print(a...);
exit(0);
}
template<class T>
vector<T> &operator+=(vector<T> &v, T x) {
for (T &t: v) t += x;
return v;
}
template<class T>
vector<T> &operator-=(vector<T> &v, T x) {
for (T &t: v) t -= x;
return v;
}
template<class T>
vector<T> &operator*=(vector<T> &v, T x) {
for (T &t: v) t *= x;
return v;
}
template<class T>
vector<T> &operator/=(vector<T> &v, T x) {
for (T &t: v) t /= x;
return v;
}
struct Init_io {
Init_io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << boolalpha << fixed << setprecision(15);
cerr << boolalpha << fixed << setprecision(15);
}
} init_io;
const string yes[] = {"no", "yes"};
const string Yes[] = {"No", "Yes"};
const string YES[] = {"NO", "YES"};
const int inf = 1001001001;
const ll linf = 1001001001001001001;
void rearrange(const vi &) {}
template<class T, class... Tail>
void rearrange(const vi &ord, vector<T> &head, Tail &...tail) {
assert(ord.size() == head.size());
vector<T> ori = head;
rep(i, ord.size()) head[i] = ori[ord[i]];
rearrange(ord, tail...);
}
template<class T, class... Tail>
void sort_by(vector<T> &head, Tail &... tail) {
vi ord(head.size());
iota(all(ord), 0);
sort(all(ord), [&](int i, int j) { return head[i] < head[j]; });
rearrange(ord, head, tail...);
}
bool in_rect(int i, int j, int h, int w) {
return 0 <= i and i < h and 0 <= j and j < w;
}
template<class T, class S>
vector<T> cumsum(const vector<S> &v, bool shift_one = true) {
int n = v.size();
vector<T> res;
if (shift_one) {
res.resize(n + 1);
rep(i, n) res[i + 1] = res[i] + v[i];
} else {
res.resize(n);
if (n) {
res[0] = v[0];
rep(i, 1, n) res[i] = res[i - 1] + v[i];
}
}
return res;
}
vvi graph(int n, int m, bool directed = false, int origin = 1) {
vvi G(n);
rep(_, m) {
INT(u, v);
u -= origin, v -= origin;
G[u].pb(v);
if (!directed) G[v].pb(u);
}
return G;
}
template<class T>
vector<vector<pair<int, T>>> weighted_graph(int n, int m, bool directed = false, int origin = 1) {
vector<vector<pair<int, T>>> G(n);
rep(_, m) {
int u, v;
T w;
scan(u, v, w);
u -= origin, v -= origin;
G[u].eb(v, w);
if (!directed) G[v].eb(u, w);
}
return G;
}
template<int mod>
class modint {
ll x;
public:
constexpr modint(ll x = 0) : x((x % mod + mod) % mod) {}
static constexpr int get_mod() { return mod; }
constexpr int val() const { return x; }
constexpr modint operator-() const { return modint(-x); }
constexpr modint &operator+=(const modint &a) {
if ((x += a.val()) >= mod) x -= mod;
return *this;
}
constexpr modint &operator++() { return *this += 1; }
constexpr modint &operator-=(const modint &a) {
if ((x += mod - a.val()) >= mod) x -= mod;
return *this;
}
constexpr modint &operator--() { return *this -= 1; }
constexpr modint &operator*=(const modint &a) {
(x *= a.val()) %= mod;
return *this;
}
constexpr modint operator+(const modint &a) const {
modint res(*this);
return res += a;
}
constexpr modint operator-(const modint &a) const {
modint res(*this);
return res -= a;
}
constexpr modint operator*(const modint &a) const {
modint res(*this);
return res *= a;
}
constexpr modint pow(ll t) const {
modint res = 1, a(*this);
while (t > 0) {
if (t & 1) res *= a;
t >>= 1;
a *= a;
}
return res;
}
template<int m>
friend istream &operator>>(istream &, modint<m> &);
// for prime mod
constexpr modint inv() const { return pow(mod - 2); }
constexpr modint &operator/=(const modint &a) { return *this *= a.inv(); }
constexpr modint operator/(const modint &a) const {
modint res(*this);
return res /= a;
}
// constraints : mod = 2 or val = 0 or val^((mod-1)/2) ≡ 1
// mod is prime
// time complexity : O(log^2 p)
// reference : https://nyaannyaan.github.io/library/modulo/mod-sqrt.hpp
modint sqrt() const {
if (x < 2) return x;
assert(this->pow((mod - 1) >> 1).val() == 1);
modint b = 1;
while (b.pow((mod - 1) >> 1).val() == 1) b += 1;
ll m = mod - 1, e = 0;
while (~m & 1) m >>= 1, e += 1;
modint X = this->pow((m - 1) >> 1);
modint Y = (*this) * X * X;
X *= *this;
modint Z = b.pow(m);
while (Y.val() != 1) {
ll j = 0;
modint t = Y;
while (t.val() != 1) {
j += 1;
t *= t;
}
Z = Z.pow(1LL << (e - j - 1));
X *= Z;
Z *= Z;
Y *= Z;
e = j;
}
return X;
}
};
using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1000000007>;
template<int mod>
istream &operator>>(istream &is, modint<mod> &a) {
ll x;
is >> x;
a = modint<mod>(x);
return is;
}
template<int mod>
constexpr ostream &operator<<(ostream &os, const modint<mod> &a) { return os << a.val(); }
template<int mod>
constexpr bool operator==(const modint<mod> &a, const modint<mod> &b) { return a.val() == b.val(); }
template<int mod>
constexpr bool operator!=(const modint<mod> &a, const modint<mod> &b) { return a.val() != b.val(); }
template<int mod>
constexpr modint<mod> &operator++(modint<mod> &a) { return a += 1; }
template<int mod>
constexpr modint<mod> &operator--(modint<mod> &a) { return a -= 1; }
using mint = modint998244353;
using vm = vector<mint>;
using vvm = vector<vm>;
using point = LP;
ll cross(const point &a, const point &b) {
return a.first * b.second - a.second * b.first;
}
ll dot(const point &a, const point &b) {
return a.first * b.first + a.second * b.second;
}
ll norm(const point &p) {
return p.first * p.first + p.second * p.second;
}
int sgn(ll l) {
if (l < 0) return -1;
if (l == 0) return 0;
return 1;
}
int ccw(const point &a, const point &b, const point &c) {
// 1 -> c is upper than line(a,b)
// -1 -> c is lower than line(a,b)
// 2 -> in order [a,b,c]
// -2 -> in order [c,a,b]
// 0 -> in order [a,c,b]
point nb = {b.first - a.first, b.second - a.second};
point nc = {c.first - a.first, c.second - a.second};
if (sgn(cross(nb, nc))) return sgn(cross(nb, nc));
if (sgn(dot(nb, nc)) < 0) return -2;
if (sgn(norm(nc) - norm(nb)) > 0) return 2;
return 0;
}
struct segment {
point a, b;
segment(point a = point(), point b = point()) : a(a), b(b) {}
bool online(const point &p) const { return !ccw(a, b, p); }
};
ostream &operator<<(ostream &os, const segment &l) { return os << '{' << l.a << ',' << l.b << '}'; }
bool intersect(const segment &l, const segment &m) {
return ccw(l.a, l.b, m.a) * ccw(l.a, l.b, m.b) <= 0 &&
ccw(m.a, m.b, l.a) * ccw(m.a, m.b, l.b) <= 0;
}
// [-pi, pi)
// no (0, 0)
bool arg_cmp(const LP &a, const LP &b) {
int ua = a.second > 0 or (a.second == 0 and a.first > 0);
int ub = b.second > 0 or (b.second == 0 and b.first > 0);
if (ua == ub) {
ll cross = a.first * b.second - a.second * b.first;
return cross > 0;
} else {
return ua < ub;
}
}
int main() {
INT(n);
vl x(n), y(n);
rep(i, n) scan(x[i], y[i]);
vector<point> pt(n);
rep(i, n) pt[i] = {x[i], y[i]};
vvi dir(n, vi(n, -1));
{
vector<tuple<int, int, LP>> tmp;
rep(i, n) rep(j, n) {
if (i == j) continue;
tmp.eb(i, j, LP{x[j] - x[i], y[j] - y[i]});
}
sort(all(tmp), [](auto a, auto b) { return arg_cmp(get<2>(a), get<2>(b)); });
int now = -1;
rep(i, SZ(tmp)) {
if (i == 0 or arg_cmp(get<2>(tmp[i - 1]), get<2>(tmp[i]))) ++now;
dir[get<0>(tmp[i])][get<1>(tmp[i])] = now;
}
}
debug(dir);
// is k in [i,j](ccw)?
auto in_int = [](int i, int j, int k) {
if (i <= j) return i <= k and k <= j;
else return i <= k or k <= j;
};
vvi ok(n, vi(n, true));
rep(i, n) rep(j, i + 1, n) {
rep(_, 2) {
int a = (i + n - 1) % n;
int b = (i + 1) % n;
ok[i][j] &= in_int(dir[i][b], dir[i][a], dir[i][j]);
swap(i, j);
}
segment s(pt[i], pt[j]);
rep(k, n) {
int a = k;
int b = (k + 1) % n;
if (s.online(pt[a])) continue;
if (s.online(pt[b])) continue;
segment t(pt[a], pt[b]);
ok[i][j] &= !intersect(s, t);
}
rep(k, n) {
if (i == k or j == k) continue;
if (!s.online(pt[k])) continue;
int a = (k + n - 1) % n;
int b = (k + 1) % n;
ok[i][j] &= in_int(dir[k][b], dir[k][a], dir[k][i]);
ok[i][j] &= in_int(dir[k][b], dir[k][a], dir[k][j]);
}
ok[i][j] = ok[j][i] = (ok[i][j] & ok[j][i]);
}
mint ans;
auto convex_low = [&](int s) -> vm {
vp eg;
rep(i, n) rep(j, n) if (i != j) {
if (!ok[i][j]) continue;
if (!arg_cmp({0, -1}, {x[j] - x[i], y[j] - y[i]})) continue;
if (arg_cmp({0, 1}, {x[j] - x[i], y[j] - y[i]})) continue;
eg.eb(i, j);
}
sort(all(eg),
[&](P a, P b) {
auto [ai, aj] = a;
auto [bi, bj] = b;
if (dir[ai][aj] != dir[bi][bj]) return dir[ai][aj] < dir[bi][bj];
return pt[ai] < pt[bi];
});
vm dp(n);
dp[s] = 1;
for (auto [i, j]: eg) {
dp[j] += dp[i];
}
return dp;
};
auto convex_up = [&](int s) -> vm {
vp eg;
rep(i, n) rep(j, n) if (i != j) {
if (!ok[i][j]) continue;
if (!arg_cmp({0, -1}, {x[j] - x[i], y[j] - y[i]})) continue;
if (arg_cmp({0, 1}, {x[j] - x[i], y[j] - y[i]})) continue;
eg.eb(i, j);
}
sort(all(eg),
[&](P a, P b) {
auto [ai, aj] = a;
auto [bi, bj] = b;
if (dir[ai][aj] != dir[bi][bj]) return dir[ai][aj] > dir[bi][bj];
return pt[ai] < pt[bi];
});
vm dp(n);
dp[s] = 1;
for (auto [i, j]: eg) {
dp[j] += dp[i];
}
return dp;
};
rep(s, n) {
vm dpl = convex_low(s);
vm dpu = convex_up(s);
debug(s);
debug(dpl);
debug(dpu);
rep(t, n) {
if (s == t) continue;
ans += dpl[t] * dpu[t];
}
}
rep(s, n) rep(t, s + 1, n) {
if (!ok[s][t]) continue;
int cnt = 0;
rep(i, n) {
if (i == s or i == t) continue;
if (segment(pt[s], pt[t]).online(pt[i])) ++cnt;
}
ans -= mint(4).pow(cnt);
ans += mint(2).pow(cnt);
}
fin(ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3492kb
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: 0ms
memory: 3368kb
input:
3 0 2022 -2022 -2022 2022 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
3 4 0 0 3 0 0
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3316kb
input:
3 -10 0 10 0 0 18
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3416kb
input:
4 0 0 -10 0 -10 -10 0 -10
output:
11
result:
ok 1 number(s): "11"
Test #6:
score: 0
Accepted
time: 2ms
memory: 3372kb
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: 3316kb
input:
4 0 0 10 5 20 0 10 10
output:
7
result:
ok 1 number(s): "7"
Test #8:
score: 0
Accepted
time: 1ms
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: 2ms
memory: 3268kb
input:
4 -100 -10 100 -10 100 10 -100 10
output:
11
result:
ok 1 number(s): "11"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
4 0 0 100 0 60 30 0 30
output:
11
result:
ok 1 number(s): "11"
Test #11:
score: 0
Accepted
time: 2ms
memory: 3312kb
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: 3312kb
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: 3320kb
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: 3420kb
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: 3488kb
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: 2ms
memory: 3444kb
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: 0ms
memory: 3284kb
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: 3376kb
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: 3376kb
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: 1ms
memory: 3364kb
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: 2ms
memory: 3492kb
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: 3408kb
input:
3 1000000 -1000000 1000000 1000000 -1000000 -1000000
output:
4
result:
ok 1 number(s): "4"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3368kb
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: 3416kb
input:
4 1000000 -1000000 1000000 1000000 0 1 -1000000 -1000000
output:
11
result:
ok 1 number(s): "11"
Test #25:
score: 0
Accepted
time: 666ms
memory: 4980kb
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: 662ms
memory: 4944kb
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: 186ms
memory: 4960kb
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: 246ms
memory: 4952kb
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: 0ms
memory: 3432kb
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: 2ms
memory: 3480kb
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: 3504kb
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: 0ms
memory: 3432kb
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: 1ms
memory: 3440kb
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: 104ms
memory: 4948kb
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: 111ms
memory: 4860kb
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: 100ms
memory: 4864kb
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: 102ms
memory: 4848kb
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: 105ms
memory: 4952kb
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: 107ms
memory: 4948kb
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: 110ms
memory: 4948kb
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: 102ms
memory: 4976kb
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: 104ms
memory: 4880kb
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: 104ms
memory: 4864kb
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: 2ms
memory: 3312kb
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: 2ms
memory: 3424kb
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: 1ms
memory: 3368kb
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: 1ms
memory: 3500kb
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: 3436kb
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: 3432kb
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: 3496kb
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: 179ms
memory: 4948kb
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: 178ms
memory: 4872kb
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: 174ms
memory: 4872kb
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: 179ms
memory: 4980kb
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: 172ms
memory: 4868kb
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: 190ms
memory: 4952kb
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: 175ms
memory: 4948kb
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: 186ms
memory: 5000kb
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: 180ms
memory: 4956kb
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: 1ms
memory: 3412kb
input:
4 -899998 -900000 0 0 450000 450001 449998 449999
output:
7
result:
ok 1 number(s): "7"
Test #61:
score: 0
Accepted
time: 0ms
memory: 3480kb
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: 3496kb
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: 0ms
memory: 3420kb
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: 114ms
memory: 4972kb
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: 114ms
memory: 4848kb
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: 100ms
memory: 4912kb
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: 121ms
memory: 4928kb
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: 104ms
memory: 4884kb
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: 3ms
memory: 3572kb
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: 6ms
memory: 3564kb
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: 5ms
memory: 3492kb
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: 11ms
memory: 3656kb
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: 19ms
memory: 3664kb
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: 3660kb
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: 47ms
memory: 4136kb
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: 45ms
memory: 4140kb
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: 2ms
memory: 3444kb
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: 115ms
memory: 4800kb
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: 2ms
memory: 3480kb
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: 2ms
memory: 3372kb
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: 2ms
memory: 3424kb
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: 2ms
memory: 3496kb
input:
4 0 0 50 -20 100 0 50 20
output:
11
result:
ok 1 number(s): "11"
Test #83:
score: 0
Accepted
time: 2ms
memory: 3368kb
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"