QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#564809 | #8858. Map Tiles | crimson231 | AC ✓ | 291ms | 5388kb | C++23 | 13.3kb | 2024-09-15 14:47:39 | 2024-09-15 14:47:40 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <vector>
#include <queue>
typedef long long ll;
//typedef long double ld;
typedef double ld;
const ll INF = 1e17;
const int LEN = 20;
const ld TOL = 1e-7;
inline int sign(const ld& x) { return x < -TOL ? -1 : x > TOL; }
inline bool zero(const ld& x) { return !sign(x); }
#define __FUCK__ ;
int N, xs, ys;
int MAXX, MAXY, MINX, MINY;
short int board[LEN][LEN];
struct Pii {
int x, y;
inline Pii(int X = 0, int Y = 0) : x(X), y(Y) {}
inline bool operator == (const Pii& p) const { return x == p.x && y == p.y; }
inline bool operator < (const Pii& p) const { return x == p.x ? y < p.y : x < p.x; }
inline Pii operator + (const Pii& p) const { return { x + p.x, y + p.y }; }
inline Pii operator - (const Pii& p) const { return { x - p.x, y - p.y }; }
inline Pii operator * (const int& n) const { return { x * n, y * n }; }
inline Pii operator / (const int& n) const { return { x / n, y / n }; }
inline ll operator * (const Pii& p) const { return (ll)x * p.x + (ll)y * p.y; }
inline ll operator / (const Pii& p) const { return (ll)x * p.y - (ll)y * p.x; }
inline Pii& operator += (const Pii& p) { x += p.x; y += p.y; return *this; }
inline Pii& operator -= (const Pii& p) { x -= p.x; y -= p.y; return *this; }
inline ll Euc() const { return (ll)x * x + (ll)y * y; }
inline friend std::istream& operator >> (std::istream& is, Pii& p) { is >> p.x >> p.y; return is; }
inline friend std::ostream& operator << (std::ostream& os, const Pii& p) { os << p.x << " " << p.y; return os; }
}; const Pii Oii = Pii(0, 0);
typedef std::vector<Pii> Polygon;
inline ll cross(const Pii& d1, const Pii& d2, const Pii& d3) { return (d2 - d1) / (d3 - d2); }
inline ll cross(const Pii& d1, const Pii& d2, const Pii& d3, const Pii& d4) { return (d2 - d1) / (d4 - d3); }
inline int ccw(const Pii& d1, const Pii& d2, const Pii& d3) { ll ret = cross(d1, d2, d3); return ret < 0 ? -1 : !!ret; }
inline ll area(const Polygon& H) {
ll ret = 0;
int sz = H.size();
for (int i = 0; i < sz; i++) ret += H[i] / H[(i + 1) % sz];
return ret;
}
inline void norm(Polygon& H) {
ll A = area(H); assert(A);
if (A < 0) std::reverse(H.begin(), H.end());
auto s = std::min_element(H.begin(), H.end());
std::rotate(H.begin(), s, H.end());
return;
}
inline Polygon graham_scan(Polygon& C) {
Polygon H;
if (C.size() < 3) {
std::sort(C.begin(), C.end());
return C;
}
std::swap(C[0], *min_element(C.begin(), C.end()));
std::sort(C.begin() + 1, C.end(), [&](const Pii& p, const Pii& q) -> bool {
int ret = ccw(C[0], p, q);
if (!ret) return (C[0] - p).Euc() < (C[0] - q).Euc();
return ret > 0;
}
);
C.erase(unique(C.begin(), C.end()), C.end());
int sz = C.size();
for (int i = 0; i < sz; i++) {
while (H.size() >= 2 && ccw(H[H.size() - 2], H.back(), C[i]) <= 0)
H.pop_back();
H.push_back(C[i]);
}
return H;
}
inline bool inner_check(const Polygon& H, const Pii& p) {
int sz = H.size();
for (int i = 0; i < sz; i++) if (ccw(H[i], H[(i + 1) % sz], p) < 0) return 0;
return 1;
}
inline int bfs(const int& x, const int& y, const int& val) {//flood fill
Pii DRC[4] = { Pii(1, 0), Pii(0, 1), Pii(-1, 0), Pii(0, -1) };
std::queue<Pii> Q;
Q.push(Pii(x, y));
board[y][x] = val;
int cnt = 1;
while (Q.size()) {
Pii p = Q.front(); Q.pop();
for (int i = 0; i < 4; i++) {
Pii w = p + DRC[i];
if ((MINX <= w.x) && (w.x <= MAXX) && (MINY <= w.y) && (w.y <= MAXY) && !board[w.y][w.x]) {
Q.push(w);
board[w.y][w.x] = val;
cnt++;
}
}
}
return cnt;
}
struct Pos {
ld x, y;
inline Pos(ld X = 0, ld Y = 0) : x(X), y(Y) {}
inline bool operator == (const Pos& p) const { return zero(x - p.x) && zero(y - p.y); }
inline bool operator < (const Pos& p) const { return zero(x - p.x) ? y < p.y : x < p.x; }
inline Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
inline Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
inline Pos operator * (const ld& scalar) const { return { x * scalar, y * scalar }; }
inline Pos operator / (const ld& scalar) const { return { x / scalar, y / scalar }; }
inline ld operator * (const Pos& p) const { return x * p.x + y * p.y; }
inline ld operator / (const Pos& p) const { return x * p.y - y * p.x; }
inline Pos& operator += (const Pos& p) { x += p.x; y += p.y; return *this; }
inline Pos& operator -= (const Pos& p) { x -= p.x; y -= p.y; return *this; }
}; const Pos O = Pos(0, 0);
typedef std::vector<Pos> Polygonf;
inline ld cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
inline ld dot(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) * (d3 - d2); }
inline int ccw(const Pos& d1, const Pos& d2, const Pos& d3) { ld ret = cross(d1, d2, d3); return sign(ret); }
inline bool on_seg_strong(const Pos& d1, const Pos& d2, const Pos& d3) { ld ret = dot(d1, d3, d2); return !ccw(d1, d2, d3) && sign(ret) >= 0; }
inline Pos intersection(const Pos& p1, const Pos& p2, const Pos& q1, const Pos& q2) { ld a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2); return (p1 * a2 + p2 * a1) / (a1 + a2); }
inline bool inner_check(const Polygonf& H, const Pos& p) {//concave
int sz = H.size(), cnt = 0;
for (int i = 0; i < sz; i++) {
Pos cur = H[i], nxt = H[(i + 1) % sz];
if (on_seg_strong(cur, nxt, p)) return 1;
if (cur.y == nxt.y) continue;
if (nxt.y < cur.y) std::swap(cur, nxt);
if (nxt.y - TOL < p.y || cur.y > p.y) continue;
cnt += ccw(cur, nxt, p) > 0;
}
return cnt & 1;
}
inline Pos P(const Pii& p) { return Pos((ld)p.x, (ld)p.y); }
inline Pii P(const Pos& p) { return Pii(p.x + TOL, p.y + TOL); }
inline Pos cen(const int& i, const int& j, const int& xs, const int& ys) { return Pos(xs * (j + .5), ys * (i + .5)); }
inline Pos norm(Pos& p, const int& x, const int& y) {//fit in tile (0, 0), (xs, ys)
while (sign(p.x) < 0) p.x += x;
while (sign(p.x - x) >= 0) p.x -= x;
while (sign(p.y) < 0) p.y += y;
while (sign(p.y - y) >= 0) p.y -= y;
return p;
}
inline void norm(int& x, const int& vx, const int& xs) {
while (x <= (vx - xs)) x += xs;
while (x > vx) x -= xs;
return;
}
inline void norm(int& x, const ld& vx, const int& xs) {
while (sign(x - (vx - xs)) <= 0) x += xs;
while (sign(x - vx) > 0) x -= xs;
return;
}
void sweep(const Pos& cur, const Pos& nxt, const int& xs, const int& ys) {//from 6632 arable
int sx = 0, ex = 0, sy = 0, ey = 0;
norm(sx, cur.x, xs);
norm(ex, nxt.x, xs);
norm(sy, cur.y, ys);
norm(ey, nxt.y, ys);
Pos d = nxt - cur;
if (zero(d.x)) {
if (sign(d.y) > 0) {
if (zero(ey - nxt.y)) ey -= ys;
if (zero(cur.x - sx) && zero(nxt.x - ex)) for (int i = sy; i <= ey; i += ys) board[i / ys][sx / xs - 1] = 1;
else for (int i = sy; i <= ey; i += ys) board[i / ys][sx / xs] = 1;
}
else if (sign(d.y) < 0) {
if (zero(sy - cur.y)) sy -= ys;
for (int i = ey; i <= sy; i += xs) board[i / ys][sx / xs] = 1;
}
return;
}
if (zero(d.y)) {
if (sign(d.x) > 0) {
if (zero(ex - nxt.x)) ex -= xs;
for (int i = sx; i <= ex; i += xs) board[sy / ys][i / xs] = 1;
}
else if (sign(d.x) < 0) {
if (zero(sx - cur.x)) sx -= xs;
if (zero(cur.y - sy) && zero(nxt.y - ey)) for (int i = ex; i <= sx; i += xs) board[sy / ys - 1][i / xs] = 1;
else for (int i = ex; i <= sx; i += xs) board[sy / ys][i / xs] = 1;
}
return;
}
Pos s = cur, e = nxt;
if (e < s) std::swap(s, e), std::swap(sx, ex), std::swap(sy, ey);
int j = sx, i = sy;
if (zero(e.x - ex)) ex -= xs;
if (sign(std::abs(e.x - s.x) - std::abs(e.y - s.y)) >= 0) {
if (s.y < e.y) {
board[i / ys][j / xs] = 1;
if (zero(e.y - ey)) ey -= ys;
while (i <= ey) {
while (j <= ex && ccw(s, e, Pos((ld)j, (ld)i + ys)) > 0 && ccw(s, e, Pos((ld)j + xs, (ld)i)) < 0) {
board[i / ys][j / xs] = 1;
j += xs;
}
if (ccw(s, e, Pos((ld)j - xs, (ld)i + 2. * ys)) > 0 && ccw(s, e, Pos(j, (ld)i + ys)) < 0) j -= xs;
i += ys;
}
}
else if (s.y > e.y) {
board[i / ys - zero(s.y - sy)][j / xs] = 1;
if (!zero(s.y - sy)) sy += ys, i += ys;
while (i > ey) {
while (j <= ex && ccw(s, e, Pos((ld)j + xs, (ld)i)) > 0 && ccw(s, e, Pos(j, (ld)i - ys)) < 0) {
board[i / ys - 1][j / xs] = 1;
j += xs;
}
if (ccw(s, e, Pos(j, (ld)i - ys)) > 0 && ccw(s, e, Pos((ld)j - xs, (ld)i - 2. * ys)) < 0) j -= xs;
i -= ys;
}
}
}
else {
if (s.y < e.y) {
board[i / ys][j / xs] = 1;
if (zero(e.y - ey)) ey -= ys;
while (j <= ex) {
while (i <= ey && ccw(s, e, Pos((ld)j, (ld)i + ys)) > 0 && ccw(s, e, Pos((ld)j + xs, (ld)i)) < 0) {
board[i / ys][j / xs] = 1;
i += ys;
}
if (ccw(s, e, Pos((ld)j + xs, (ld)i)) > 0 && ccw(s, e, Pos((ld)j + 2. * xs, (ld)i - ys)) < 0) i -= ys;
j += xs;
}
}
else if (s.y > e.y) {
board[i / ys - zero(s.y - sy)][j / xs] = 1;
if (!zero(s.y - sy)) sy += ys, i += ys;
while (j <= ex) {
while (i > ey && ccw(s, e, Pos((ld)j + xs, (ld)i)) > 0 && ccw(s, e, Pos((ld)j, (ld)i - ys)) < 0) {
board[i / ys - 1][j / xs] = 1;
i -= ys;
}
if (ccw(s, e, Pos((ld)j + 2. * xs, (ld)i + ys)) > 0 && ccw(s, e, Pos((ld)j + xs, (ld)i)) < 0) i += ys;
j += xs;
}
}
}
return;
}
int sweep(const Polygonf& HF, const int& xs, const int& ys) {
memset(board, 0, sizeof board);
ld lx = 1e9, rx = -1e9, ly = 1e9, uy = -1e9;
int sz = HF.size();
for (int i = 0; i < sz; i++) {
lx = std::min(lx, HF[i].x);
rx = std::max(rx, HF[i].x);
ly = std::min(ly, HF[i].y);
uy = std::max(uy, HF[i].y);
const Pos& cur = HF[i], & nxt = HF[(i + 1) % sz];
sweep(cur, nxt, xs, ys);
}
MAXX = (int)rx / xs;
MINX = (int)lx / xs;
MAXY = (int)uy / ys;
MINY = (int)ly / ys;
MAXX += 2;
MAXY += 2;
for (int i = MINY; i <= MAXY; i++) {
for (int j = MINX; j <= MAXX; j++) {
if (!board[i][j]) {
if (inner_check(HF, cen(i, j, xs, ys))) bfs(j, i, 1);
else bfs(j, i, 2);
}
}
}
int cnt = 0;
for (int i = MINY; i <= MAXY; i++) {
for (int j = MINX; j <= MAXX; j++) {
assert(board[i][j]);
if (board[i][j] == 1) cnt++;
}
}
return cnt;
}
void solve() {
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
std::cout << std::fixed;
std::cout.precision(7);
std::cin >> N >> xs >> ys;
Polygon H(N);
Polygonf V;//All possible point
for (int i = 0; i < N; i++) std::cin >> H[i];
norm(H);
Pii S = H[0];
for (int i = 0; i < N; i++) {//O(50)
for (int j = 0; j < N; j++) {//O(50 * 50)
Pii I = H[i], J = H[j], K = H[(j + 1) % N];
int x = I.x, y = J.y;
Pos v = P(S - Pii(x, y));
V.push_back(norm(v, xs, ys));
if (J.x != K.x) {
if (J.x > K.x) std::swap(J, K);
int jx = I.x;
norm(jx, J.x, xs);
int kx = I.x;
norm(kx, K.x, xs);
Pii vec = K - J;
for (int kw = jx; kw <= kx; kw += xs) {//O(50 * 50 * 20)
if (kw < J.x || K.x < kw) continue;
ld yh = J.y + ((ld)kw - J.x) * vec.y / vec.x;
v = P(S) - Pos(I.x, yh);
V.push_back(norm(v, xs, ys));
}
}
I = H[i], J = H[j], K = H[(j + 1) % N];
x = J.x, y = I.y;
v = P(S - Pii(x, y));
V.push_back(norm(v, xs, ys));
if (J.y != K.y) {
if (J.y > K.y) std::swap(J, K);
int jy = I.y;
norm(jy, J.y, ys);
int ky = I.y;
norm(ky, K.y, ys);
Pii vec = K - J;
for (int kh = jy; kh <= ky; kh += ys) {//O(50 * 50 * 20)
if (kh < J.y || K.y < kh) continue;
ld yw = J.x + ((ld)kh - J.y) * vec.x / vec.y;
v = P(S) - Pos(yw, I.y);
V.push_back(norm(v, xs, ys));
}
}
}
}
std::sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
for (int i = 0; i < N; i++) {//O(50)
Pii I1 = H[i], I2 = H[(i + 1) % N];
for (int j = 0; j < N; j++) {//O(50 * 50)
Pii J1 = H[j], J2 = H[(j + 1) % N];
if (i == j || !cross(I1, I2, J1, J2)) continue;
Pii vec = I2 - I1;
if (J2 < J1) std::swap(J1, J2);
Polygon box = { J1, J1 - vec, J2, J2 - vec };
box = graham_scan(box);
assert(box.size() == 4);
int lx = 1e9, rx = -1e9, ly = 1e9, uy = -1e9;
for (int k = 0; k < 4; k++) {
lx = std::min(lx, box[k].x);
rx = std::max(rx, box[k].x);
ly = std::min(ly, box[k].y);
uy = std::max(uy, box[k].y);
}
int jx = I1.x;
norm(jx, lx, xs);
int jy = I1.y;
norm(jy, ly, ys);
for (int x = jx; x <= rx; x += xs) {//O(50 * 50 * 20)
for (int y = jy; y <= uy; y += ys) {//O(50 * 50 * 20 * 20)
if (inner_check(box, Pii(x, y))) {//O(50 * 50 * 20 * 20 * 4) == O(4000000)
Pos o = intersection(P(J1), P(J2), Pos(x, y), Pos(x, y) + P(vec));
Pos v = P(S) - o;
V.push_back(norm(v, xs, ys));
}
}
}
}
}
std::sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
Polygonf C(N);
for (int i = 0; i < N; i++) C[i] = P(H[i]);
int sz = V.size();
int cnt = 1e6;
for (int z = 0; z < sz; z++) {//O(50 * 50 * 20 * 20 * 4) == O(4000000)
const Pos& s = V[z];
Polygonf HF = C;
Pos v = s - HF[0];
ld miny = 1e9;
for (int i = 0; i < N; i++) HF[i] += v, miny = std::min(miny, HF[i].y);
int y = 0; norm(y, miny, ys);
for (int i = 0; i < N; i++) HF[i].y -= y, HF[i] += Pos(xs, ys);
cnt = std::min(cnt, sweep(HF, xs, ys));//O(50 * 50 * 20 * 20 * 4 * 50) == O(2,0000,0000)
}
std::cout << cnt << "\n";
return;
}
int main() { solve(); return 0; }//boj8883
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3572kb
input:
12 9 9 1 8 1 16 6 16 9 29 19 31 23 24 30 23 29 18 20 12 22 8 14 0 14 8
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
4 5 7 10 10 15 10 15 17 10 17
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
12 9 9 2 17 2 25 7 25 10 38 20 40 24 33 31 32 30 27 21 21 23 17 15 9 15 17
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
4 5 7 11 12 16 12 16 19 11 19
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
12 4 3 0 0 0 12 8 12 8 9 4 9 4 3 8 3 8 6 12 6 12 12 16 12 16 0
output:
12
result:
ok single line: '12'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
12 4 3 0 0 0 12 8 12 8 9 4 9 4 4 8 3 8 6 12 6 12 12 16 12 16 0
output:
13
result:
ok single line: '13'
Test #7:
score: 0
Accepted
time: 3ms
memory: 3716kb
input:
12 5 6 2 2 50 3 49 5 4 41 16 39 6 46 9 55 49 23 46 16 50 9 49 59 3 60
output:
89
result:
ok single line: '89'
Test #8:
score: 0
Accepted
time: 3ms
memory: 3712kb
input:
12 6 5 2 2 3 50 5 49 41 4 39 16 46 6 55 9 23 49 16 46 9 50 59 49 60 3
output:
89
result:
ok single line: '89'
Test #9:
score: 0
Accepted
time: 50ms
memory: 3792kb
input:
46 98 79 468 612 408 594 421 658 439 616 469 744 9 464 113 776 314 771 169 735 481 768 513 709 780 506 799 751 702 715 596 788 818 760 832 595 967 753 948 511 875 545 975 385 964 47 924 139 886 5 489 8 478 23 302 5 319 78 608 140 510 274 694 386 641 219 700 241 708 193 898 267 884 500 493 490 383 34...
output:
80
result:
ok single line: '80'
Test #10:
score: 0
Accepted
time: 50ms
memory: 3832kb
input:
46 98 79 468 612 408 594 421 658 439 616 469 744 14 467 106 776 314 771 169 735 481 768 513 709 780 506 799 751 702 715 596 788 818 760 832 595 967 753 948 511 875 545 975 385 964 47 924 139 886 5 489 8 478 23 302 5 319 78 608 140 510 274 694 386 641 219 700 241 708 193 898 267 884 500 493 490 383 3...
output:
81
result:
ok single line: '81'
Test #11:
score: 0
Accepted
time: 48ms
memory: 3828kb
input:
46 79 98 612 468 594 408 658 421 616 439 744 469 464 9 776 113 771 314 735 169 768 481 709 513 506 780 751 799 715 702 788 596 760 818 595 832 753 967 511 948 545 875 385 975 47 964 139 924 5 886 8 489 23 478 5 302 78 319 140 608 274 510 386 694 219 641 241 700 193 708 267 898 500 884 490 493 345 38...
output:
80
result:
ok single line: '80'
Test #12:
score: 0
Accepted
time: 2ms
memory: 4008kb
input:
22 100 90 344 218 702 119 601 84 770 76 638 299 865 251 872 429 824 346 635 400 668 531 852 502 772 585 622 566 825 727 602 659 244 758 354 570 93 363 315 448 460 428 441 347 249 322
output:
45
result:
ok single line: '45'
Test #13:
score: 0
Accepted
time: 3ms
memory: 3708kb
input:
22 100 90 865 251 872 429 824 346 635 400 668 531 852 502 772 585 622 566 826 727 602 659 244 758 354 570 93 363 315 448 460 428 441 347 249 322 344 218 702 119 601 84 770 76 638 299
output:
46
result:
ok single line: '46'
Test #14:
score: 0
Accepted
time: 6ms
memory: 3764kb
input:
22 100 90 668 531 852 502 772 585 622 566 825 727 602 659 244 758 354 570 93 363 315 448 460 428 441 347 249 322 344 218 702 118 601 84 770 76 638 299 865 251 872 429 824 346 635 400
output:
46
result:
ok single line: '46'
Test #15:
score: 0
Accepted
time: 6ms
memory: 3812kb
input:
22 90 100 216 345 117 703 82 602 74 771 297 639 249 866 427 873 344 825 398 636 529 669 500 853 583 773 564 623 725 826 657 603 756 244 568 355 361 94 446 316 426 461 345 442 320 250
output:
45
result:
ok single line: '45'
Test #16:
score: 0
Accepted
time: 77ms
memory: 3800kb
input:
50 100 100 475 951 448 474 379 489 326 357 105 665 172 482 30 540 59 297 253 309 89 424 271 315 231 37 404 53 283 139 273 337 115 431 289 334 132 448 576 153 650 215 606 54 744 302 845 182 737 403 943 219 815 623 943 340 844 696 648 561 761 536 799 422 755 450 455 466 489 934 693 679 550 954 997 942...
output:
95
result:
ok single line: '95'
Test #17:
score: 0
Accepted
time: 74ms
memory: 3752kb
input:
50 100 100 289 334 132 449 576 153 650 215 606 54 744 302 845 182 737 403 943 219 815 623 943 340 844 696 648 561 761 536 799 422 755 450 455 466 489 934 693 679 550 954 997 942 960 406 997 277 908 374 995 165 791 336 995 104 732 218 996 15 542 5 618 156 507 14 25 4 23 940 475 951 448 474 379 489 32...
output:
96
result:
ok single line: '96'
Test #18:
score: 0
Accepted
time: 76ms
memory: 3848kb
input:
50 100 100 951 525 474 552 489 621 357 674 665 895 482 828 540 970 297 941 309 747 424 911 315 729 37 769 53 596 139 717 337 727 431 885 334 711 448 868 153 424 215 350 54 394 302 256 182 155 403 263 219 57 623 185 340 57 696 156 561 352 536 239 422 201 450 245 466 545 934 511 679 307 954 450 942 3 ...
output:
95
result:
ok single line: '95'
Test #19:
score: 0
Accepted
time: 12ms
memory: 3732kb
input:
19 73 97 50 37 380 532 370 732 713 791 263 908 104 409 18 2 501 124 701 293 440 595 608 319 601 234 430 119 24 11 294 832 571 798 316 772 328 520 308 430
output:
54
result:
ok single line: '54'
Test #20:
score: 0
Accepted
time: 12ms
memory: 3728kb
input:
19 73 97 294 832 571 798 316 772 328 520 308 430 50 37 380 533 370 732 713 791 263 908 104 409 18 2 501 124 701 293 440 595 608 319 601 234 430 119 24 11
output:
54
result:
ok single line: '54'
Test #21:
score: 0
Accepted
time: 12ms
memory: 3740kb
input:
19 97 73 430 308 520 328 772 316 798 571 832 294 11 24 119 430 234 601 319 608 595 440 293 701 124 501 2 18 409 104 908 263 791 713 732 370 532 380 37 50
output:
54
result:
ok single line: '54'
Test #22:
score: 0
Accepted
time: 9ms
memory: 3728kb
input:
19 97 73 430 308 520 328 772 316 798 571 832 294 11 24 119 430 234 601 319 608 595 440 293 701 124 501 2 18 409 104 908 263 791 714 732 370 532 380 37 50
output:
55
result:
ok single line: '55'
Test #23:
score: 0
Accepted
time: 8ms
memory: 3988kb
input:
26 18 36 65 150 121 332 116 319 97 279 124 342 26 3 11 204 47 232 95 296 35 81 36 105 21 164 24 186 33 144 50 144 65 203 36 165 55 205 72 247 90 285 76 256 13 191 16 155 24 125 35 60 35 64
output:
31
result:
ok single line: '31'
Test #24:
score: 0
Accepted
time: 46ms
memory: 3780kb
input:
50 6 76 30 430 33 411 39 397 44 343 37 385 37 363 43 307 38 285 5 730 7 49 30 164 17 178 10 174 35 268 24 253 14 201 25 431 40 247 50 335 50 96 34 198 44 97 20 2 39 6 57 119 48 509 31 437 35 583 37 621 59 467 47 582 43 596 51 727 18 670 52 739 58 546 59 582 52 755 58 686 52 760 33 705 40 724 46 727 ...
output:
83
result:
ok single line: '83'
Test #25:
score: 0
Accepted
time: 14ms
memory: 3804kb
input:
35 57 48 390 413 434 452 329 369 367 400 449 464 424 412 424 419 430 438 383 401 282 277 280 252 253 244 201 181 463 407 455 472 72 160 50 75 188 193 84 34 327 366 203 241 189 228 266 292 76 116 241 292 281 326 243 284 231 280 169 215 227 266 278 322 292 333 288 332 325 366 440 448
output:
25
result:
ok single line: '25'
Test #26:
score: 0
Accepted
time: 21ms
memory: 3768kb
input:
31 33 74 79 537 184 587 63 410 24 255 134 289 42 290 233 633 45 516 8 190 226 329 312 355 314 281 132 12 319 208 329 607 210 464 137 425 211 413 272 424 268 371 311 398 297 376 317 363 259 359 20 201 29 375 106 525 63 509 130 548 95 544 100 537
output:
56
result:
ok single line: '56'
Test #27:
score: 0
Accepted
time: 12ms
memory: 3724kb
input:
22 23 71 17 703 192 694 179 632 203 423 86 369 214 385 104 132 189 129 45 20 168 287 118 295 116 351 112 348 27 374 58 224 34 72 12 345 48 628 54 440 141 689 94 568 58 672
output:
68
result:
ok single line: '68'
Test #28:
score: 0
Accepted
time: 25ms
memory: 3736kb
input:
31 95 47 267 358 427 436 242 364 281 204 245 277 171 464 115 456 53 354 77 386 11 188 53 365 4 414 7 318 4 214 17 361 0 135 157 429 320 84 327 319 360 348 378 378 566 43 31 104 720 20 800 206 860 296 676 350 888 389 615 391 788 432 659 435
output:
71
result:
ok single line: '71'
Test #29:
score: 0
Accepted
time: 21ms
memory: 3800kb
input:
34 8 80 1 617 17 715 28 740 25 782 51 756 65 619 80 678 74 97 37 578 37 579 35 532 33 404 27 560 13 563 14 507 38 355 38 461 56 221 65 162 52 293 49 406 57 257 55 264 58 235 55 304 55 298 52 355 78 7 37 19 75 45 1 532 30 622 69 417 32 754
output:
71
result:
ok single line: '71'
Test #30:
score: 0
Accepted
time: 28ms
memory: 3728kb
input:
36 37 5 255 38 287 32 286 40 277 44 258 42 253 37 252 37 246 40 247 44 93 35 47 22 60 25 232 42 350 2 350 1 203 28 152 22 99 25 261 7 169 3 155 12 71 10 114 14 17 7 96 47 87 40 294 46 174 43 360 50 363 27 347 25 345 14 324 46 332 12 297 46 303 27
output:
77
result:
ok single line: '77'
Test #31:
score: 0
Accepted
time: 9ms
memory: 3732kb
input:
23 46 3 61 19 77 28 273 30 309 22 185 17 362 22 307 23 316 25 418 30 354 24 359 24 378 23 452 25 295 18 418 24 160 13 361 18 375 8 327 2 26 4 187 21 248 21 277 28
output:
70
result:
ok single line: '70'
Test #32:
score: 0
Accepted
time: 64ms
memory: 3732kb
input:
50 79 44 3 389 96 432 79 440 47 430 58 436 34 425 17 429 12 424 30 420 2 411 6 288 11 219 206 375 98 295 56 329 87 357 13 371 104 396 609 351 90 208 60 93 164 12 255 174 736 223 513 40 241 86 312 15 326 41 603 12 719 63 561 57 556 19 410 45 298 49 313 59 527 34 719 204 626 75 773 180 666 340 370 259...
output:
82
result:
ok single line: '82'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
4 100 100 0 0 0 1000 1000 1000 1000 0
output:
100
result:
ok single line: '100'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
3 1 1 5 5 5 6 6 6
output:
1
result:
ok single line: '1'
Test #35:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
15 10 10 39 53 20 51 37 54 30 70 39 63 50 91 0 91 0 0 91 0 91 91 51 91 40 63 50 65 47 60 50 50
output:
99
result:
ok single line: '99'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
3 100 100 666 666 666 667 667 667
output:
1
result:
ok single line: '1'
Test #37:
score: 0
Accepted
time: 28ms
memory: 3772kb
input:
50 100 100 0 0 999 1 0 2 999 3 0 4 999 5 0 6 999 7 0 8 999 9 0 10 999 11 0 12 999 13 0 14 999 15 0 16 999 17 0 18 999 19 0 20 999 21 0 22 999 23 0 24 999 25 0 26 999 27 0 28 999 29 0 30 999 31 0 32 999 33 0 34 999 35 0 36 999 37 0 38 999 39 0 40 999 41 0 42 999 43 0 44 999 45 0 46 999 47 1000 1000 1...
output:
19
result:
ok single line: '19'
Test #38:
score: 0
Accepted
time: 57ms
memory: 4024kb
input:
50 100 100 0 0 1 999 2 1 3 999 4 1 5 999 6 1 7 999 8 1 9 999 10 1 11 999 12 1 13 999 14 1 15 999 16 1 17 999 18 1 19 999 20 1 21 999 22 1 23 999 24 1 25 999 26 1 27 999 28 1 29 999 30 1 31 999 32 1 33 999 34 1 35 999 36 1 37 999 38 1 39 999 40 1 41 999 42 1 43 999 44 1 45 999 46 1 47 999 1000 1000 4...
output:
64
result:
ok single line: '64'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
3 1 100 4 4 8 4 6 10
output:
4
result:
ok single line: '4'
Test #40:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
3 100 1 4 4 8 4 6 10
output:
6
result:
ok single line: '6'
Test #41:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
12 9 9 8 1 16 1 16 6 29 9 31 19 24 23 23 30 18 29 12 20 8 22 0 14 8 14
output:
10
result:
ok single line: '10'
Test #42:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
4 5 7 10 10 15 10 15 17 10 17
output:
1
result:
ok single line: '1'
Test #43:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
11 40 60 169 157 219 157 219 197 259 217 209 317 169 317 169 287 149 247 129 247 129 217 169 217
output:
8
result:
ok single line: '8'
Test #44:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
16 4 6 15 11 12 11 11 12 11 17 4 17 4 12 3 11 0 11 0 6 3 6 4 5 4 0 11 0 11 5 12 6 15 6
output:
8
result:
ok single line: '8'
Test #45:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
20 100 100 1 1 451 1 451 0 452 0 452 1 901 1 901 451 902 451 902 452 901 452 901 901 452 901 452 902 451 902 451 901 1 901 1 452 0 452 0 451 1 451
output:
85
result:
ok single line: '85'
Test #46:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
4 1 1 5 0 10 5 5 10 0 5
output:
60
result:
ok single line: '60'
Test #47:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
28 5 5 7 41 7 13 46 13 46 41 13 41 13 17 40 17 40 37 19 37 19 21 34 21 34 33 25 33 25 25 28 25 28 31 31 31 31 23 22 23 22 35 37 35 37 19 16 19 16 39 43 39 43 15 10 15 10 41
output:
48
result:
ok single line: '48'
Test #48:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
10 1 1 1 1 10 1 10 0 0 0 0 10 10 10 10 2 9 2 9 9 1 9
output:
35
result:
ok single line: '35'
Test #49:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
4 10 10 1 0 100 1 99 100 0 99
output:
100
result:
ok single line: '100'
Test #50:
score: 0
Accepted
time: 7ms
memory: 4008kb
input:
23 100 100 303 352 294 345 292 295 347 296 352 307 358 295 409 295 406 346 403 349 409 353 408 415 356 417 348 407 344 415 296 415 8 988 982 979 983 25 12 16 8 968 292 399 290 383 294 358
output:
99
result:
ok single line: '99'
Test #51:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
10 100 100 150 450 350 249 551 450 350 651 157 457 7 990 993 989 994 13 9 15 7 968
output:
95
result:
ok single line: '95'
Test #52:
score: 0
Accepted
time: 291ms
memory: 5216kb
input:
50 100 50 980 491 979 9 961 482 958 12 938 479 933 15 926 477 905 6 906 474 885 7 884 474 865 8 863 472 847 9 841 473 830 7 819 472 811 8 800 471 791 8 780 474 777 9 765 473 761 10 11 11 752 22 15 23 749 34 16 37 748 49 15 52 746 64 16 68 748 83 15 86 744 100 13 105 742 115 15 123 745 126 16 135 744...
output:
83
result:
ok single line: '83'
Test #53:
score: 0
Accepted
time: 259ms
memory: 5280kb
input:
50 97 93 3 922 7 10 956 11 954 920 947 22 15 20 11 901 25 33 938 32 938 916 931 40 31 42 27 900 34 48 926 47 928 904 921 57 40 57 44 897 47 64 916 65 913 901 906 73 55 73 59 895 65 80 901 79 898 899 893 89 73 88 71 896 82 97 887 100 879 916 880 108 90 106 85 893 98 116 874 117 866 912 866 122 106 12...
output:
58
result:
ok single line: '58'
Test #54:
score: 0
Accepted
time: 259ms
memory: 5388kb
input:
50 97 93 11 912 8 11 958 11 959 920 34 908 26 32 937 35 937 891 54 880 48 59 918 60 920 868 71 852 64 79 899 81 903 844 87 827 78 98 882 101 888 823 103 801 96 118 863 121 867 795 124 773 117 137 840 143 850 777 847 132 108 125 114 782 876 806 870 110 87 108 98 811 897 835 890 88 73 86 80 841 913 85...
output:
100
result:
ok single line: '100'