QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#498761#7674. SkiingMax_s_xaMAC ✓101ms65308kbC++147.1kb2024-07-30 19:28:272024-07-30 19:28:27

Judging History

你现在查看的是最新测评结果

  • [2024-07-30 19:28:27]
  • 评测
  • 测评结果:AC
  • 用时:101ms
  • 内存:65308kb
  • [2024-07-30 19:28:27]
  • 提交

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;
}

詳細信息

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 '