QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#465184#7674. SkiingCiriya666AC ✓232ms41304kbC++144.0kb2024-07-06 18:17:362024-07-06 18:17:36

Judging History

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

  • [2024-07-06 18:17:36]
  • 评测
  • 测评结果:AC
  • 用时:232ms
  • 内存:41304kb
  • [2024-07-06 18:17:36]
  • 提交

answer

#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

int N, Vy;
double Amax, tx[251], ty[251];

void velocity_interval(double x1, double y1, double x2, double y2,
    double sv1, double sv2, double& fv1, double& fv2) {
  if (x1 == x2 && y1 == y2) {fv1 = sv1; fv2 = sv2; return;}
  double d = x2-x1, t = y2-y1;
  sv1 = max(sv1, d/t - 0.5*Amax*t);
  sv2 = min(sv2, d/t + 0.5*Amax*t);
  if (sv1 > sv2) {fv1 = 1e50; fv2 = -1e50; return;}
  if (Amax == 0) {fv1 = sv1; fv2 = sv2; return;}

  // For maximal final velocity, start with min speed, decelerate for time u,
  // then accelerate.
  double a = Amax;
  double b = -2*t*Amax;
  double c = sv1*t + 0.5*Amax*t*t - d;
  double u = (-b - sqrt(max(0.0, b*b - 4*a*c))) / (2*a);
  fv2 = sv1 + Amax * ((t-u) - u);
//cout << sv1 << " -> " << fv2 << ": u = " << u << endl;

  // For minimal final velocity, start with max speed, accelerate for time u,
  // then decelerate.
  a = -Amax;
  b = 2*t*Amax;
  c = sv2*t - 0.5*Amax*t*t - d;
  u = (-b + sqrt(max(0.0, b*b - 4*a*c))) / (2*a);
  fv1 = sv2 + Amax * (u - (t-u));
//cout << sv2 << " -> " << fv1 << ": u = " << u << endl;
}

struct Interval {
  double v1, v2;
  int nt;
  Interval(double v1, double v2, int nt) : v1(v1), v2(v2), nt(nt) {}
  bool operator<(const Interval& i) const {
    if (nt != i.nt) return nt > i.nt;
    return v1 < i.v1;
  }
  friend ostream& operator<<(ostream& out, const Interval& i) {
    out << i.v1 << " to " << i.v2 << " (" << i.nt << ")";
    return out;
  }
};

