QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#498761 | #7674. Skiing | Max_s_xaM | AC ✓ | 101ms | 65308kb | C++14 | 7.1kb | 2024-07-30 19:28:27 | 2024-07-30 19:28:27 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 260;
const lf eps = 1e-9;
int n; lf vy, ax;
struct Point
{
lf x, y; int id;
bool operator < (const Point &u) const { return (fabs(y - u.y) < eps ? id < u.id : y < u.y); }
}a[MAXN];
struct Line
{
lf x, y;
bool operator < (const Line &u) const { return x == u.x ? y > u.y : x < u.x; }
};
struct Answer
{
// vector <int> res;
vector <Line> d;
}f[MAXN][MAXN];
vector <Line> mg;
inline lf Calc(lf v1, lf v2, lf t)
{
return (v1 + v2) * t / 2;
}
inline pair <lf, lf> Solve(lf mn, lf mx, lf t, lf dist)
{
if (fabs(t) < eps) return (fabs(dist) < eps ? make_pair(mn, mx) : make_pair(1e20, -1e20));
lf l = dist / t - ax * t / 2, r = dist / t + ax * t / 2, b, c, delta;
if (Calc(mx + ax * t, mx, t) < dist) return {1e20, -1e20};
if (Calc(mx - ax * t, mx, t) < dist)
{
b = -2 * (ax * t + mx), c = -ax * ax * t * t - 2 * ax * t * mx + mx * mx + 4 * ax * dist;
delta = b * b - 4 * c;
l = max(l, (-b - sqrt(delta)) / 2);
}
if (Calc(mn - ax * t, mn, t) > dist) return {1e20, -1e20};
if (Calc(mn + ax * t, mn, t) > dist)
{
b = 2 * (ax * t - mn), c = -ax * ax * t * t + 2 * ax * t * mn + mn * mn - 4 * ax * dist;
delta = b * b - 4 * c;
r = min(r, (-b + sqrt(delta)) / 2);
}
return make_pair(l, r);
}
int main()
{
// freopen("A.in", "r", stdin);
// freopen("A.out", "w", stdout);
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n), Read(vy), Read(ax);
for (int i = 1, j = 1; i <= n; i++, j++)
{
Read(a[i].x), Read(a[i].y);
if (a[i].y < 0) { i--, n--; continue; }
a[i].y /= vy, a[i].id = j;
}
a[++n] = Point{0, 0, 0};
sort(a + 1, a + n + 1);
if (ax == 0)
{
bool flag = 0;
for (int i = 2; i <= n; i++)
if (a[i].x == 0) { cout << a[i].id << ' '; flag = 1; }
if (!flag) cout << "Cannot visit any targets\n";
return 0;
}
// for (int i = 1; i <= n; i++) cout << a[i].x << ' ' << a[i].y << '\n';
for (int i = 1; i <= n; i++)
{
// f[i][1].res.push_back(a[i].id);
f[i][1].d.push_back(Line{-1e20, 1e20});
}
for (int i = n; i >= 1; i--)
for (int k = 1; k <= n - i + 1; k++)
{
if (!f[i][k].d.size()) continue;
sort(f[i][k].d.begin(), f[i][k].d.end());
lf pl = -1e21, pr = -1e21;
mg.clear();
for (auto [x, y] : f[i][k].d)
{
if (x > pr)
{
if (pl != -1e21) mg.push_back(Line{pl, pr});
pl = x, pr = y;
}
else pr = max(pr, y);
}
if (pl != -1e21) mg.push_back(Line{pl, pr});
f[i][k].d = mg;
// cout << "Solve " << a[i].id << ' ' << k << ' ' << a[i].x << ' ' << a[i].y << "\n";
// for (auto [x, y] : f[i][k].d) cout << x << ' ' << y << "\n";
// cout << "\n";
for (int j = i - 1; j >= 1; j--)
{
// if (f[j].res.size() > f[i].res.size() + 1 || (f[j].res.size() == f[i].res.size() + 1 && f[j].res[1] < a[i].id)) continue;
lf len = a[i].y - a[j].y, dist = a[i].x - a[j].x;
mg.clear();
for (auto [x, y] : f[i][k].d)
{
auto cur = Solve(x, y, len, dist);
if (cur.first > cur.second) continue;
mg.push_back(Line{cur.first, cur.second});
}
if (mg.size())
{
if (j == 1)
{
bool flag = 0;
for (auto [x, y] : mg)
if ((x < 0 || fabs(x) < eps) && (y > 0 || fabs(y) < eps)) { flag = 1; break; }
if (!flag) continue;
}
// f[j].res = {a[j].id};
// for (auto x : f[i].res) f[j].res.push_back(x);
for (auto x : mg) f[j][k + 1].d.push_back(x);
// cout << "Trans " << a[i].id << ' ' << k << ' ' << a[j].id << '\n';
}
}
}
int x = 1, y = 1;
while (f[1][y].d.size()) y++; y--;
if (y == 1) return cout << "Cannot visit any targets\n", 0;
// cout << "-----------\n";
// cout << x << ' ' << y << "\n";
lf l = 0, r = 0; a[n + 1].id = 2e9;
for (int i = y - 1; i >= 1; i--)
{
int p = n + 1; lf pl = 0, pr = 0;
// cout << "srch " << x << ' ' << y << '\n';
for (int j = x + 1; j <= n; j++)
{
if (a[j].id > a[p].id || !f[j][i].d.size()) continue;
lf len = a[j].y - a[x].y, dist = a[j].x - a[x].x;
auto cur = Solve(l, r, len, dist);
if (cur.first > cur.second) continue;
for (auto [xx, yy] : f[j][i].d)
if (xx <= cur.second && cur.first <= yy) { pl = cur.first, pr = cur.second, p = j; break; }
}
x = p, l = pl, r = pr;
cout << a[x].id << ' ';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6800kb
input:
4 100 400 -100 100 50 200 -100 300 150 300
output:
1 2 4
result:
ok single line: '1 2 4 '
Test #2:
score: 0
Accepted
time: 1ms
memory: 5260kb
input:
1 100 100 1000 10
output:
Cannot visit any targets
result:
ok single line: 'Cannot visit any targets'
Test #3:
score: 0
Accepted
time: 0ms
memory: 7192kb
input:
0 100 100
output:
Cannot visit any targets
result:
ok single line: 'Cannot visit any targets'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5260kb
input:
2 100 100 100 100 -100 100
output:
Cannot visit any targets
result:
ok single line: 'Cannot visit any targets'
Test #5:
score: 0
Accepted
time: 0ms
memory: 6424kb
input:
2 1000 2001 1000 1000 -1000 1000
output:
1
result:
ok single line: '1 '
Test #6:
score: 0
Accepted
time: 1ms
memory: 6496kb
input:
3 10 30 10 10 -10 10 0 20
output:
1
result:
ok single line: '1 '
Test #7:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
3 10 31 10 10 -10 10 0 20
output:
1 3
result:
ok single line: '1 3 '
Test #8:
score: 0
Accepted
time: 1ms
memory: 6524kb
input:
4 10 31 10 10 -10 10 0 19 0 20
output:
1 4
result:
ok single line: '1 4 '
Test #9:
score: 0
Accepted
time: 1ms
memory: 7124kb
input:
4 10 31 10 10 -10 10 0 20 0 21
output:
1 3
result:
ok single line: '1 3 '
Test #10:
score: 0
Accepted
time: 1ms
memory: 5856kb
input:
5 10 31 10 10 -10 10 0 19 0 20 0 21
output:
3 4 5
result:
ok single line: '3 4 5 '
Test #11:
score: 0
Accepted
time: 0ms
memory: 6576kb
input:
3 10 50 100 40 -100 40 -100 50
output:
2 3
result:
ok single line: '2 3 '
Test #12:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
7 10 25 -10 10 10 10 10 20 10 30 0 40 -10 20 -10 30
output:
1 6 7 5
result:
ok single line: '1 6 7 5 '
Test #13:
score: 0
Accepted
time: 97ms
memory: 64896kb
input:
250 1 79988 -10000 1 10000 2 -10000 3 10000 4 -10000 5 10000 6 -10000 7 10000 8 -10000 9 10000 10 -10000 11 10000 12 -10000 13 10000 14 -10000 15 10000 16 -10000 17 10000 18 -10000 19 10000 20 -10000 21 10000 22 -10000 23 10000 24 -10000 25 10000 26 -10000 27 10000 28 -10000 29 10000 30 -10000 31 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 ...43 244 245 246 247 248 249 250 '
Test #14:
score: 0
Accepted
time: 61ms
memory: 46848kb
input:
250 1 39999 -10000 1 10000 2 -10000 3 10000 4 -10000 5 10000 6 -10000 7 10000 8 -10000 9 10000 10 -10000 11 10000 12 -10000 13 10000 14 -10000 15 10000 16 -10000 17 10000 18 -10000 19 10000 20 -10000 21 10000 22 -10000 23 10000 24 -10000 25 10000 26 -10000 27 10000 28 -10000 29 10000 30 -10000 31 10...
output:
1 3 4 6 7 9 10 12 13 15 16 18 19 21 22 24 25 27 28 30 31 33 34 36 37 39 40 42 43 45 46 48 49 51 52 54 55 57 58 60 61 63 64 66 67 69 70 72 73 75 76 78 79 81 82 84 85 87 88 90 91 93 94 96 97 99 100 102 103 105 106 108 109 111 112 114 115 117 118 120 121 123 124 126 127 129 130 132 133 135 136 138 139 ...
result:
ok single line: '1 3 4 6 7 9 10 12 13 15 16 18 ...40 241 243 244 246 247 249 250 '
Test #15:
score: 0
Accepted
time: 1ms
memory: 5680kb
input:
1 100 100 0 0
output:
1
result:
ok single line: '1 '
Test #16:
score: 0
Accepted
time: 74ms
memory: 51520kb
input:
250 1 40001 -10000 1 10000 2 -10000 3 10000 4 -10000 5 10000 6 -10000 7 10000 8 -10000 9 10000 10 -10000 11 10000 12 -10000 13 10000 14 -10000 15 10000 16 -10000 17 10000 18 -10000 19 10000 20 -10000 21 10000 22 -10000 23 10000 24 -10000 25 10000 26 -10000 27 10000 28 -10000 29 10000 30 -10000 31 10...
output:
1 2 4 5 6 8 9 10 12 13 14 16 17 18 20 21 22 24 25 26 28 29 30 32 33 34 36 37 38 40 41 42 44 45 46 48 49 50 52 53 54 56 57 58 60 61 62 64 65 66 68 69 70 72 73 74 76 77 78 80 81 82 84 85 86 88 89 90 92 93 94 96 97 98 100 101 102 104 105 106 108 109 110 112 113 114 116 117 118 120 121 122 124 125 126 1...
result:
ok single line: '1 2 4 5 6 8 9 10 12 13 14 16 1...41 242 244 245 246 248 249 250 '
Test #17:
score: 0
Accepted
time: 76ms
memory: 54684kb
input:
250 1 60000 -10000 1 10000 2 -10000 3 10000 4 -10000 5 10000 6 -10000 7 10000 8 -10000 9 10000 10 -10000 11 10000 12 -10000 13 10000 14 -10000 15 10000 16 -10000 17 10000 18 -10000 19 10000 20 -10000 21 10000 22 -10000 23 10000 24 -10000 25 10000 26 -10000 27 10000 28 -10000 29 10000 30 -10000 31 10...
output:
1 2 3 5 6 7 8 10 11 12 13 15 16 17 18 20 21 22 23 25 26 27 28 30 31 32 33 35 36 37 38 40 41 42 43 45 46 47 48 50 51 52 53 55 56 57 58 60 61 62 63 65 66 67 68 70 71 72 73 75 76 77 78 80 81 82 83 85 86 87 88 90 91 92 93 95 96 97 98 100 101 102 103 105 106 107 108 110 111 112 113 115 116 117 118 120 12...
result:
ok single line: '1 2 3 5 6 7 8 10 11 12 13 15 1...41 242 243 245 246 247 248 250 '
Test #18:
score: 0
Accepted
time: 78ms
memory: 58128kb
input:
250 1 70000 -10000 1 10000 2 -10000 3 10000 4 -10000 5 10000 6 -10000 7 10000 8 -10000 9 10000 10 -10000 11 10000 12 -10000 13 10000 14 -10000 15 10000 16 -10000 17 10000 18 -10000 19 10000 20 -10000 21 10000 22 -10000 23 10000 24 -10000 25 10000 26 -10000 27 10000 28 -10000 29 10000 30 -10000 31 10...
output:
1 2 3 4 5 6 8 9 10 11 12 13 14 16 17 18 19 20 21 22 24 25 26 27 28 29 30 32 33 34 35 36 37 38 40 41 42 43 44 45 46 48 49 50 51 52 53 54 56 57 58 59 60 61 62 64 65 66 67 68 69 70 72 73 74 75 76 77 78 80 81 82 83 84 85 86 88 89 90 91 92 93 94 96 97 98 99 100 101 102 104 105 106 107 108 109 110 112 113...
result:
ok single line: '1 2 3 4 5 6 8 9 10 11 12 13 14...42 243 244 245 246 248 249 250 '
Test #19:
score: 0
Accepted
time: 91ms
memory: 63512kb
input:
250 1 79700 -10000 1 10000 2 -10000 3 10000 4 -10000 5 10000 6 -10000 7 10000 8 -10000 9 10000 10 -10000 11 10000 12 -10000 13 10000 14 -10000 15 10000 16 -10000 17 10000 18 -10000 19 10000 20 -10000 21 10000 22 -10000 23 10000 24 -10000 25 10000 26 -10000 27 10000 28 -10000 29 10000 30 -10000 31 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 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 101 102 103 104...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...43 244 245 246 247 248 249 250 '
Test #20:
score: 0
Accepted
time: 92ms
memory: 64960kb
input:
250 1 79950 -10000 1 10000 2 -10000 3 10000 4 -10000 5 10000 6 -10000 7 10000 8 -10000 9 10000 10 -10000 11 10000 12 -10000 13 10000 14 -10000 15 10000 16 -10000 17 10000 18 -10000 19 10000 20 -10000 21 10000 22 -10000 23 10000 24 -10000 25 10000 26 -10000 27 10000 28 -10000 29 10000 30 -10000 31 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 ...42 243 244 245 246 247 248 250 '
Test #21:
score: 0
Accepted
time: 1ms
memory: 5904kb
input:
1 1000 2001 1000 1000
output:
1
result:
ok single line: '1 '
Test #22:
score: 0
Accepted
time: 1ms
memory: 6320kb
input:
1 100 200 101 100
output:
Cannot visit any targets
result:
ok single line: 'Cannot visit any targets'
Test #23:
score: 0
Accepted
time: 1ms
memory: 6984kb
input:
2 100 200 0 100 182 200
output:
1 2
result:
ok single line: '1 2 '
Test #24:
score: 0
Accepted
time: 1ms
memory: 6488kb
input:
2 100 200 0 100 183 200
output:
1
result:
ok single line: '1 '
Test #25:
score: 0
Accepted
time: 1ms
memory: 5812kb
input:
1 100 0 0 0
output:
1
result:
ok single line: '1 '
Test #26:
score: 0
Accepted
time: 1ms
memory: 6304kb
input:
3 100 200 0 100 0 200 199 300
output:
1 2 3
result:
ok single line: '1 2 3 '
Test #27:
score: 0
Accepted
time: 1ms
memory: 6880kb
input:
3 100 200 0 100 0 200 200 300
output:
1 2
result:
ok single line: '1 2 '
Test #28:
score: 0
Accepted
time: 0ms
memory: 7164kb
input:
1 100 0 0 100
output:
1
result:
ok single line: '1 '
Test #29:
score: 0
Accepted
time: 0ms
memory: 6824kb
input:
1 100 0 1 100
output:
Cannot visit any targets
result:
ok single line: 'Cannot visit any targets'
Test #30:
score: 0
Accepted
time: 1ms
memory: 6076kb
input:
1 100 0 1 0
output:
Cannot visit any targets
result:
ok single line: 'Cannot visit any targets'
Test #31:
score: 0
Accepted
time: 0ms
memory: 7200kb
input:
8 10000 0 0 0 1 0 0 100 0 50 0 0 0 50 0 0 0 100
output:
1 5 7 4 6 3 8
result:
ok single line: '1 5 7 4 6 3 8 '
Test #32:
score: 0
Accepted
time: 0ms
memory: 5752kb
input:
1 1000 10 -490 10000
output:
1
result:
ok single line: '1 '
Test #33:
score: 0
Accepted
time: 0ms
memory: 6800kb
input:
1 1000 10 510 10000
output:
Cannot visit any targets
result:
ok single line: 'Cannot visit any targets'
Test #34:
score: 0
Accepted
time: 0ms
memory: 5460kb
input:
100 1000 100 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 28...
output:
73 34 88 92 96
result:
ok single line: '73 34 88 92 96 '
Test #35:
score: 0
Accepted
time: 2ms
memory: 7568kb
input:
100 1000 1000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 2...
output:
62 25 100 79 10 20 21 98
result:
ok single line: '62 25 100 79 10 20 21 98 '
Test #36:
score: 0
Accepted
time: 3ms
memory: 6064kb
input:
100 1000 10000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 ...
output:
1 26 86 42 33 73 51 23 3 19 72 92 97 30 90 14 31 61 38 36
result:
ok single line: '1 26 86 42 33 73 51 23 3 19 72 92 97 30 90 14 31 61 38 36 '
Test #37:
score: 0
Accepted
time: 4ms
memory: 8260kb
input:
100 1000 100000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160...
output:
57 2 24 26 86 9 49 82 44 33 65 73 51 66 13 43 23 3 55 84 19 12 92 97 30 10 63 20 71 35 45 6 16 77 21 98 37
result:
ok single line: '57 2 24 26 86 9 49 82 44 33 65...3 20 71 35 45 6 16 77 21 98 37 '
Test #38:
score: 0
Accepted
time: 5ms
memory: 7516kb
input:
100 1000 1000000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -716...
output:
57 29 2 1 24 74 18 86 9 49 82 91 42 44 33 32 68 65 83 73 51 66 93 78 34 43 100 7 79 3 11 52 55 84 75 19 12 72 8 92 53 97 30 10 90 87 17 20 71 14 35 58 45 96 61 94 16 54 50 21 60 36 37
result:
ok single line: '57 29 2 1 24 74 18 86 9 49 82 ... 96 61 94 16 54 50 21 60 36 37 '
Test #39:
score: 0
Accepted
time: 0ms
memory: 6252kb
input:
150 1000 100 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 28...
output:
73 34 88 92 96
result:
ok single line: '73 34 88 92 96 '
Test #40:
score: 0
Accepted
time: 4ms
memory: 6056kb
input:
150 1000 1000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 2...
output:
116 62 73 34 19 72 92 14 104 136
result:
ok single line: '116 62 73 34 19 72 92 14 104 136 '
Test #41:
score: 0
Accepted
time: 7ms
memory: 8944kb
input:
150 1000 10000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 ...
output:
1 26 86 42 33 25 34 122 88 19 72 92 97 30 90 14 31 61 38 36 123
result:
ok single line: '1 26 86 42 33 25 34 122 88 19 72 92 97 30 90 14 31 61 38 36 123 '
Test #42:
score: 0
Accepted
time: 4ms
memory: 10000kb
input:
150 1000 100000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160...
output:
57 145 2 119 74 26 103 9 49 82 44 62 95 69 40 138 139 34 43 23 3 55 84 19 12 92 97 30 10 63 20 71 35 45 6 81 143 99 21 131 98 37
result:
ok single line: '57 145 2 119 74 26 103 9 49 82...35 45 6 81 143 99 21 131 98 37 '
Test #43:
score: 0
Accepted
time: 3ms
memory: 13828kb
input:
150 1000 1000000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -716...
output:
29 110 28 1 119 24 74 26 103 86 9 116 140 67 42 44 113 33 32 68 65 83 73 51 66 138 139 106 78 34 43 100 7 79 3 11 52 55 84 75 19 12 72 148 120 132 97 144 112 70 10 90 87 63 146 20 71 14 35 58 45 96 61 94 109 16 77 147 118 21 38 131 98 37 123
result:
ok single line: '29 110 28 1 119 24 74 26 103 8...77 147 118 21 38 131 98 37 123 '
Test #44:
score: 0
Accepted
time: 1ms
memory: 7200kb
input:
20 1000 100 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352
output:
19 14
result:
ok single line: '19 14 '
Test #45:
score: 0
Accepted
time: 1ms
memory: 6596kb
input:
20 1000 1000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352
output:
4 12 20 16
result:
ok single line: '4 12 20 16 '
Test #46:
score: 0
Accepted
time: 1ms
memory: 6988kb
input:
20 1000 10000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352
output:
1 9 13 4 12 10 17 6
result:
ok single line: '1 9 13 4 12 10 17 6 '
Test #47:
score: 0
Accepted
time: 1ms
memory: 7148kb
input:
20 1000 100000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352
output:
1 18 9 13 7 3 12 8 10 20 14 6 16
result:
ok single line: '1 18 9 13 7 3 12 8 10 20 14 6 16 '
Test #48:
score: 0
Accepted
time: 1ms
memory: 6800kb
input:
20 1000 10000000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352
output:
2 1 5 18 9 13 7 3 11 4 19 12 8 10 15 17 20 14 6 16
result:
ok single line: '2 1 5 18 9 13 7 3 11 4 19 12 8 10 15 17 20 14 6 16 '
Test #49:
score: 0
Accepted
time: 9ms
memory: 7248kb
input:
250 1000 100 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 28...
output:
73 34 88 92 96 236
result:
ok single line: '73 34 88 92 96 236 '
Test #50:
score: 0
Accepted
time: 8ms
memory: 8796kb
input:
250 1000 1000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 2...
output:
116 62 186 135 75 148 241 233 71 109 204 37
result:
ok single line: '116 62 186 135 75 148 241 233 71 109 204 37 '
Test #51:
score: 0
Accepted
time: 21ms
memory: 13340kb
input:
250 1000 10000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 ...
output:
1 159 215 140 194 250 95 219 138 78 181 43 205 3 184 72 92 97 30 90 71 45 200 76 81 118 60 224
result:
ok single line: '1 159 215 140 194 250 95 219 1... 90 71 45 200 76 81 118 60 224 '
Test #52:
score: 0
Accepted
time: 32ms
memory: 19896kb
input:
250 1000 100000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160...
output:
57 128 119 24 159 26 86 9 49 82 226 44 33 214 221 111 163 171 172 121 13 43 205 23 170 190 55 84 158 19 12 148 53 241 144 198 225 87 71 126 47 152 200 213 168 232 54 38 131 98 37 185
result:
ok single line: '57 128 119 24 159 26 86 9 49 8...13 168 232 54 38 131 98 37 185 '
Test #53:
score: 0
Accepted
time: 46ms
memory: 31268kb
input:
250 1000 1000000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -716...
output:
57 192 110 193 28 1 119 24 74 26 103 86 156 101 215 189 22 140 82 91 42 108 245 33 32 68 221 65 40 207 219 51 25 172 121 13 34 181 183 240 177 100 7 218 79 46 3 4 135 56 237 75 19 162 12 72 8 92 53 239 144 30 228 48 90 225 87 63 146 20 124 14 195 35 45 47 152 200 206 61 94 109 176 16 77 147 118 21 3...
result:
ok single line: '57 192 110 193 28 1 119 24 74 ... 38 131 248 98 173 222 185 201 '
Test #54:
score: 0
Accepted
time: 58ms
memory: 44892kb
input:
250 1000 10000000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -71...
output:
27 89 57 192 29 110 128 193 145 2 1 5 119 166 24 74 216 26 80 103 86 156 199 101 115 208 215 9 22 169 49 194 82 91 226 42 44 108 245 250 33 32 191 95 182 160 221 65 69 167 111 83 207 186 163 51 25 41 138 139 93 150 13 34 181 153 178 177 43 100 102 7 23 151 79 46 170 175 11 4 135 190 52 88 55 137 84 ...
result:
ok single line: '27 89 57 192 29 110 128 193 14... 98 36 236 173 136 123 185 201 '
Test #55:
score: 0
Accepted
time: 89ms
memory: 63684kb
input:
250 100 10000000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -716...
output:
188 27 142 89 247 57 192 29 196 110 128 193 145 2 212 28 133 1 5 119 166 24 74 159 39 26 80 105 134 18 103 149 86 156 199 244 101 115 114 208 215 189 9 22 116 169 140 49 194 82 127 67 91 226 42 44 113 108 245 250 33 62 32 214 191 95 182 68 160 187 221 65 69 167 111 40 83 207 73 186 163 219 157 51 25...
result:
ok single line: '188 27 142 89 247 57 192 29 19...37 173 222 231 136 123 185 201 '
Test #56:
score: 0
Accepted
time: 88ms
memory: 65308kb
input:
250 10 10000000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160...
output:
188 27 142 89 247 57 192 29 196 110 128 193 145 2 223 212 28 133 1 5 119 166 24 74 159 216 39 26 80 105 134 18 103 149 86 156 199 244 101 115 114 208 215 189 9 22 116 169 140 49 194 82 127 67 91 226 42 44 113 108 245 250 33 62 32 214 191 95 182 68 160 187 221 65 69 167 111 40 83 207 73 186 163 219 1...
result:
ok single line: '188 27 142 89 247 57 192 29 19...73 224 222 231 136 123 185 201 '
Test #57:
score: 0
Accepted
time: 101ms
memory: 64624kb
input:
250 1 10000000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 ...
output:
188 27 142 89 247 57 192 29 196 110 128 193 145 2 223 212 28 133 1 5 119 166 24 74 159 216 39 26 80 105 134 18 103 149 86 156 199 244 101 115 114 208 215 189 9 22 116 169 140 49 194 82 127 67 91 226 42 44 113 108 245 250 33 62 32 214 191 95 182 68 160 187 221 65 69 167 111 40 83 207 73 186 163 219 1...
result:
ok single line: '188 27 142 89 247 57 192 29 19...73 224 222 231 136 123 185 201 '
Test #58:
score: 0
Accepted
time: 1ms
memory: 6968kb
input:
50 1000 100 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 288...
output:
4 30
result:
ok single line: '4 30 '
Test #59:
score: 0
Accepted
time: 0ms
memory: 6240kb
input:
50 1000 1000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 28...
output:
13 7 10 20 35 37
result:
ok single line: '13 7 10 20 35 37 '
Test #60:
score: 0
Accepted
time: 1ms
memory: 6580kb
input:
50 1000 10000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 2...
output:
1 26 42 33 25 23 3 12 10 20 35 16 37
result:
ok single line: '1 26 42 33 25 23 3 12 10 20 35 16 37 '
Test #61:
score: 0
Accepted
time: 0ms
memory: 7092kb
input:
50 1000 100000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160 ...
output:
1 24 18 22 42 44 32 25 13 43 23 3 12 8 30 10 15 35 45 6 16 21 36
result:
ok single line: '1 24 18 22 42 44 32 25 13 43 2...12 8 30 10 15 35 45 6 16 21 36 '
Test #62:
score: 0
Accepted
time: 1ms
memory: 6492kb
input:
50 1000 1000000 1204 616 -3002 565 -3362 4992 15 5064 8596 661 9004 8411 3333 4613 -4814 6136 9846 1695 3605 6918 -7412 5034 772 5861 3135 3921 -1916 7612 7266 7091 7270 8707 6574 7262 -5683 1305 -968 5659 3600 7352 1960 9180 -6773 1793 -3857 4676 -1662 925 593 3552 3418 1233 -5548 65 3206 574 -7160...
output:
29 2 1 24 26 18 9 49 42 44 33 32 40 25 41 13 34 7 23 46 3 4 19 12 8 30 48 10 15 17 20 14 35 45 47 6 16 21 38 36 37
result:
ok single line: '29 2 1 24 26 18 9 49 42 44 33 ...0 14 35 45 47 6 16 21 38 36 37 '
Test #63:
score: 0
Accepted
time: 8ms
memory: 9860kb
input:
250 123 38 586 100 -649 100 783 100 -502 100 527 100 715 100 -273 100 -219 100 72 100 -352 100 -702 200 815 200 447 200 -991 200 -525 200 516 200 -550 200 143 200 408 200 153 200 -630 300 -554 300 -516 300 505 300 363 300 -167 300 460 300 -611 300 -487 300 -101 300 180 400 16 400 -761 400 -925 400 3...
output:
36 57 77 91 95 113 125 141 162 179 205 213 230 239
result:
ok single line: '36 57 77 91 95 113 125 141 162 179 205 213 230 239 '
Test #64:
score: 0
Accepted
time: 14ms
memory: 9752kb
input:
250 123 69 445 100 -840 100 231 100 62 100 841 100 -954 100 658 100 30 100 -401 100 305 100 -903 200 -777 200 -782 200 -480 200 -661 200 -761 200 -823 200 -592 200 170 200 -742 200 -536 300 -318 300 -229 300 -198 300 862 300 -453 300 -431 300 -563 300 665 300 -894 300 -225 400 -395 400 -524 400 -683...
output:
24 37 51 66 73 98 117 127 141 180 184 195 201 226 237 243
result:
ok single line: '24 37 51 66 73 98 117 127 141 180 184 195 201 226 237 243 '
Test #65:
score: 0
Accepted
time: 12ms
memory: 9676kb
input:
250 123 97 303 100 971 100 122 100 -932 100 -846 100 -622 100 -855 100 278 100 684 100 962 100 -661 200 -811 200 -453 200 31 200 -355 200 -36 200 904 200 231 200 -511 200 806 200 -442 300 362 300 57 300 -902 300 917 300 819 300 678 300 -514 300 -627 300 313 300 929 400 -806 400 -287 400 -440 400 73 ...
output:
14 23 35 47 53 74 83 91 111 126 138 159 164 177 186 205 213 229 231 242
result:
ok single line: '14 23 35 47 53 74 83 91 111 12...64 177 186 205 213 229 231 242 '
Test #66:
score: 0
Accepted
time: 20ms
memory: 11932kb
input:
250 124 61 846 100 -300 100 260 100 -745 100 -780 100 553 200 -328 200 -464 200 499 200 -2 200 574 300 1 300 -101 300 809 300 93 300 -190 400 750 400 -223 400 446 400 -397 400 74 500 -968 500 715 500 -71 500 228 500 838 600 171 600 -626 600 -715 600 -214 600 954 700 -316 700 -577 700 -905 700 589 70...
output:
10 12 30 32 43 59 72 84 87 98 102 118 128 135 139 155 159 165 176 193 201 212 219 226 237 246
result:
ok single line: '10 12 30 32 43 59 72 84 87 98 ...76 193 201 212 219 226 237 246 '
Test #67:
score: 0
Accepted
time: 17ms
memory: 14248kb
input:
250 124 71 951 200 -53 199 -84 200 3 201 163 202 -362 302 166 299 -490 300 -208 301 570 300 1 398 231 400 -127 400 -148 401 -864 402 750 500 633 498 561 501 359 499 697 502 -731 599 -983 600 -455 601 -461 601 -831 599 527 702 -90 701 411 700 978 699 -372 699 -157 800 679 802 -118 799 327 798 933 801...
output:
7 12 26 40 45 52 61 77 82 90 96 106 121 126 131 141 159 161 175 183 190 203 208 218 226 232 242 246
result:
ok single line: '7 12 26 40 45 52 61 77 82 90 9...90 203 208 218 226 232 242 246 '