UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#183554#3293. 赛车高手mH1001304ms3452kbC++11977b2023-08-09 10:42:242023-08-09 12:34:54

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t;
int solve(int x)
{
  if (!x)
    return 1;
  int l = 2, r = 1e10, mid, nowl, nowr;
  while (l <= r)
  {
    mid = l + r >> 1;
    if (mid % 2 == 0)
      nowr = (mid / 2) * (mid / 2 + 1) / 2 + ((mid - 2) / 2) * ((mid - 2) / 2 + 1) / 2, nowl = nowr - mid / 2 + 1;
    else
      mid++, nowr = (mid / 2) * (mid / 2 + 1) / 2 + ((mid - 2) / 2) * ((mid - 2) / 2 + 1) / 2 - mid / 2, mid--, nowl = nowr - mid / 2 + 1;
    if (nowl <= x && x <= nowr)
      return mid;
    if (nowl < x)
      l = mid + 1;
    else
      r = mid - 1;
  }
  return 1;
}
signed main()
{
#ifndef ONLINE_JUDGE
  freopen("data/data.in", "r", stdin);
// freopen("data/data.out", "w", stdout);
#endif
  std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> t;
  while (t--)
  {
    int x, y;
    cin >> x >> y;
    cout << max(solve(x) - 1, solve(y) - 1) << '\n';
  }
  exit(0);
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 12
Accepted

Test #1:

score: 12
Accepted
time: 0ms
memory: 3316kb

input:

5
5 2
4 4
3 5
1 7
7 0

output:

4
3
4
5
5

result:

ok 5 number(s): "4 3 4 5 5"

Test #2:

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

input:

5
4 3
5 1
3 5
5 4
0 3

output:

3
4
4
4
3

result:

ok 5 number(s): "3 4 4 4 3"

Test #3:

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

input:

5
2 4
7 7
3 4
1 0
2 5

output:

3
5
3
1
4

result:

ok 5 number(s): "3 5 3 1 4"

Test #4:

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

input:

5
1 5
0 4
3 4
5 5
3 0

output:

4
3
3
4
3

result:

ok 5 number(s): "4 3 3 4 3"

Test #5:

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

input:

5
7 2
2 0
0 0
3 4
1 3

output:

5
2
0
3
3

result:

ok 5 number(s): "5 2 0 3 3"

Test #6:

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

input:

5
6 3
4 6
0 0
0 1
3 6

output:

4
4
0
1
4

result:

ok 5 number(s): "4 4 0 1 4"

Subtask #2:

score: 18
Accepted

Test #7:

score: 18
Accepted
time: 2ms
memory: 3392kb

input:

1000
34 32
44 38
40 40
36 33
35 42
50 39
47 44
35 46
43 42
48 44
36 47
47 34
39 37
41 43
46 45
46 38...

output:

11
13
12
11
12
14
13
13
13
13
13
13
12
13
13
13
11
13
14
13
12
13
11
13
14
13
13
12
11
14
13
13
12
1...

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 3ms
memory: 3416kb

input:

1000
37 30
40 45
30 49
37 46
36 38
42 31
47 35
32 44
43 32
35 30
41 43
48 36
31 50
48 35
35 48
42 31...

output:

12
13
13
13
12
12
13
13
13
11
13
13
14
13
13
12
11
13
12
11
12
13
12
12
12
12
13
13
13
13
13
11
13
1...

result:

ok 1000 numbers

Subtask #3:

score: 23
Accepted

Test #9:

score: 23
Accepted
time: 40ms
memory: 3328kb

input:

100000
841 838
231 460
847 778
618 476
156 915
513 746
799 514
104 726
890 483
768 609
342 200
998 5...

output:

57
42
58
49
60
54
56
53
59
55
36
63
48
60
57
59
49
32
63
35
43
44
47
22
60
57
52
52
44
61
53
60
42
5...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 53ms
memory: 3336kb

input:

100000
912 98
419 152
759 739
470 38
553 325
253 380
502 424
424 360
427 47
900 214
611 795
147 477
...

output:

60
40
55
43
47
38
44
41
41
59
56
43
59
47
58
26
29
51
49
53
62
43
58
55
56
38
62
61
59
59
51
61
32
5...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 53ms
memory: 3328kb

input:

100000
501 999
860 874
392 556
800 209
119 326
819 998
792 634
354 432
891 789
503 341
205 694
347 6...

output:

63
59
47
56
36
63
56
41
59
44
52
51
59
43
62
54
60
56
59
62
55
35
52
57
42
50
40
59
51
62
58
58
48
5...

result:

ok 100000 numbers

Subtask #4:

score: 21
Accepted

Test #12:

score: 21
Accepted
time: 7ms
memory: 3388kb

input:

10000
127242112 331239013
419887545 759000120
404003605 271909138
274815360 989671976
673172191 6209...

output:

36399
55099
40199
62918
51891
48658
56775
59812
58568
58586
60194
39375
56380
28525
55412
52989
5430...

result:

ok 10000 numbers

Test #13:

score: 0
Accepted
time: 7ms
memory: 3452kb

input:

10000
833191680 711905519
995892235 172495560
93436866 66456469
514928589 49749413
368451495 6435858...

output:

57730
63115
19332
45384
38390
34318
38990
60488
58428
39644
40888
56141
58409
46646
51185
47755
5111...

result:

ok 10000 numbers

Test #14:

score: 0
Accepted
time: 5ms
memory: 3436kb

input:

10000
393108867 859390517
304703077 995318776
350647871 438753568
485670762 106497250
783120224 9482...

output:

58630
63097
41892
44075
61587
17380
60705
50037
59567
46798
41746
48250
24109
42278
62359
60096
2981...

result:

ok 10000 numbers

Subtask #5:

score: 26
Accepted

Test #15:

score: 26
Accepted
time: 378ms
memory: 3384kb

input:

300000
700102399929944494 466914043647205576
963273968501598633 43742775117069954
241153529041271553...

output:

1673442439
1962930430
1397577702
1288005461
1826708623
1899820906
1157253013
1647448882
1927604378
1...

result:

ok 300000 numbers

Test #16:

score: 0
Accepted
time: 372ms
memory: 3436kb

input:

300000
914905156460489120 812430935117677043
317659731522230587 84827654902782275
657344151116347785...

output:

1913013493
1127226208
1621535261
1495988556
1256004714
1697822158
1973843358
1933507133
1212197277
1...

result:

ok 300000 numbers

Test #17:

score: 0
Accepted
time: 376ms
memory: 3452kb

input:

300000
591040884900350350 885831892853121821
828686318008633549 889473553177834500
23136283869037978...

output:

1882372856
1886238111
962003822
1710473454
1311321596
1281408943
1401553144
1716761705
1151792299
15...

result:

ok 300000 numbers