QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408301#2295. Dyson CircleAndycipationAC ✓384ms8944kbC++202.7kb2024-05-10 00:47:412024-05-10 00:47:43

Judging History

This is the latest submission verdict.

  • [2024-05-10 00:47:43]
  • Judged
  • Verdict: AC
  • Time: 384ms
  • Memory: 8944kb
  • [2024-05-10 00:47:41]
  • Submitted

answer

/*
 * author:  ADMathNoob
 * created: 05/09/24 12:12:19
 * problem: https://qoj.ac/problem/2295
 */

/*
Comments about problem:


*/

#include <bits/stdc++.h>

using namespace std;

#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  if (n == 1) {
    cout << 4 << '\n';
    return 0;
  }
  vector<int> x(n), y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }
  for (int rot = 0; rot < 2; rot++) {
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
      d[i] = x[i] - y[i];
    }
    if (count(d.begin(), d.end(), d[0]) == n) {
      int minX = *min_element(x.begin(), x.end());
      int maxX = *max_element(x.begin(), x.end());
      int delta = maxX - minX;
      cout << 2 * delta + 5 << '\n';
      return 0;
    }
    for (int i = 0; i < n; i++) {
      x[i] = -x[i];
    }
  }
  const int inf = 1e9;
  int ans = 0;
  for (int rot = 0; rot < 4; rot++) {
    // build the top-right diagonal
    int y1 = *max_element(y.begin(), y.end());
    int x2 = *max_element(x.begin(), x.end());
    int x1 = inf;
    int y2 = -inf;
    for (int i = 0; i < n; i++) {
      if (y[i] == y1) {
        x1 = min(x1, x[i]);
      }
      if (x[i] == x2) {
        y2 = max(y2, y[i]);
      }
    }
    y1 += 1;
    x2 += 1;
    
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return x[i] > x[j];
    });
    int maxY = -inf;
    int beg = 0;
    vector<pair<int, int>> suf;
    while (beg < n) {
      int end = beg;
      while (end < n && x[order[end]] == x[order[beg]]) ++end;
      for (int i = beg; i < end; i++) {
        maxY = max(maxY, y[order[i]]);
      }
      suf.emplace_back(x[order[beg]], maxY);
      beg = end;
    }
    reverse(suf.begin(), suf.end());
    // debug(suf);

    auto Exists = [&](int x0, int y0) {
      // does there exist a point (x, y) with x >= x0, y >= y0?
      auto it = lower_bound(suf.begin(), suf.end(), make_pair(x0, -inf));
      if (it == suf.end()) return false;
      return it->second >= y0;
    };
    
    int cx = x1, cy = y1;
    int res = 0;
    while (cx != x2) {
      assert(!Exists(cx, cy));
      if (Exists(cx + 1, cy - 1)) {
        cx += 1;
      } else {
        cx += 1;
        cy -= 1;
      }
      res += 1;
      // debug(cx, cy);
    }
    assert(cy >= y2);
    res += cy - y2;
    // debug(res);
    ans += res;
    
    // next iteration
    for (int i = 0; i < n; i++) {
      int nx = y[i];
      int ny = -x[i];
      x[i] = nx;
      y[i] = ny;
    }
  }
  cout << ans << '\n';
  return 0;
}

详细

Test #1:

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

input:

1
-201504 -209794

output:

4

result:

ok single line: '4'

Test #2:

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

input:

2
23 42
24 43

output:

7

result:

ok single line: '7'

Test #3:

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

input:

2
23 42
24 41

output:

7

result:

ok single line: '7'

Test #4:

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

input:

2
-1000000 -1000000
1000000 1000000

output:

4000005

result:

ok single line: '4000005'

Test #5:

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

input:

2
1000000 -1000000
-1000000 1000000

output:

4000005

result:

ok single line: '4000005'

Test #6:

score: 0
Accepted
time: 24ms
memory: 3564kb

input:

2
-1000000 -1000000
1000000 999999

output:

4000004

result:

ok single line: '4000004'

Test #7:

score: 0
Accepted
time: 25ms
memory: 3528kb

input:

2
-1000000 -1000000
999999 1000000

output:

4000004

result:

ok single line: '4000004'

Test #8:

score: 0
Accepted
time: 25ms
memory: 3580kb

input:

2
1000000 -1000000
-1000000 999999

output:

4000004

result:

ok single line: '4000004'

Test #9:

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

input:

2
1000000 -1000000
-999999 1000000

output:

4000004

result:

ok single line: '4000004'

Test #10:

score: 0
Accepted
time: 25ms
memory: 3524kb

input:

2
4711 -1000000
4711 1000000

output:

4000004

result:

ok single line: '4000004'

Test #11:

