QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #49003 | #2702. Jeopardised Journey | YaoBIG | AC ✓ | 2680ms | 67364kb | C++17 | 9.4kb | 2022-09-18 16:32:19 | 2022-09-18 16:32:20 |
Judging History
answer
#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
using namespace std;
template<class A, class B> string to_string(pair<A, B> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<class A> string to_string(A v) {
bool first = 1;
string res = "{";
for (const auto &x: v) {
if (!first) res += ", ";
first = 0;
res += to_string(x);
}
res += "}";
return res;
}
template<class A, class B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
void debug_out() { cerr << endl; }
template<class Head, class... Tail> void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) if(0) puts("No effect.")
#endif
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
/**
* Author: Yuhao Yao
* Date: 22-08-26
* Status:
* project_to_line (double) tested on https://acm.hdu.edu.cn/showproblem.php?pid=6419.
* dis_to_line (double) tested on https://acm.hdu.edu.cn/showproblem.php?pid=6419.
* dis_to_seg (double) tested on https://acm.hdu.edu.cn/showproblem.php?pid=6419.
*/
template<class T> struct Point {
// use T = double or T = long long.
using P = Point;
using type = T;
static constexpr T eps = 1e-9;
static constexpr bool isInt = is_integral_v<T>;
static int sgn(T x) { return (x > eps) - (x < -eps); }
static int cmp(T x, T y) { return sgn(x - y); }
T x, y;
P operator +(P a) const { return P{x + a.x, y + a.y}; }
P operator -(P a) const { return P{x - a.x, y - a.y}; }
P operator *(T a) const { return P{x * a, y * a}; }
P operator /(T a) const { return P{x / a, y / a}; }
bool operator ==(P a) const { return cmp(x, a.x) == 0 && cmp(y, a.y) == 0; }
bool operator <(P a) const { return cmp(x, a.x) == 0 ? cmp(y, a.y) < 0: x < a.x; }
T len2() const { return x * x + y * y; }
T len() const { return sqrt(x * x + y * y); }
P unit() const {
if (isInt) return *this; // for long long
else return len() <= eps ? P{} : *this / len(); // for double / long double;
}
// dot and cross may lead to big relative error for imprecise point when the result is relatively smaller than the input magnitude.
T dot(P b) const { return x * b.x + y * b.y; }
T cross(P b) const { return x * b.y - y * b.x; }
bool is_upper() const { return y > eps || (sgn(y) == 0 && x < -eps); }
// return -1 if a has smaller pollar; return 1 if a has a larger pollar; return 0 o.w.
static int argcmp(P a, P b) {
if (a.is_upper() != b.is_upper()) return cmp(a.is_upper(), b.is_upper());
return sgn(b.cross(a));
// Taking unit makes it slower but I believe it is also safer. You can drop .unit() when you think the precision is not an issue.
// atan2 is much slower.
}
P rot90() const { return P{-y, x}; }
P rot270() const { return P{y, -x}; }
// Possible precision error:
// Absolute error is multiplied by the magnitude while the resulting coordinates can have 0 as magnitude!
P rotate(T theta) const {
P a{cos(theta), sin(theta)};
return P{x * a.x - y * a.y, x * a.y + y * a.x};
}
// Returns the signed projected length onto line $ab$. Return 0 if $a = b$.
T project_len(P a, P b) const { /// start-hash
if (isInt) return (*this - a).dot(b - a);
else if (a == b) return 0;
else return (*this - a).dot(b - a) / (b - a).len();
}
// Returns the signed distance to line $ab$. Returns 0 if $a = b$.
T dis_to_line(P a, P b) const { /// start-hash
if (isInt) return (*this - a).cross(b - a);
else if (a == b) return 0;
else return (*this - a).cross(b - a) / (b - a).len();
} /// end-hash
// Returns the distance to line segment $ab$. Safe when $a = b$.
// Only for double / long double.
T dis_to_seg(P a, P b) const { /// start-hash
if (project_len(a, b) <= eps) return (*this - a).len();
if (project_len(b, a) <= eps) return (*this - b).len();
return fabs(dis_to_line(a, b));
} /// end-hash
// Calculate the projection to line $ab$. Return $a$ when $a = b$.
// Only for double / long double.
P project_to_line(P a, P b) const { /// start-hash
return a + (b - a).unit() * project_len(a, b);
} /// end-hash
// Check if it is on segment ab. Safe when a == b.
bool on_seg(P a, P b) const { /// start-hash
return dis_to_seg(a, b) <= eps;
} /// end-hash
// Check if it is on line ab. Need a != b, otherwise returns true.
bool on_line(P a, P b) const { /// start-hash
return sgn(dis_to_line(a, b)) == 0;
} /// end-hash
friend string to_string(P p) { return "(" + to_string(p.x) + ", " + to_string(p.y) + ")"; }
};
/**
* Author: Yuhao Yao
* Date: 22-09-17
* Description: Compute the tangent points from Point $a$ to Circle $(o, r)$. return empty vector if $a$ is not outside the given Circle.
* Only works for double or long double.
* Status:
*/
template<class T, class P = Point<T>>
vector<P> PointCircleTagentPoints(P a, P o, T r) {
if (P::cmp((a - o).len2(), r * r) <= 0) return {};
T d = sqrt(max((a - o).len2() - r * r, T{0}));
T theta = asin(min(r / (a - o).len(), T{1}));
P v = (o - a).unit();
return {a + v.rotate(-theta) * d, a + v.rotate(theta) * d};
}
/**
* Author: Yuhao Yao
* Date: 22-09-16
* Description: Compute the Vertex-BiConnected Components of a \textbf{connected} graph.
* Multiple edges and self loops are allowed.
* $id[eid]$ records the index of bcc the edge $eid$ is in.
* $top[u]$ records the second highest vertex (which is unique) in the bcc which vertex $u$ is in.
* If the graph is not connected then only the component which $st$ is in is considered.
* Time: O(|E|).
* Status: tested on https://codeforces.com/gym/102900/problem/K.
*/
struct VertexBCC {
int bcc;
vi dfn, low, top, id, fa;
VertexBCC(int n, const vector<pii> &es, int st = 0): bcc(0), dfn(n, -1), low(n), top(n, -1), id(sz(es)), fa(n, -1) {
vi mark(sz(es)), sta;
int cnt = 0;
vvi g(n);
rep(ind, 0, sz(es) - 1) {
auto [x, y] = es[ind];
g[x].push_back(ind);
g[y].push_back(ind);
}
auto dfs = [&](auto dfs, int now) -> void {
low[now] = dfn[now] = cnt++;
for (auto ind: g[now]) if (mark[ind] == 0) {
mark[ind] = 1;
int oldsz = sz(sta);
sta.push_back(ind);
auto [x, y] = es[ind];
int v = now ^ x ^ y;
if (dfn[v] == -1) {
dfs(dfs, v);
fa[v] = now;
low[now] = min(low[now], low[v]);
if (low[v] >= dfn[now]) {
while (sz(sta) > oldsz) {
id[sta.back()] = bcc;
auto [a, b] = es[sta.back()];
top[a] = top[b] = v;
sta.pop_back();
}
bcc++;
}
} else low[now] = min(low[now], dfn[v]);
}
};
dfs(dfs, st);
top[st] = st;
}
bool SameBcc(int x, int y) {
assert(dfn[x] != -1 && dfn[y] != -1);
if (x == fa[top[y]] || y == fa[top[x]]) return 1;
else return top[x] == top[y];
}
};
template<class T> struct BIT {
int n;
vector<T> a;
BIT(int n): n(n), a(n + 1, 0) {}
void Add(int i, T x) {
for (++i; i <= n; i += i & -i) a[i] += x;
}
T Ask(int i) {
T ans{};
for (++i; i; i -= i & -i) ans += a[i];
return ans;
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
using T = long double;
using P = Point<T>;
int n, m; cin >> n >> m;
vector<P> as(n), os(m);
vector<T> rs(m);
for (auto &[x, y]: as) cin >> x >> y;
rep(i, 0, m - 1) {
cin >> os[i].x >> os[i].y >> rs[i];
}
vector<pii> es;
rep(i, 0, n - 1) {
P a = as[i];
vector<P> vec;
rep(j, i + 1, n - 1) vec.push_back(as[j] - a);
auto cmp = [](P a, P b) { return P::argcmp(a, b) < 0; };
sort(all(vec), cmp);
vec.erase(unique(all(vec), [](P a, P b) { return P::argcmp(a, b) == 0; }), vec.end());
auto getid = [&](P p) { return lower_bound(all(vec), p, cmp) - vec.begin(); };
struct Info {
int l, r, id;
T len;
};
vector<Info> qs;
rep(j, 0, m - 1) {
P o = os[j];
T rad = rs[j];
auto res = PointCircleTagentPoints(a, o, rad);
assert(sz(res) == 2);
int l = lower_bound(all(vec), res[0] - a, cmp) - vec.begin();
int r = upper_bound(all(vec), res[1] - a, cmp) - vec.begin() - 1;
T d2 = (o - a).len2() - rad * rad;
if (l <= r || P::argcmp(res[1] - a, res[0] - a) < 0) qs.push_back({l, r, -1, d2});
}
rep(j, i + 1, n - 1) {
int ind = getid(as[j] - a);
qs.push_back({ind, ind, j, (as[j] - a).len2()});
}
sort(all(qs), [](Info a, Info b) { return a.len < b.len; });
int tot = sz(vec);
BIT<int> bit(tot + 1);
for (auto [l, r, id, _]: qs) {
if (id != -1 && bit.Ask(l) == 0) es.emplace_back(i, id);
bit.Add(l, 1);
bit.Add(r + 1, -1);
if (l > r) bit.Add(0, 1);
}
}
VertexBCC bcc(n, es, n - 1);
rep(i, 0, n - 2) if (bcc.dfn[i] != -1 && bcc.SameBcc(i, n - 1)) printf("%d ", i + 1);
puts("");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3784kb
input:
4 2 0 0 0 10 10 0 10 10 5 0 2 10 5 2
output:
1 2
result:
ok single line: '1 2 '
Test #2:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
3 1 0 3 3 4 3 5 1 5 1
output:
1 2
result:
ok single line: '1 2 '
Test #3:
score: 0
Accepted
time: 363ms
memory: 19488kb
input:
1000 1000 0 0 10 11 20 23 30 36 40 50 50 65 60 81 70 98 80 116 90 135 100 155 110 176 120 198 130 221 140 245 150 270 160 296 170 323 180 351 190 380 200 410 210 441 220 473 230 506 240 540 250 575 260 611 270 648 280 686 290 725 300 765 310 806 320 848 330 891 340 935 350 980 360 1026 370 1073 380 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...92 993 994 995 996 997 998 999 '
Test #4:
score: 0
Accepted
time: 516ms
memory: 15380kb
input:
1000 1000 0 0 10 11 20 23 30 36 40 50 50 65 60 81 70 98 80 116 90 135 100 155 110 176 120 198 130 221 140 245 150 270 160 296 170 323 180 351 190 380 200 410 210 441 220 473 230 506 240 540 250 575 260 611 270 648 280 686 290 725 300 765 310 806 320 848 330 891 340 935 350 980 360 1026 370 1073 380 ...
output:
result:
ok 0 lines
Test #5:
score: 0
Accepted
time: 2162ms
memory: 51144kb
input:
2000 2000 0 0 10 11 20 23 30 36 40 50 50 65 60 81 70 98 80 116 90 135 100 155 110 176 120 198 130 221 140 245 150 270 160 296 170 323 180 351 190 380 200 410 210 441 220 473 230 506 240 540 250 575 260 611 270 648 280 686 290 725 300 765 310 806 320 848 330 891 340 935 350 980 360 1026 370 1073 380 ...
output:
result:
ok 0 lines
Test #6:
score: 0
Accepted
time: 1602ms
memory: 67364kb
input:
2000 2000 0 0 10 11 20 23 30 36 40 50 50 65 60 81 70 98 80 116 90 135 100 155 110 176 120 198 130 221 140 245 150 270 160 296 170 323 180 351 190 380 200 410 210 441 220 473 230 506 240 540 250 575 260 611 270 648 280 686 290 725 300 765 310 806 320 848 330 891 340 935 350 980 360 1026 370 1073 380 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 1994 1995 1996 1997 1998 1999 '
Test #7:
score: 0
Accepted
time: 524ms
memory: 17012kb
input:
1000 1000 0 0 0 10 0 20 0 30 0 40 0 50 0 60 0 70 0 80 0 90 0 100 0 110 0 120 0 130 0 140 0 150 0 160 0 170 0 180 0 190 0 200 0 210 0 220 0 230 0 240 0 250 0 260 0 270 0 280 0 290 0 300 10 0 10 10 10 20 10 30 10 40 10 50 10 60 10 70 10 80 10 90 10 100 10 110 10 120 10 130 10 140 10 150 10 160 10 170 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...92 993 994 995 996 997 998 999 '
Test #8:
score: 0
Accepted
time: 2242ms
memory: 53108kb
input:
2000 2000 0 0 0 10 0 20 0 30 0 40 0 50 0 60 0 70 0 80 0 90 0 100 0 110 0 120 0 130 0 140 0 150 0 160 0 170 0 180 0 190 0 200 0 210 0 220 0 230 0 240 0 250 0 260 0 270 0 280 0 290 0 300 0 310 0 320 0 330 0 340 0 350 0 360 0 370 0 380 0 390 0 400 0 410 0 420 0 430 10 0 10 10 10 20 10 30 10 40 10 50 10...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 1994 1995 1996 1997 1998 1999 '
Test #9:
score: 0
Accepted
time: 2ms
memory: 3852kb
input:
4 0 0 0 10 0 0 10 10 10
output:
1 2 3
result:
ok single line: '1 2 3 '
Test #10:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 1 1000000 -1 0 10 0 0 1 1 1
output:
1
result:
ok single line: '1 '
Test #11:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
3 1 1000000 1000000 0 1000000 0 0 1000000 0 707107
output:
2
result:
ok single line: '2 '
Test #12:
score: 0
Accepted
time: 2ms
memory: 3860kb
input:
3 1 1000000 1000000 0 1000000 0 0 1000000 0 707106
output:
1 2
result:
ok single line: '1 2 '
Test #13:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
10 10 -834 -260 -119 241 12 -242 21 -60 -465 743 874 143 717 -496 696 762 892 448 -302 259 33 727 80 169 -496 142 221 -40 166 843 600 48 688 -99 270 520 -977 321 -815 822 128 -265 922 85 -644 -731 107 -978 -489 250
output:
1 2 3 4 5 6 8 9
result:
ok single line: '1 2 3 4 5 6 8 9 '
Test #14:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
10 10 572 871 465 -206 800 413 149 417 236 749 67 -649 -413 568 -455 -385 291 472 -184 980 277 835 10 -727 59 325 662 -844 146 81 -141 233 134 -762 115 -378 -488 27 940 776 141 481 -129 9 -934 872 265 -171 195 40
output:
1 2 3 4 5 6 7 8 9
result:
ok single line: '1 2 3 4 5 6 7 8 9 '
Test #15:
score: 0
Accepted
time: 2ms
memory: 3816kb
input:
10 10 -751 948 -463 348 477 -65 224 -705 -391 -134 -823 757 -503 807 352 -300 -97 -594 128 605 -342 -308 174 902 -634 347 111 -316 184 88 969 133 741 623 73 548 327 125 -196 -915 253 -974 610 63 -844 -939 103 -616 260 100
output:
1 2 3 4 5 6 7 8
result:
ok single line: '1 2 3 4 5 6 7 8 '
Test #16:
score: 0
Accepted
time: 2ms
memory: 3748kb
input:
10 10 -710 515 -669 195 -985 851 231 785 188 -101 -270 -580 788 -317 32 658 -726 60 880 150 24 408 249 -956 -375 304 841 482 265 150 926 155 -700 -50 63 45 -20 116 -509 939 286 484 -88 159 -940 -977 221 536 864 55
output:
1 2 3 4 6 7 9
result:
ok single line: '1 2 3 4 6 7 9 '
Test #17:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
10 10 -611 -747 -912 629 904 -294 826 -551 -14 -994 831 -573 363 977 -443 -579 177 -621 868 525 151 489 91 465 -225 164 459 -909 53 712 -468 34 -231 -776 218 -47 3 81 282 561 2 -541 940 222 -663 91 63 -752 580 41
output:
1 2 3 4 5 6 7 8 9
result:
ok single line: '1 2 3 4 5 6 7 8 9 '
Test #18:
score: 0
Accepted
time: 7ms
memory: 3840kb
input:
100 100 -210 91 483 -787 -558 -816 2 936 -845 -935 -73 -719 -698 -719 221 -601 823 2 158 68 -234 977 -38 992 371 127 -144 921 808 540 943 -50 -17 426 164 426 610 -482 714 -883 -65 -359 -601 589 274 972 989 449 327 147 -482 -555 476 480 -563 199 -41 645 120 -232 186 415 -930 -479 -158 586 -701 -196 -...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 90 91 92 93 94 95 96 97 98 99
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 90 91 92 93 94 95 96 97 98 99 '
Test #19:
score: 0
Accepted
time: 7ms
memory: 3924kb
input:
100 100 -433 319 -606 372 340 194 966 -381 998 93 -634 -901 125 -306 335 -502 -633 -784 -726 198 -651 -862 618 644 115 897 -755 338 560 -501 -996 -521 -830 -602 851 862 944 817 -519 942 -90 -153 -607 -965 894 729 -467 -739 -703 159 811 -354 298 781 -358 -235 679 -113 -897 239 738 -541 718 -739 -142 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 90 91 92 93 94 95 96 97 98 99 '
Test #20:
score: 0
Accepted
time: 7ms
memory: 3880kb
input:
100 100 692 429 -77 196 573 950 -650 696 -406 53 -198 -849 -541 -265 550 -127 -368 -285 -922 -398 573 -177 -207 -873 712 311 896 956 82 -308 872 -225 -879 -205 -677 -954 -254 -327 -906 692 -921 248 -804 -110 -664 746 -885 320 -187 -806 923 -614 17 68 -134 -271 -269 -238 37 -834 806 -91 293 -721 705 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 94 95 96 97 98 99
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 89 90 91 92 94 95 96 97 98 99 '
Test #21:
score: 0
Accepted
time: 7ms
memory: 3752kb
input:
100 100 -798 -490 -162 645 383 -717 551 693 689 -118 -527 -277 45 -427 294 -402 433 569 -973 -319 676 756 -593 105 -979 -472 844 963 -124 40 -381 430 902 457 427 285 -908 -22 330 781 860 803 -143 -95 -623 -849 855 -838 721 882 -156 749 638 251 206 -989 -869 50 974 359 -558 -55 -211 -656 -246 -784 98...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 94 95 96 97 98 99
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 89 90 91 92 94 95 96 97 98 99 '
Test #22:
score: 0
Accepted
time: 7ms
memory: 3804kb
input:
100 100 913 -468 -873 353 578 234 983 -328 -54 844 -751 533 729 801 328 -478 143 -150 43 -154 -713 -742 -612 -444 216 -759 -38 -522 -416 184 929 -502 717 -592 -797 647 643 -462 -680 -59 -266 -431 -525 -537 -278 803 338 865 6 -267 64 645 -9 452 -447 -441 -955 515 38 -371 52 -33 479 121 728 -966 -232 ...
output:
1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 12 13 14 ... 90 91 92 93 94 95 96 97 98 99 '
Test #23:
score: 0
Accepted
time: 605ms
memory: 4572kb
input:
1000 1000 -502 -995 560 -206 -681 653 -651 -783 94 56 -332 724 914 162 977 487 -918 -992 394 176 -904 -565 -730 -699 25 -266 -522 -158 -878 134 -561 -380 491 -1000 415 811 -995 -884 -972 451 524 -304 528 790 -790 505 278 -708 514 24 820 962 811 -910 -737 188 176 93 -970 299 -773 -531 -729 -929 -179 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 67 68 69 70 71 72 73 74 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 ...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...92 993 994 995 996 997 998 999 '
Test #24:
score: 0
Accepted
time: 622ms
memory: 4476kb
input:
1000 1000 -922 -344 -554 911 92 319 -191 -61 717 -331 900 -228 -724 -68 47 -709 239 478 -757 -374 998 551 800 -343 172 891 427 793 884 121 -208 -686 777 590 -775 222 -90 386 -487 -373 -592 -235 399 36 -951 -201 328 288 -371 923 914 -21 474 -934 636 -354 958 63 -209 -806 -816 584 -491 -686 174 86 888...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...92 993 994 995 996 997 998 999 '
Test #25:
score: 0
Accepted
time: 611ms
memory: 4524kb
input:
1000 1000 -320 -942 -72 -63 -755 -940 670 236 -161 362 -478 -509 637 -719 578 167 -826 -588 931 -554 -588 -281 -672 -603 807 659 -372 -854 -293 -879 -56 739 -468 872 -324 -223 -715 -301 -635 476 -587 239 -681 -598 521 -750 569 -953 -338 852 -155 427 -76 173 -824 -269 184 -196 229 -757 -75 -827 982 4...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...92 993 994 995 996 997 998 999 '
Test #26:
score: 0
Accepted
time: 629ms
memory: 4492kb
input:
1000 1000 398 325 -190 451 682 -686 -370 -790 -947 -696 -36 937 -1 -382 834 -46 -703 49 847 838 363 -979 -622 262 179 -438 229 54 119 652 -899 -482 -23 264 -679 11 578 -49 222 983 256 -462 920 -745 157 -894 561 806 155 408 996 -130 782 -626 -515 -39 288 714 -633 -592 718 -531 278 47 -915 599 -590 66...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...92 993 994 995 996 997 998 999 '
Test #27:
score: 0
Accepted
time: 615ms
memory: 4560kb
input:
1000 1000 -121 590 413 -123 816 368 722 -687 232 -108 -206 615 -136 -457 -130 14 195 -628 -127 345 -728 216 600 518 189 138 317 -228 -132 474 -233 747 64 -820 -23 -120 900 -301 545 133 943 -309 -252 160 586 970 -826 -218 -658 399 -521 -33 -33 -921 -515 -492 218 803 281 -562 277 -952 -462 -307 -420 5...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...92 993 994 995 996 997 998 999 '
Test #28:
score: 0
Accepted
time: 2635ms
memory: 5040kb
input:
2000 2000 -395 235 355 -278 151 -755 548 327 -794 516 271 682 -699 -154 -295 -80 -449 -962 863 399 963 739 210 -276 139 -619 -679 779 -204 -630 -107 753 957 -400 -525 108 -155 -625 -213 403 892 -941 86 -455 257 -857 817 808 -467 680 559 -504 419 121 573 -90 503 894 41 -349 -736 934 -595 -779 -466 23...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 1994 1995 1996 1997 1998 1999 '
Test #29:
score: 0
Accepted
time: 2638ms
memory: 4992kb
input:
2000 2000 -592 336 165 890 39 -783 365 -421 785 -353 -7 828 -682 -747 -968 746 -983 -548 -563 891 -549 -758 878 26 -561 216 -925 584 155 267 -341 916 -397 824 806 642 -607 171 -426 -822 818 567 -641 -512 -828 -609 -765 -459 195 24 -568 646 618 -338 25 -591 -770 100 -655 386 -281 5 654 323 -171 460 3...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 1994 1995 1996 1997 1998 1999 '
Test #30:
score: 0
Accepted
time: 2656ms
memory: 4916kb
input:
2000 2000 410 -538 362 -943 947 -284 201 236 -450 816 360 -924 188 -439 792 495 747 805 459 -954 -533 -642 -510 601 749 -873 849 642 220 527 -178 -369 -659 -815 -312 -711 -99 -759 877 803 -943 589 879 597 -850 672 92 -750 829 -448 -352 -704 262 138 -750 11 266 -549 -347 -162 978 476 821 -680 -987 -4...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 1994 1995 1996 1997 1998 1999 '
Test #31:
score: 0
Accepted
time: 2680ms
memory: 5032kb
input:
2000 2000 588 -138 -77 991 -902 81 634 -362 155 200 85 245 -407 -606 -632 -308 189 852 282 -744 498 -859 -858 -990 -287 433 -794 -595 -125 273 54 -185 -512 -671 -194 -62 763 -559 576 -82 993 -338 -837 -414 408 -117 279 -51 -265 -87 205 -414 407 699 -404 -880 484 -198 -123 -641 -572 931 174 -84 -387 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 1994 1995 1996 1997 1998 1999 '
Test #32:
score: 0
Accepted
time: 2636ms
memory: 5056kb
input:
2000 2000 617 664 -343 247 -719 427 561 740 -711 -544 50 707 -536 450 784 217 -194 -963 817 -777 -24 263 -975 943 -825 -527 459 -121 421 457 -733 38 122 -76 -715 755 -296 -801 495 -7 -345 -103 -300 119 -653 -163 -311 506 -126 -494 -919 -798 769 -894 -502 944 -69 957 175 -648 415 442 742 -111 -281 -6...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 1993 1994 1995 1996 1998 1999 '
Test #33:
score: 0
Accepted
time: 2ms
memory: 3864kb
input:
4 2 0 0 10 0 0 10 10 10 5 5 1 5 1 1
output:
2 3
result:
ok single line: '2 3 '
Test #34:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
3 1 10 0 0 10 0 0 1 1 1
output:
result:
ok 0 lines
Test #35:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
7 5 0 0 10 10 10 -10 40 0 30 10 30 -10 20 0 10 4 1 6 -3 3 14 -3 3 20 10 4 30 0 4
output:
2 4 5 6
result:
ok single line: '2 4 5 6 '