QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#479207 | #5538. Magical Barrier | karuna | AC ✓ | 302ms | 27040kb | C++20 | 3.0kb | 2024-07-15 15:57:14 | 2024-07-15 15:57:14 |
Judging History
answer
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int SZ = 1010;
struct point {
ll x, y;
};
point operator+(point a, point b) { return {a.x + b.x, a.y + b.y}; }
point operator-(point a, point b) { return {a.x - b.x, a.y - b.y}; }
ll operator*(point a, point b) { return a.x * b.x + a.y * b.y; }
ll operator/(point a, point b) { return a.x * b.y - a.y * b.x; }
int ccw(point p, point q, point r) {
ll s = (q - p) / (r - p);
return (s > 0) - (s < 0);
}
int n; point P[SZ];
vector<int> O[SZ], R[SZ];
int cnt[SZ][SZ];
vector<int> pre[SZ];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> P[i].x >> P[i].y;
}
auto sgn = [&](point p) { return p.y == 0 ? p.x > 0 : p.y > 0; };
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) if (j != i) O[i].push_back(j);
sort(O[i].begin(), O[i].end(), [&](int j, int k) {
if (sgn(P[j] - P[i]) != sgn(P[k] - P[i])) {
return sgn(P[j] - P[i]);
}
else return ccw(P[i], P[j], P[k]) > 0;
});
R[i].resize(n);
for (int j = 0; j < n - 1; j++) R[i][O[i][j]] = j;
}
vector<pii> bdz;
int ord[n];
iota(ord, ord + n, 0);
sort(ord, ord + n, [&](int i, int j) {
return P[i].x == P[j].x ? P[i].y < P[j].y : P[i].x < P[j].x;
});
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
bdz.push_back({ord[j], ord[i]});
}
}
sort(bdz.begin(), bdz.end(), [&](pii a, pii b) {
auto [p, q] = a;
auto [r, s] = b;
return (P[q] - P[p]) / (P[s] - P[r]) > 0;
});
int pos[n];
for (int i = 0; i < n; i++) pos[ord[i]] = i;
for (auto [u, v] : bdz) {
assert(pos[v] == pos[u] + 1);
cnt[v][u] = pos[u];
cnt[u][v] = n - pos[v] - 1;
swap(pos[u], pos[v]);
swap(ord[pos[u]], ord[pos[v]]);
}
for (int i = 0; i < n; i++) {
pre[i].resize(2 * n - 1);
for (int j = 0; j < 2 * (n - 1); j++) {
pre[i][j + 1] = pre[i][j] + (cnt[O[i][j % (n - 1)]][i]) - j;
}
}
int ans = 0;
for (int u = 0; u < n; u++) {
for (int v = 0; v < u; v++) {
int cur = 0;
{
int pos = R[u][v] + 1;
int ss = pos, ee = pos + n - 2;
while (ss < ee) {
int k = (ss + ee) / 2;
int x = O[u][k % (n - 1)];
if (x == v || ccw(P[u], P[v], P[x]) < 0) ee = k;
else ss = k + 1;
}
cur += pre[u][ss] - pre[u][pos] + (ss - pos) * (pos - 1);
}
{
int pos = R[v][u] + (n - 1) - 1;
int ss = pos - (n - 2), ee = pos;
while (ss < ee) {
int k = (ss + ee + 1) / 2;
int x = O[v][k % (n - 1)];
if (x == u || ccw(P[u], P[v], P[x]) < 0) ss = k;
else ee = k - 1;
}
cur -= pre[v][pos + 1] - pre[v][ss + 1] + (pos - ss) * (ss + 1);
}
// cout << "(" << P[u].x << ", " << P[u].y << ") and (" << P[v].x << ", " << P[v].y << ") -> " << cur << "?\n";
// cout << u << " and " << v << " -> " << cur << "?\n";
ans = max(ans, cur);
}
}
cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3648kb
input:
6 0 0 0 6 6 0 6 6 1 4 1 2
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
2 0 0 0 1
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
4 -3 0 3 0 0 3 0 1
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
4 0 0 0 1 1 0 1 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
2 0 -1337 -5 -4
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 293ms
memory: 26880kb
input:
1000 496963365 -584310020 963238159 -571008004 18078662 -750762438 135156509 -968440195 77520950 -725908810 956053561 -538228505 806742035 -803854232 529068738 -825479182 64371444 -975013392 164324947 -824966981 629969244 -744727107 685160229 -787078273 985061882 -907085223 349370979 -716383138 4759...
output:
248984
result:
ok single line: '248984'
Test #7:
score: 0
Accepted
time: 160ms
memory: 20864kb
input:
785 898853675 -355443599 587710369 -109896349 65215177 -655940164 65656867 -722300646 152157112 -797929191 218594484 -368530385 174510182 -865407506 262993628 -702633530 644403903 -704799677 726216106 -191062003 14210758 -489976777 392385091 -423177763 932719998 -270137440 53134287 -527726316 533708...
output:
153255
result:
ok single line: '153255'
Test #8:
score: 0
Accepted
time: 25ms
memory: 9332kb
input:
359 368 212 21 338 179 276 352 131 223 285 206 56 103 34 300 212 36 215 277 421 395 122 52 32 18 165 148 409 174 0 24 243 203 84 39 53 144 359 316 80 59 178 370 232 9 265 381 205 38 127 294 419 16 41 41 373 266 221 120 282 293 310 413 325 6 366 249 130 357 257 214 279 375 188 142 126 364 280 351 269...
output:
31862
result:
ok single line: '31862'
Test #9:
score: 0
Accepted
time: 27ms
memory: 7196kb
input:
347 -23 206 -8 392 -298 386 -384 49 -268 16 -20 1 -91 305 -128 51 -37 11 -173 332 -311 21 -307 371 -226 105 -312 347 -380 246 -304 34 -362 84 -392 389 -45 84 -318 97 -171 254 -376 270 -243 129 -327 391 -27 145 0 283 -370 131 -44 33 -52 252 -261 169 -6 395 -34 261 -127 394 -219 345 -184 341 -57 189 -...
output:
29746
result:
ok single line: '29746'
Test #10:
score: 0
Accepted
time: 18ms
memory: 7968kb
input:
314 -309 -278 -302 -325 -269 -322 -241 -83 -8 -339 -92 -64 -9 -279 -28 -49 -155 -107 -152 -10 -260 -191 -175 -242 -66 -324 -87 -92 -60 -340 -121 -15 -219 -131 -68 -346 -214 -247 -25 -201 -98 -119 -214 -344 -126 -31 -127 -243 -27 -116 -6 -79 -315 -269 -135 -224 -132 -331 -127 -200 -21 -315 -280 -25 -...
output:
24326
result:
ok single line: '24326'
Test #11:
score: 0
Accepted
time: 21ms
memory: 6872kb
input:
333 38 220 232 267 285 111 312 122 119 194 233 321 377 172 271 186 22 135 260 94 196 62 104 212 105 57 315 362 313 363 133 359 170 24 274 333 402 236 283 67 91 288 182 136 226 361 383 326 149 34 243 292 232 64 255 293 189 330 211 322 272 347 373 336 313 355 340 144 409 151 12 141 68 101 320 248 229 ...
output:
27390
result:
ok single line: '27390'
Test #12:
score: 0
Accepted
time: 16ms
memory: 7180kb
input:
300 -65 84 -23 220 -188 146 -304 156 -53 290 -235 126 -306 113 -155 214 -102 76 -48 101 -93 307 -47 148 -285 298 -86 121 -196 322 -234 286 -311 213 -182 230 -299 82 -115 194 -172 348 -322 260 -25 264 -81 145 -220 80 -343 159 -209 141 -91 292 -148 173 -223 313 -79 315 -310 192 -76 80 -17 121 -149 27 ...
output:
22162
result:
ok single line: '22162'
Test #13:
score: 0
Accepted
time: 17ms
memory: 7600kb
input:
306 299 55 89 185 270 319 207 249 287 263 12 128 10 126 229 182 31 165 238 181 354 193 64 294 190 2 97 56 336 85 126 244 114 328 248 35 349 160 155 46 69 200 99 299 200 357 250 16 262 85 118 53 215 81 160 120 70 63 110 342 120 232 342 137 225 303 68 289 33 274 306 321 59 97 235 43 228 173 221 265 31...
output:
23086
result:
ok single line: '23086'
Test #14:
score: 0
Accepted
time: 289ms
memory: 26792kb
input:
1000 -3452 4035 2601 971 -586 37 0 0 -740 58 -1680 6688 3222 3201 1519 218 1908 6408 -921 6861 -3470 3688 1368 175 -2876 1271 -2892 1292 2892 5249 -637 6891 -561 6896 -2060 6519 -439 21 -829 73 2921 5180 -3457 3967 1063 6756 1896 6415 2881 5273 1713 289 -1259 179 3200 2729 -3395 4497 2774 1245 3151 ...
output:
249001
result:
ok single line: '249001'
Test #15:
score: 0
Accepted
time: 289ms
memory: 25896kb
input:
977 4169 -4398 4378 -4166 -305 -5703 1284 396 4844 3748 3540 5041 3699 -4787 2847 -5207 490 29 4857 -3380 -5392 1962 5488 -1111 -5293 -1741 1226 -5646 5379 -1747 -4120 -3586 347 2681 5220 2843 56 -5716 -5096 2910 -3948 4624 1577 2044 4309 4482 5600 505 -3392 4986 1066 2514 -4978 3201 4720 3960 1731 ...
output:
237656
result:
ok single line: '237656'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 5 7 -7 -5 7 -7
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 283ms
memory: 26644kb
input:
993 8295 -11130 -9583 9884 3554 -11777 7735 -11452 -8197 -13118 -12691 -8638 6073 -3699 99 -12566 -6160 -10501 -7903 11368 4507 -1268 10577 -9338 13727 -140 -6860 -3211 1577 -92 6318 -5541 258 -12561 1610 -96 -28 -12569 -12523 5684 -4528 -1007 -13643 532 4413 -1189 -7307 -4534 -444 -7 -7055 -8826 22...
output:
245520
result:
ok single line: '245520'
Test #18:
score: 0
Accepted
time: 292ms
memory: 26840kb
input:
999 5561 8060 1029 4971 2711 6880 14325 -6496 97 1759 12628 -7380 8 -352 1800 6070 16058 -4377 312 -2892 15335 5726 2884 6998 3685 7425 16878 -1435 884 -4660 606 4060 2942 -6974 8355 8425 3 254 13626 -6924 12783 7743 16507 -3302 16605 2833 3722 7441 10694 8226 14818 -6115 15768 5025 2604 18228 111 -...
output:
248502
result:
ok single line: '248502'
Test #19:
score: 0
Accepted
time: 297ms
memory: 26768kb
input:
1000 -968093280 -77108841 -973844126 224058363 -220744035 813592927 636250867 -228733410 -810943418 -244620353 200967604 -327656462 -866801495 -194346626 916176483 500630846 -498200646 791124654 931230541 9006759 988721448 173172090 -996080665 12268718 338183703 -310393279 -683642752 -287163485 9623...
output:
249000
result:
ok single line: '249000'
Test #20:
score: 0
Accepted
time: 302ms
memory: 26848kb
input:
1000 -757418723 90436380 492915528 -134295398 -874211525 16122778 204169465 -187891707 -242691367 172211001 963766011 -28817654 396669381 -120383389 -705351807 92084168 723125875 -10156233 -490438112 126496051 -966669223 -151601535 -781680399 46058924 -303311696 -276584325 149047354 125216314 580822...
output:
248975
result:
ok single line: '248975'
Test #21:
score: 0
Accepted
time: 290ms
memory: 26896kb
input:
1000 948937975 -400862981 949503258 -402633523 -62248656 -867263748 992412912 23306165 -294026734 -826355663 428366657 -836203727 117442085 945544383 799867257 560855266 -685754722 -565644358 338547350 895435744 -15463705 -871489332 -982752478 -52782254 -368876871 -795873560 405151165 870056639 -961...
output:
249001
result:
ok single line: '249001'
Test #22:
score: 0
Accepted
time: 292ms
memory: 27040kb
input:
1000 -527972426 -670577622 878502001 -387465887 251263072 -781530497 -853954408 -583082000 -769399469 -505745678 -129283302 -417659959 -352808972 -430246191 219886946 -800596228 652814103 -294264025 -421276344 -677366635 651801630 -532370572 352447876 -712646580 -441541536 -684056753 -842728937 -525...
output:
248949
result:
ok single line: '248949'
Test #23:
score: 0
Accepted
time: 245ms
memory: 24636kb
input:
942 -5947 3790 -5041 -1377 -2581 534 -3964 1667 -1151 148 -1008 128 -2076 -192 -4905 384 -3482 1145 -2045 -183 -5410 -2482 -7110 4815 -6510 -3727 -4903 305 -7961 5164 -7375 -4161 -4585 -2662 -5952 -3229 -4927 -651 -3766 1430 -9357 5379 -1273 167 -5832 -3092 -8291 -4384 -4931 881 -5149 -1796 -4674 31...
output:
220416
result:
ok single line: '220416'
Test #24:
score: 0
Accepted
time: 236ms
memory: 24536kb
input:
941 5386 -416 5048 -90 5491 -22 -4627 4490 -2715 5892 -2753 -876 -5388 -5807 -3276 -3399 -2446 -4293 1725 -449 -2394 -4120 5979 90 5100 -83 572 16 -471 -1404 -4664 4515 -2661 4529 -2529 3604 -976 864 -538 528 -2128 2359 -5308 -5767 -3584 3412 -1532 -2405 -2561 3773 -2737 603 -2709 5356 -2969 -2433 -...
output:
198674
result:
ok single line: '198674'
Test #25:
score: 0
Accepted
time: 266ms
memory: 25808kb
input:
974 5256 -701 2279 -59 -2264 946 -2162 6822 -2656 -3628 4290 -579 7985 -573 437 1028 -4411 -6752 12038 -1503 5913 -742 -3330 -5303 -4358 -6704 617 -2537 10163 -949 -3364 -5362 -717 2350 4098 -1078 11309 768 -1642 -5757 6079 -746 -4218 5603 10490 -1012 10328 192 -1610 4192 11825 -1409 4267 -575 5055 ...
output:
216328
result:
ok single line: '216328'
Test #26:
score: 0
Accepted
time: 257ms
memory: 26248kb
input:
987 -5539 1158 9914 -8901 9224 -8535 -12293 2195 1958 3107 3769 5388 1432 -861 3474 -2953 5091 -455 -2411 816 -2316 1349 8300 8074 -9710 802 8428 -8003 4841 8495 201 -144 7660 -7319 -3018 935 9124 8699 7869 -7522 2948 4129 8748 8432 -8146 1072 -10321 651 5162 1652 8988 8606 7005 6706 5318 2698 8536 ...
output:
221600
result:
ok single line: '221600'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
4 0 -5 5 0 1 1 1 5
output:
0
result:
ok single line: '0'
Test #28:
score: 0
Accepted
time: 266ms
memory: 26260kb
input:
983 -3074 -2437 2999 7501 14818 -2250 5472 -3245 3839 -2737 4856 2813 2939 9086 4068 14174 2947 8581 3328 12152 2788 10818 -4950 -2840 1322 -2312 -854 -567 -2057 -1335 7371 -4182 2781 6061 2869 10183 4399 14770 9877 -1207 -735 -472 15290 -2253 -3716 -2540 -3995 -2015 4489 14921 7388 -4193 3114 -2561...
output:
235280
result:
ok single line: '235280'
Test #29:
score: 0
Accepted
time: 278ms
memory: 26764kb
input:
996 500004311 -499999349 499995528 -500004324 160 500004385 -500002749 -500000746 -499998629 -500001288 -500002571 -500001322 1586 500002772 -500002579 -499999901 1632 500001714 -1306 499999484 1957 500002266 -500003862 -500001423 -3413 500003537 -3025 500003357 500001275 -500003374 500001833 -50000...
output:
246973
result:
ok single line: '246973'
Test #30:
score: 0
Accepted
time: 288ms
memory: 26668kb
input:
997 395 500003716 4072 -500004778 499996004 333337794 -500004409 -3591 -3153 499997226 -500000081 1990 -499997209 333335726 1918 500000293 -500001940 741 -500004910 333338117 -787 500004308 -499997413 2767 -500004232 333336772 -499997005 3471 -499997551 333329609 499997259 333333300 -545 -499996641 ...
output:
247490
result:
ok single line: '247490'
Test #31:
score: 0
Accepted
time: 272ms
memory: 26296kb
input:
988 -669 -845 1146 -680 635 -2777 5869 3520 371 -4316 -926 3776 2409 3916 -6474 5918 408 -4747 5485 4905 7139 6183 1374 -9960 -4381 4571 -1395 335 429 -6570 489 -6566 5053 3261 1074 -9289 516 -3771 1072 -920 428 -6597 504 -3926 1287 -9787 -7564 7240 972 -1258 -7569 7248 -6105 5603 3981 2759 402 -697...
output:
225908
result:
ok single line: '225908'
Test #32:
score: 0
Accepted
time: 255ms
memory: 25464kb
input:
965 -499999940 -499999730 500000289 313 -3035 2731 499999805 -39 -500000000 500000358 500000258 118 499999559 -470 -76 -343 -500000287 500000365 -500000057 -499999958 -1769 1968 -499999875 499999605 3522 276 -1912 -3061 499999804 499 -500000271 -499999547 499999938 231 -2963 -2829 -499999569 5000003...
output:
203957
result:
ok single line: '203957'
Test #33:
score: 0
Accepted
time: 228ms
memory: 24628kb
input:
939 1482 1260 -500000434 499999806 -1149 1747 -1260 1764 -3404 3034 2618 2273 -553 -392 -90 -3078 2757 2379 -2220 1380 -499999836 499999642 -112 -998 644 1683 -499999699 499999913 499999670 500000167 -1971 1946 499999801 499999965 -3162 2736 2555 2230 -1087 539 -428 -725 -194 -2134 500000495 5000003...
output:
186708
result:
ok single line: '186708'
Test #34:
score: 0
Accepted
time: 247ms
memory: 25188kb
input:
955 -500000461 499999573 -500000200 500000494 499999939 500000463 -39524918 53025080 -99 -500000165 -500000200 500000091 -500000219 499999560 -499999918 499999537 410 -499999818 499999933 500000103 -782940 -97167732 -349 -500000158 7048224 -70490840 500000237 500000298 -121433800 71838974 -31 -50000...
output:
196114
result:
ok single line: '196114'
Test #35:
score: 0
Accepted
time: 252ms
memory: 25868kb
input:
968 -12670145 11374518 49588653 53257314 500000215 500000158 -8908087 -115578630 529677 -71499488 25624561 33337978 -76255449 92204400 499999734 499999840 -120030147 73937760 -500000414 499999624 -46637397 80896480 1095073 -34357320 -65295465 86876630 5074591 -102596268 -500000181 500000227 5792209 ...
output:
197768
result:
ok single line: '197768'
Test #36:
score: 0
Accepted
time: 262ms
memory: 26176kb
input:
977 83649189 40238137 92840791 48787531 155777175 13666781 131614099 -133559403 34560415 9091049 78190421 -55691683 500000145 499999824 499999690 -500000016 213134377 -226679563 8550991 -782899 -17378157 -7445807 149194543 -220979967 -231554525 9693119 126556711 98799479 -43668547 -14871337 -1559746...
output:
209251
result:
ok single line: '209251'
Test #37:
score: 0
Accepted
time: 249ms
memory: 25504kb
input:
962 -121030326 164192864 -195872956 182875129 140748524 -7241051 93616974 -5934996 201849184 -17632706 -500000310 500000030 221383224 -23651916 -203538931 189178264 500000197 53 -159360201 137617484 -178496746 165839629 -128582731 -313281 -499999956 500000192 499999784 110 -155271681 -137562626 -225...
output:
201519
result:
ok single line: '201519'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
4 0 1 1000000000 -1000000000 1 0 -1000000000 1000000000
output:
1
result:
ok single line: '1'
Test #39:
score: 0
Accepted
time: 226ms
memory: 24036kb
input:
928 170269973 -272038995 136492629 156219873 -47171679 -19145691 305743329 -317318107 141297165 165392169 99585057 -96527839 175220101 -36616731 156001957 -202737203 -272548095 -3130571 -11356047 -27298843 148722357 -180534423 104753573 108101717 297954157 -313023143 -14559071 -26352495 171725893 27...
output:
194714
result:
ok single line: '194714'
Test #40:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
6 0 0 -2 -99 -100 -100 -56 -55 -100 0 0 -100
output:
4
result:
ok single line: '4'
Test #41:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
6 -100 0 2021 2023 -2022 0 2019 -2021 99 101 99 -99
output:
1
result:
ok single line: '1'
Test #42:
score: 0
Accepted
time: 284ms
memory: 26972kb
input:
1000 -742147404 -283695660 -466639637 288446353 -83175126 146887879 969866611 -661949195 334569680 -966256649 55429457 51833284 -748377689 -415645264 34617026 853758184 -118667814 392964857 -929275128 -49421111 -19389314 614045676 -12269024 -39409010 901905217 -20981356 -81827036 -37385291 584210585...
output:
248992
result:
ok single line: '248992'
Test #43:
score: 0
Accepted
time: 157ms
memory: 19340kb
input:
774 -26422194 60886359 452287984 458733035 -6427410 -261937333 -265362764 587539606 671091287 -196803029 -406574773 -714708522 -370481503 -448336592 -633039773 764194633 562006117 355891150 -247317078 58953343 -342293532 -775239898 -688832160 -409147438 515472348 7385278 727654419 164961897 -8472053...
output:
148996
result:
ok single line: '148996'
Test #44:
score: 0
Accepted
time: 290ms
memory: 26780kb
input:
1000 -72285764 -581996567 -822447341 -398199852 -331102816 -910495620 -235765662 -51188181 -654757419 -15344880 -73989701 -106766327 -561359665 -236163519 -462377613 -952098496 -888525203 -359979765 -626973746 -922268418 -766692243 -653113679 -946363316 -357536066 -483253705 -857013734 -364199596 -5...
output:
248909
result:
ok single line: '248909'