score: 0
Accepted
time: 25ms
memory: 3524kb

input:

2
1000000 4711
-1000000 4711

output:

4000004

result:

ok single line: '4000004'

Test #12:

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

input:

7
-53 94
-71 20
-93 -75
62 30
-90 36
22 -45
-17 -28

output:

478

result:

ok single line: '478'

Test #13:

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

input:

3
66 -48
-97 45
63 -70

output:

349

result:

ok single line: '349'

Test #14:

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

input:

1
-77 10

output:

4

result:

ok single line: '4'

Test #15:

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

input:

4
60 83
20 -33
-69 51
54 -60

output:

399

result:

ok single line: '399'

Test #16:

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

input:

4
2 70
66 -44
13 -23
-61 -11

output:

326

result:

ok single line: '326'

Test #17:

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

input:

10
-93 -97
-9 95
-35 94
-68 -16
-58 37
19 -99
-29 23
14 -60
-37 -48
-47 -99

output:

527

result:

ok single line: '527'

Test #18:

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

input:

10
18 -100
-24 24
-75 -89
-42 8
-80 62
93 25
-98 -19
-51 72
4 32
25 25

output:

546

result:

ok single line: '546'

Test #19:

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

input:

6
37 12
29 -27
-62 -50
11 -53
44 -15
-77 70

output:

376

result:

ok single line: '376'

Test #20:

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

input:

4
-6 -48
-64 -37
80 -5
3 64

output:

326

result:

ok single line: '326'

Test #21:

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

input:

8
-16 -72
-86 -53
90 -57
-59 28
56 47
91 13
-60 -21
-78 41

output:

513

result:

ok single line: '513'

Test #22:

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

input:

8
76 -67
-88 97
-20 29
-50 59
-39 48
27 -18
34 -25
56 -47

output:

333

result:

ok single line: '333'

Test #23:

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

input:

8
31 74
-53 -10
21 64
30 73
57 100
-52 -9
15 58
50 93

output:

225

result:

ok single line: '225'

Test #24:

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

input:

9
29 -3
96 64
2 -30
49 17
-32 -64
27 -5
55 23
21 -11
-66 -98

output:

329

result:

ok single line: '329'

Test #25:

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

input:

3
-15 -41
96 70
92 66

output:

227

result:

ok single line: '227'

Test #26:

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

input:

9
20 37
31 26
72 -15
-25 82
58 -1
76 -19
22 35
26 31
34 23

output:

207

result:

ok single line: '207'

Test #27:

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

input:

9
-13 -85
-98 0
-96 -2
-12 -86
-82 -16
-80 -18
-6 -92
-70 -28
-93 -5

output:

189

result:

ok single line: '189'

Test #28:

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

input:

8
-99 -79
-34 -14
68 88
-42 -22
-28 -8
6 26
4 24
14 34

output:

339

result:

ok single line: '339'

Test #29:

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

input:

6
-49 -72
-6 -29
61 38
92 69
-33 -56
-3 -26

output:

287

result:

ok single line: '287'

Test #30:

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

input:

8
26 -95
25 -94
-54 -15
-15 -54
22 -91
-39 -30
-50 -19
-25 -44

output:

165

result:

ok single line: '165'

Test #31:

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

input:

9
67 33
74 26
15 85
18 82
37 63
50 50
25 75
65 35
44 56

output:

123

result:

ok single line: '123'

Test #32:

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

input:

928
9500 1342
-7881 -5408
-6068 2272
764 -9877
-5181 -4671
2693 -1209
-3812 740
-7435 -7344
651 -3291
-4600 5063
8754 -328
1773 2138
7600 -74
-1670 -3442
6797 -4644
-2210 1409
7503 -6035
-958 9285
193 -5508
7249 -657
-5131 -8697
5096 -7891
-9423 2007
-3245 -3779
6887 -9459
-9269 647
6908 6326
3645 6...

output:

77873

result:

ok single line: '77873'

Test #33:

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

input:

169
6936 5081
5618 8088
-5765 -9632
5222 -8105
6474 -3280
-2624 9418
-3808 4388
-5907 3256
-2304 -1222
-2858 9116
3688 562
8021 -2717
9742 -2383
-2260 643
-7695 -3694
5694 809
9918 7229
7157 -8613
6628 9313
91 -4074
-5235 -1485
-7080 8703
7513 1894
-9582 -588
-2942 788
3007 -1539
-7216 -3973
3812 -6...

output:

70155

result:

ok single line: '70155'

Test #34:

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

input:

