QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#548953 | #1914. Falling Portals | isirazeev | 7.142857 | 54ms | 9684kb | C++20 | 2.9kb | 2024-09-05 22:21:53 | 2024-09-05 22:21:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = (int) 1e5 * 2 + 10;
struct line {
int k, b;
line() : k(0), b(0) {};
line(int _k, int _b) : k(_k), b(_b) {};
};
long double intersectX(line a, line b) {
return (long double) (b.b - a.b) / (long double) (a.k - b.k);
}
pair<int, int> intersect(line a, line b) {
int d = abs(__gcd((b.b - a.b), (a.k - b.k))), minus = (b.b < a.b ? -1 : 1);
return {(b.b - a.b) / d * minus, (a.k - b.k) / d * minus};
}
int a[N], q[N], n, sz = 0;
pair<int, int> ans[N];
vector<line> st;
int sign(int x) {
return (x >= 0 ? 1 : -1);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> q[i], q[i]--;
vector<int> ord;
for (int i = 0; i < n; i++) ord.emplace_back(i);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return a[i] < a[j];
});
reverse(ord.begin(), ord.end());
for (int i: ord) {
line k = line(-(i + 1), a[i]);
while (sz >= 1) {
if (k.k < st[sz - 1].k || (sz >= 2 && intersectX(st[sz - 1], k) >=
intersectX(st[sz - 1], st[sz - 2])))
st.pop_back(), sz--;
else break;
}
st.emplace_back(k), sz++;
if (a[q[i]] < a[i]) {
line t = line(-(q[i] + 1), a[q[i]]);
int l = 0, r = sz;
while (r - l > 1) {
int mid = (l + r) / 2;
if (intersectX(st[mid], k) >= (mid > 0 ? intersectX(st[mid], st[mid - 1]) : -1e18))
l = mid;
else
r = mid;
}
ans[i] = intersect(st[l], t);
}
}
st.clear(), sz = 0;
reverse(ord.begin(), ord.end());
for (int i: ord) {
line k = line(-(i + 1), a[i]);
while (sz >= 1) {
if (k.k > st[sz - 1].k || (sz >= 2 && intersectX(st[sz - 1], k) <=
intersectX(st[sz - 1], st[sz - 2])))
st.pop_back(), sz--;
else break;
}
st.emplace_back(k), sz++;
if (a[q[i]] > a[i]) {
line t = line(-(q[i] + 1), a[q[i]]);
int l = 0, r = sz;
while (r - l > 1) {
int mid = (l + r) / 2;
if (intersectX(st[mid], k) <= (mid > 0 ? intersectX(st[mid], st[mid - 1]) : 1e18))
l = mid;
else
r = mid;
}
ans[i] = intersect(st[l], t);
}
}
for (int i = 0; i < n; i++) {
if (ans[i].first == (int) 1e18 || sign(ans[i].first) != sign(ans[i].second)) cout << "-1\n";
else cout << ans[i].first << "/" << ans[i].second << "\n";
}
return 0;
}
详细
Pretests
Final Tests
Test #1:
score: 7.14286
Accepted
time: 1ms
memory: 5596kb
input:
4 3 5 10 2 3 3 2 1
output:
7/2 7/2 5/1 -1
result:
ok 4 lines
Test #2:
score: 0
Wrong Answer
time: 50ms
memory: 9516kb
input:
100000 472909419 819415545 354941190 517113826 307239833 831177800 578834772 704837117 326642977 846249751 997452224 322958397 143787473 278464288 864820832 175161120 545824609 549197171 224617065 387719870 938593011 671365566 982006335 210657906 552581470 851423470 973444746 978545568 66820178 6528...
output:
241244953/31221 41149778/48281 452538539/85232 209334325/32597 148851281/50439 131218209/42116 62687114/6449 282893997/35531 20263629/3139 88773191/30046 203889403/2459 272943018/33431 493001077/60184 215153471/10925 44364708/6077 302226432/68245 110511785/73608 75011328/3757 221790099/3970 61878419...
result:
wrong answer 1st lines differ - expected: '118375763/30533', found: '241244953/31221'
Test #3:
score: 0
Wrong Answer
time: 51ms
memory: 9684kb
input:
100000 315623747 979206700 183094144 181505867 2572616 772718102 942741911 19472958 458398376 484546774 348949045 306690702 414701395 131437507 43708479 224826052 238532133 327518511 70279102 323433367 124141008 73101443 605805888 102782315 282343812 345273900 201043659 430908518 243739589 724275027...
output:
130531/66524 292813/7595 525151083/24941 319327425/95353 974493012/7847 710573306/77679 765015070/53031 394552387/23254 572160749/3220 200735349/46396 501841671/90841 556056596/61005 179273411/30494 797632461/39496 563884742/91191 356044935/41912 619342247/58682 44715329/86990 115649841/15859 144465...
result:
wrong answer 3rd lines differ - expected: '127274533/24541', found: '525151083/24941'
Test #4:
score: 0
Wrong Answer
time: 49ms
memory: 9544kb
input:
100000 1 4273 15397 29998 27927 48335 59992 44642 37593 89985 41136 43307 119975 48665 62351 149962 8744 116987 179946 98859 144057 209927 19516 41099 239906 183405 142896 269883 7437 83101 299858 174434 127933 329832 91448 39029 359803 174356 124036 389771 136441 166104 419738 196420 51865 449702 2...
output:
214487230/35559 88821503/17702 96116964/31589 33498601/86298 54677767/38514 276085/89744 70346167/10315 3282261/4553 68350042/8415 147158147/18561 21536511/19411 63364259/76039 45605789/97961 6387316/95781 92020293/27694 417768/89743 47243948/5883 132305758/65579 98284659/59579 22738769/87450 433106...
result:
wrong answer 3rd lines differ - expected: '32033856/10529', found: '96116964/31589'
Test #5:
score: 0
Wrong Answer
time: 49ms
memory: 9560kb
input:
100000 1 933326351 11431 29998 989129972 37227 59992 989874362 62527 89984 979798680 75881 119974 982112916 19608 149961 995611915 151806 179946 913593466 132088 209929 930585647 149041 239909 930246483 218498 269887 972955258 54548 299863 927767028 295901 329836 953302565 223592 359806 995522236 31...
output:
221281385/50982 829322777/84166 52985461/6135 943970452/35443 987715279/45986 959092712/59617 147960739/33437 183593591/13318 912916297/6703 1465993/13499 925334617/17356 45774484/6773 88791275/12168 986496071/99268 916995273/8386 216676519/36327 907112071/59273 6593999/86177 224643841/42798 2915296...
result:
wrong answer 2nd lines differ - expected: '401837273/42017', found: '829322777/84166'
Test #6:
score: 0
Wrong Answer
time: 48ms
memory: 9548kb
input:
100000 1 944663363 19033 29999 978821096 9085 59995 944910920 6257 89989 935899956 82545 119982 940520499 117973 149972 912135517 105359 179960 992861910 149037 209947 995445085 200979 239932 965159106 3211 269915 909296230 233961 299895 975484316 298245 329873 977094068 214362 359849 995636217 2225...
output:
2982983/44613 757069534/67939 54143670/22831 3857750/3981 15707617/178 264626224/32479 13213694/88485 812008619/29488 4457716/1137 164134519/68166 762978999/40438 37311556/7075 62587210/83049 379078350/34157 603628/61 202644680/30819 171427262/17537 100865737/29580 202766575/30858 75690997/2894 3910...
result:
wrong answer 2nd lines differ - expected: '105551441/9703', found: '757069534/67939'
Test #7:
score: 0
Wrong Answer
time: 1ms
memory: 5800kb
input:
100 534473706 617535198 746655229 582822181 350704338 460330801 735571468 88013273 362424504 855094440 710187915 697682713 997401051 460972806 717634399 444280514 755460273 944591484 265200138 839544060 662809699 661469793 497227720 278087261 937000185 722532327 468846527 92827045 15385128 139854649...
output:
460073995/39 499461693/79 70579417/54 301848200/89 354956825/18 586295847/20 353515088/23 722738799/65 142459051/37 101926695/19 460073995/39 101852132/77 47435537/1 -1 630417805/24 442572991/33 750699957/37 353261461/15 497874367/28 90739905/41 173559563/28 295815304/71 54515017/2 379371014/71 2186...
result:
wrong answer 4th lines differ - expected: '253499725/86', found: '301848200/89'
Test #8:
score: 0
Wrong Answer
time: 1ms
memory: 7704kb
input:
100 832359132 241086117 70268513 75641100 493265869 8969911 580115154 253097306 322151607 572536179 103433364 769475382 58915476 7943159 674934181 286336577 158800591 167266000 146088101 655190514 41590604 326590745 562776717 281254161 127537826 133491925 80685740 116325615 999795567 247078385 96567...
output:
-1 252179752/3 37201903/6 851541346/89 607501188/53 312966442/25 128273573/32 317502509/94 74819236/17 78959213/10 89021968/17 369132746/25 274426577/13 811758438/43 501895629/13 3353383/1 671014573/36 444919577/16 444919577/16 169084232/15 -1 64200075/14 165725031/4 442582477/42 772096419/52 -1 215...
result:
wrong answer 5th lines differ - expected: '534493001/48', found: '607501188/53'
Test #9:
score: 0
Wrong Answer
time: 2ms
memory: 7948kb
input:
2000 21505957 142018840 50835846 230286771 619214141 711966088 451418032 83312406 997278214 235672441 776998092 992475976 912444334 252212792 547270894 875994775 420249958 660039013 284835603 996966995 545404037 762620339 218177198 216536966 712712166 284586306 598975962 889965588 251816698 28540064...
output:
621739397/749 33520808/215 602667263/810 707562741/409 704650991/252 587327957/1085 570972173/1671 182030611/1121 -1 435186842/1103 446600371/912 342292000/1507 717288703/862 232372902/589 276874481/787 23472297/29 230823844/1717 856492709/1296 644019603/1964 -1 22858965/59 16684299/13 838178813/543...
result:
wrong answer 2nd lines differ - expected: '68924125/851', found: '33520808/215'
Test #10:
score: 0
Wrong Answer
time: 2ms
memory: 7756kb
input:
2000 797776435 328363264 380792931 830287509 570335429 882870824 429432401 710728673 945865610 940849228 403089500 796543599 901854446 712568094 68385691 346788092 179631402 72575296 680321593 139773675 517849401 190654156 839257552 981435241 992409916 887842045 919377993 677204575 940817503 5589288...
output:
122356085/1554 38621117/206 133392018/569 434894295/118 75415673/24 95982178/1303 596084162/1725 360180127/1036 397141904/631 157916978/581 66250822/207 555552027/1399 329391712/1187 175253001/1957 382634689/502 635406610/291 138740381/173 793983196/1477 24604043/373 104206472/217 99876178/265 85467...
result:
wrong answer 1st lines differ - expected: '103496945/1514', found: '122356085/1554'
Test #11:
score: 0
Wrong Answer
time: 42ms
memory: 9524kb
input:
100000 40496370 324535254 49378557 776806467 392153838 609799230 999070315 9268041 50237542 87633903 878656049 864388090 896320175 129811364 229732659 323726790 766611509 83562791 105404287 304944654 412773020 198917959 443657299 415124223 512809649 256079123 986186956 2116823 811457832 528369347 63...
output:
909844125/74797 430373516/14009 498253787/87383 163202103/38510 168816906/91357 606545024/91907 628939831/44474 176270891/15211 51693914/669 527910257/30794 605230669/33802 173418011/7099 242800380/2891 460509391/88506 260581953/28021 346856627/38410 131183323/31917 131610719/28054 251355311/76073 2...
result:
wrong answer 2nd lines differ - expected: '224068850/13921', found: '430373516/14009'
Test #12:
score: 0
Wrong Answer
time: 54ms
memory: 9544kb
input:
100000 747693760 346580867 964846225 969980340 332880584 194631534 209614296 522099709 464443293 921495511 83514635 841823909 900939960 262364081 256636328 411285480 427902137 406071146 24620069 112056879 943629859 862303870 308874724 251885142 471236107 744614688 681975403 212603157 214491071 32304...
output:
11915208/665 118249853/13726 943301712/55825 205382259/47299 8084821/2769 334404865/19093 133890504/18665 112710324/15191 433490952/42503 243891325/11662 794770271/18621 195687091/69616 145387495/72399 448431291/13709 141049841/41358 432007538/37793 70596851/6324 40884160/983 671242823/75454 7890235...
result:
wrong answer 1st lines differ - expected: '78195569/6188', found: '11915208/665'
Test #13:
score: 0
Wrong Answer
time: 50ms
memory: 9676kb
input:
100000 97813451 955958588 478382047 254807140 430405236 587356632 581166185 416641725 298677059 255167178 707387178 995828332 1210912 419588635 497113506 472224137 683979366 992616764 280702107 282745359 832716627 830311108 1931725 972918653 684698510 654423087 966059769 427612303 261873029 35728741...
output:
127919159/46770 280179943/35972 276507634/23291 467503688/72483 569214241/67999 829231721/47325 859076459/9363 409450599/10844 208778793/36916 438642859/29786 812412562/63679 964201005/20009 308404938/34405 345136094/70027 807250128/41977 819491159/8643 740975556/33319 38437703/72885 68125552/6621 7...
result:
wrong answer 2nd lines differ - expected: '266183846/35305', found: '280179943/35972'
Test #14:
score: 0
Wrong Answer
time: 54ms
memory: 9560kb
input:
100000 822999751 128955399 431407947 917749297 190297412 252492617 150325783 759881331 829939635 283074122 899601042 159665057 607610844 489768568 320041755 787661887 373639719 710748050 188262807 366602165 732969261 932719233 208477147 358075812 125541209 536067868 278333698 201086482 537247556 180...
output:
400217721/46846 51144568/51191 651498883/85639 178650081/31622 69049393/12697 453362396/60239 208731638/20087 217287819/26732 388325915/33272 158878077/8417 87245940/85093 867713789/68509 658159581/13907 761488589/26185 114253785/13088 155306252/68279 670755269/37911 684528407/28610 94981649/12609 6...
result:
wrong answer 1st lines differ - expected: '80903637/10393', found: '400217721/46846'