main() {
  while (cin >> N) {
    cin >> Vy >> Amax;
    Amax /= Vy;
    vector<pair<double, int> > yv;
    yv.push_back(make_pair(0, 0));
    vector<vector<Interval> > v(N+1);
    for (int i = 1; i <= N; i++) {
      cin >> tx[i] >> ty[i];
      tx[i] /= Vy; ty[i] /= Vy;
      yv.push_back(make_pair(ty[i], i));
      v[i].push_back(Interval(-1e50, 1e50, 1));
    }
    sort(yv.begin(), yv.end());

    for (int yi = N; yi >= 0; yi--) {
      int y = yv[yi].second;

      // Merge intervals.
      sort(v[y].begin(), v[y].end());
      vector<Interval> v2;
      for (int i = 0; i < v[y].size(); i++) {
        if (v2.size() && v[y][i].nt == v2.back().nt
                      && v[y][i].v1 < v2.back().v2) {
          v2.back().v2 = max(v2.back().v2, v[y][i].v2);
        } else {
          v2.push_back(v[y][i]);
        }
      }
      v[y].swap(v2);
      //for (int i = 0; i < v[y].size(); i++) cout << y << ' ' << v[y][i] << endl;

      for (int x = 0; x <= N; x++) {
        if (ty[x] >= ty[y] && !(tx[x] == tx[y] && ty[x] == ty[y] && x < y))
          continue;
        for (int i = 0; i < v[y].size(); i++) {
          Interval& in = v[y][i];

          Interval in2(0.0, 0.0, in.nt+1);
          velocity_interval(tx[x], ty[x], tx[y], ty[y],
              in.v1, in.v2, in2.v1, in2.v2);
          if (in2.v1 <= in2.v2) v[x].push_back(in2);
        }
      }
    }

    int i, j;
    for (i = 0; i < v[0].size(); i++) {
      if (v[0][i].v1 <= 0.0 && v[0][i].v2 >= 0.0) break;
    }
    if (i == v[0].size()) {
      cout << "Cannot visit any targets" << endl;
    } else {
      double v1 = 0.0, v2 = 0.0, fv1, fv2;
      int t = 0, x = 0, y;
      for (int nt = v[0][i].nt-1; nt > 0; nt--) {
        for (y = 1; y <= N; y++) {
          if (ty[x] >= ty[y] && !(tx[x] == tx[y] && ty[x] == ty[y] && x < y))
            continue;
          velocity_interval(tx[x], ty[x], tx[y], ty[y], v1, v2, fv1, fv2);
          if (fv1 > fv2) continue;
          for (j = 0; j < v[y].size(); j++) {
            if (v[y][j].nt < nt) break;
            if (fv1 <= v[y][j].v2 && fv2 >= v[y][j].v1) break;
          }
          if (j < v[y].size() && v[y][j].nt == nt) {
            cout << y;
            if (nt == 1) cout << endl; else cout << ' ';
            x = y; v1 = fv1; v2 = fv2;
            break;
          }
          assert(y < N);
        }
      }
    }
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3752kb

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: 0ms
memory: 3828kb

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: 3752kb

input:

0 100 100

output:

Cannot visit any targets

result:

ok single line: 'Cannot visit any targets'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3688kb

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: 3692kb

input:

2 1000 2001
1000 1000
-1000 1000

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

3 10 30
10 10
-10 10
0 20

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3888kb

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: 0ms
memory: 3984kb

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: 0ms
memory: 3832kb

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: 0ms
memory: 3756kb

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: 3732kb

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: 0ms
memory: 3860kb

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: 214ms
memory: 38600kb

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 ...243 244 245 246 247 248 249 250'

Test #14:

score: 0
Accepted
time: 145ms
memory: 29752kb

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 ...240 241 243 244 246 247 249 250'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

1 100 100
0 0

output:

1

result:

ok single line: '1'

Test #16:

score: 0
Accepted
time: 160ms
memory: 32052kb

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...241 242 244 245 246 248 249 250'

Test #17:

score: 0
Accepted
time: 179ms
memory: 32928kb

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...241 242 243 245 246 247 248 250'

Test #18:

score: 0
Accepted
time: 198ms
memory: 34604kb

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...242 243 244 245 246 248 249 250'

Test #19:

score: 0
Accepted
time: 210ms
memory: 38284kb

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 ...243 244 245 246 247 248 249 250'

Test #20:

score: 0
Accepted
time: 232ms
memory: 38572kb

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 ...242 243 244 245 246 247 248 250'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

1 1000 2001
1000 1000

output:

1

result:

ok single line: '1'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3760kb

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: 0ms
memory: 3992kb

input:

2 100 200
0 100
182 200

output:

1 2

result:

ok single line: '1 2'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3984kb

input:

2 100 200
0 100
183 200

output:

1

result:

ok single line: '1'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

1 100 0
0 0

output:

1

result:

ok single line: '1'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3760kb

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: 0ms
memory: 3712kb

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: 3824kb

input:

1 100 0
0 100

output:

1

result:

ok single line: '1'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3764kb

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: 0ms
memory: 3716kb

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: 3996kb

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: 3700kb

input:

1 1000 10
-490 10000

output:

1

result:

ok single line: '1'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3768kb

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: 4156kb

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: 4144kb

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: 4ms
memory: 4380kb

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: 3ms
memory: 5160kb

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...63 20 71 35 45 6 16 77 21 98 37'

Test #38:

score: 0
Accepted
time: 9ms
memory: 5852kb

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 ...5 96 61 94 16 54 50 21 60 36 37'

Test #39:

score: 0
Accepted
time: 0ms
memory: 4324kb

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: 4624kb

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: 9ms
memory: 5816kb

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: 15ms
memory: 7424kb

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: 22ms
memory: 10172kb

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: 0ms
memory: 3852kb

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: 0ms
memory: 3760kb

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: 0ms
memory: 3800kb

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: 0ms
memory: 3868kb

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: 0ms
memory: 4024kb

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: 11ms
memory: 5100kb

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: 15ms
memory: 6964kb

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: 26ms
memory: 10520kb

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...0 90 71 45 200 76 81 118 60 224'

Test #52:

score: 0
Accepted
time: 52ms
memory: 15472kb

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...213 168 232 54 38 131 98 37 185'

Test #53:

score: 0
Accepted
time: 91ms
memory: 22780kb

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 ...1 38 131 248 98 173 222 185 201'

Test #54:

score: 0
Accepted
time: 150ms
memory: 30960kb

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...1 98 36 236 173 136 123 185 201'

Test #55:

score: 0
Accepted
time: 219ms
memory: 41256kb

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: 212ms
memory: 41276kb

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...173 224 222 231 136 123 185 201'

Test #57:

score: 0
Accepted
time: 228ms
memory: 41304kb

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...173 224 222 231 136 123 185 201'

Test #58:

score: 0
Accepted
time: 1ms
memory: 3828kb

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: 1ms
memory: 3892kb

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: 0ms
memory: 3924kb

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: 1ms
memory: 3892kb

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 23 3 12 8 30 10 15 35 45 6 16 21 36'

Test #62:

score: 0
Accepted
time: 2ms
memory: 3880kb

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 ...20 14 35 45 47 6 16 21 38 36 37'

Test #63:

score: 0
Accepted
time: 15ms
memory: 7656kb

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: 18ms
memory: 8056kb

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: 20ms
memory: 8648kb

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...164 177 186 205 213 229 231 242'

Test #66:

score: 0
Accepted
time: 26ms
memory: 10168kb

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 ...176 193 201 212 219 226 237 246'

Test #67:

score: 0
Accepted
time: 30ms
memory: 10880kb

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...190 203 208 218 226 232 242 246'