982
1816 -5967
-4260 -1809
-2231 -2712
844 -4972
-9502 -5807
4573 803
-165 -9542
5213 -4586
8204 -9338
-5987 5346
-2776 259
-8713 1220
5567 -9971
-9162 1136
-7821 3489
6955 1572
-3224 3616
-3771 -6699
8798 -5005
-4546 8265
4880 7595
8935 -7607
-7651 3702
-2959 -7771
4835 3799
4721 -5351
-3920 7617
9...

output:

76110

result:

ok single line: '76110'

Test #35:

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

input:

948
7264 8780
-8677 -2160
8517 -1833
1779 -8096
-372 -2433
9531 413
-2236 9743
9776 -2165
-2317 9848
-3255 7550
9080 -1872
1160 8144
360 -8478
8353 -4707
3244 7922
-1059 -2763
1873 -4106
6868 -34
5996 -8327
8969 722
-6024 1189
4137 589
3556 590
-1135 7561
6797 7066
3761 4542
6382 9066
3114 8561
9398...

output:

75323

result:

ok single line: '75323'

Test #36:

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

input:

730
-1743 -5203
-8233 913
-3735 1872
5071 2264
7527 2290
7827 4860
-5248 -9172
2768 7223
-4685 -2793
-1314 -3543
-331 -9886
-8989 4887
7985 8844
5984 -50
-9607 2860
-5311 5312
8426 1651
424 6430
8629 -2438
303 -309
-897 7570
8705 -3474
944 -8738
-6588 -1574
9113 3324
-5477 -5032
7654 -9986
-5007 710...

output:

74922

result:

ok single line: '74922'

Test #37:

score: 0
Accepted
time: 271ms
memory: 7924kb

input:

141317
-274942 -682201
-186052 -834038
-100601 61727
-944698 131823
635222 867300
-239410 817250
374969 -790867
-634764 -180132
170347 -815536
-517742 -6722
233434 -165940
-664181 523395
-705446 -753154
-793193 -360072
273024 -790792
581243 464110
-275845 -813563
725947 -118324
-797098 250331
884513...

output:

7974752

result:

ok single line: '7974752'

Test #38:

score: 0
Accepted
time: 68ms
memory: 3856kb

input:

3219
799461 -763629
-845801 -828705
436218 602504
64013 119629
-145168 23186
336602 -109589
602702 586542
131754 579855
-920365 -764639
179226 954008
-867415 959133
276457 158237
974550 316414
163430 264439
-647957 562192
-544042 -675651
-21138 -853886
-270398 525889
633758 731146
859843 789223
-553...

output:

7897260

result:

ok single line: '7897260'

Test #39:

score: 0
Accepted
time: 98ms
memory: 3884kb

input:

20296
872721 871788
928806 299409
352690 -755652
-332775 70799
-458562 664306
796842 -379164
-370289 557717
-435954 916731
-394675 -15900
417387 -920207
-493742 -157086
873833 -40616
79906 840493
538679 -450830
181308 395172
-880496 536539
-253127 153008
-759596 -968053
-144713 405014
-305183 -13728...

output:

7930553

result:

ok single line: '7930553'

Test #40:

score: 0
Accepted
time: 290ms
memory: 8944kb

input:

200000
-282804 959107
-747453 48772
-484768 -296154
482756 -763650
-435017 693599
-978517 640299
-121371 -683431
-77727 -710560
703571 885689
-335235 847996
-620488 891368
851990 -144059
56422 75285
853527 -382440
-274932 662212
654877 -205493
166985 -663763
-80386 -608151
749100 794472
685651 42769...

output:

7970085

result:

ok single line: '7970085'

Test #41:

score: 0
Accepted
time: 384ms
memory: 7372kb

input:

200000
-1000000 383683
1000000 905265
-474152 -1000000
787627 1000000
-1000000 -820522
-840177 1000000
1000000 -88481
-1000000 -170781
-172081 -1000000
-367521 -1000000
-766211 -1000000
-377722 -1000000
1000000 -58096
-1000000 -11022
-235995 -1000000
-1000000 -924069
396030 1000000
1000000 495411
49...

output:

7999928

result:

ok single line: '7999928'

Test #42:

score: 0
Accepted
time: 23ms
memory: 5392kb

input:

200000
-113124 681399
-646832 147691
105913 900436
-782103 12420
-254677 539846
-75306 719217
32514 827037
71770 866293
-404302 390221
-714475 80048
91667 886190
-728326 66197
-887910 -93387
-440470 354053
-301100 493423
-769098 25425
-803965 -9442
120598 915121
-74363 720160
124557 919080
-124198 6...

output:

2410937

result:

ok single line: '2410937'

Test #43:

score: 0
Accepted
time: 43ms
memory: 3576kb

input:

4
-1000000 -1000000
-1000000 1000000
1000000 -1000000
1000000 1000000

output:

8000004

result:

ok single line: '8000004'