QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#511755 | #8321. 季风 | TheRaptor | 90 | 106ms | 3860kb | C++17 | 2.0kb | 2024-08-10 10:38:27 | 2024-08-10 10:38:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
long long n,k,x,y,lo,hi,mid1,mid2,j;
__int128 a1,a2,v1,v2;
pair<long long,long long> arr[100005];
pair<long long,long long> net;
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
long long in;
long long ik,ix,iy;
cin >> in >> ik >> ix >> iy;
n=in,k=ik,x=ix,y=iy;
net={0,0};
for(int i=0; i<n; i++){
long long a,b;
cin >> a >> b;
arr[i].first=a; arr[i].second=b;
net.first+=arr[i].first;
net.second+=arr[i].second;
if(i) arr[i].first+=arr[i-1].first,arr[i].second+=arr[i-1].second;
}
if(x==0&&y==0){
cout << 0 << '\n';
continue;
}
long long iters[n];
memset(iters,-1,sizeof(iters));
for(int i=0; i<n; i++){
lo=0,hi=1e13;
while(hi-lo>2){
mid1=(lo*2ll+hi)/3ll;
mid2=(lo+hi*2ll)/3ll;
//cout << lo << ' ' << mid1 << ' ' << mid2 << ' ' << hi << '\n';
a1=x-(arr[i].first+(__int128)mid1*net.first),a2=y-(arr[i].second+(__int128)mid1*net.second);
if(a1<0) a1=-a1;
if(a2<0) a2=-a2;
v1=a1+a2-(i+1+(__int128)mid1*n)*k;
if(v1<=0){
hi=mid2;
continue;
}
a1=x-(arr[i].first+(__int128)mid2*net.first),a2=y-(arr[i].second+(__int128)mid2*net.second);
if(a1<0) a1=-a1;
if(a2<0) a2=-a2;
v2=a1+a2-(i+1+(__int128)mid2*n)*k;
if(v1<=0&&v2<=0) hi=mid2;
else if(v2>v1) hi=mid2;
else lo=mid1;
}
for(j=lo; j<=hi; j++){
a1=x-(arr[i].first+(__int128)j*net.first),a2=y-(arr[i].second+(__int128)j*net.second);
if(a1<0) a1=-a1;
if(a2<0) a2=-a2;
v1=a1+a2-(i+1+(__int128)j*n)*k;
if(v1<=0){
iters[i]=j;
break;
}
}
}
long long ans=1e18+5;
for(int i=0; i<n; i++){
//cout << iters[i] << ' ';
if(iters[i]!=-1) if(ans>iters[i]*n+i+1) ans=iters[i]*n+i+1;
}
if(ans>=(long long)1e18) cout << -1 << '\n';
else cout << ans << '\n';
}
}
詳細信息
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 3560kb
input:
300 1 32286 -66773299 39159226 2655 14568 1 9900506 22484330 26135209 -33930 -9866575 1 669210 -40846340 -58419438 -529764 8866 1 74 -74443560 -78969527 -14 -37 1 473964 -91643319 -21680398 106817 243107 1 8543824 31629618 -37823687 1090776 4153469 1 16 -8109 -8410 -16 0 1 794120 -60084819 -21436725...
output:
2397 48619539 135 1227305 914 13 -1 96 28 1092928 42688085 -1 40791405 1 54608218 168 3415 13660 -1 53118060 19256086 17049 162101612 168026244 -1 147383845 16356862 158113199 367 19 -1 212 7 6677 13 56318408 0 -1 5 -1 107373214 7 176722 26 90888792 562 -1 3189099 655611 159239 1015616 60054 16874 8...
result:
ok 300 numbers
Test #2:
score: 10
Accepted
time: 1ms
memory: 3644kb
input:
300 1 0 14658671 -17744707 -19 23 1 0 -43777875 2899010 1318511 -388002 1 0 -39267054 -13736220 -19633527 -6868110 1 0 51104805 90132261 1473 -925 1 0 -30105792 20070528 48 -32 1 0 -73521410 -3106528 7939241 3095051 1 0 1934605 -4643052 -5 12 1 0 10981610 -30724102 5490805 -15362051 1 0 -8877616 887...
output:
-1 -1 2 -1 -1 -1 -1 2 -1 -1 -1 1 1 -1 1 -1 -1 504450 -1 383792 -1 2 -1 -1 -1 2 -1 1 551573 1 -1 1 -1 -1 -1 -1 290386 -1 -1 -1 -1 -1 1 -1 -1 122858 -1 1 -1 -1 1 -1 2 -1 1 1 -1 -1 558002 0 -1 1 -1 -1 -1 -1 -1 1 1 2 -1 2 -1 -1 -1 -1 2 -1 453621 2 2 -1 -1 127092 -1 -1 2 2 -1 198741 -1 -1 2 1 -1 -1 -1 2 ...
result:
ok 300 numbers
Test #3:
score: 10
Accepted
time: 1ms
memory: 3632kb
input:
300 1 342739 0 84733186 0 0 1 1 -71236915 69825956 0 0 1 1 96944547 67493888 0 0 1 101010 10720443 27403069 0 0 1 0 -47050862 27820930 0 0 1 299851 -32954036 24041633 0 0 1 22039 16175909 -32970576 0 0 1 54 -92637795 -64306686 0 0 1 65 -42213950 -76922091 0 0 1 48846 0 20220443 0 0 1 4641 0 0 0 0 1 ...
output:
248 141062871 164438435 378 -1 191 2230 2906380 1832863 414 0 -1 21701397 25503860 3505 1570 43 56654328 1699 52308137 7951717 89151814 4773275 -1 243123 13 -1 69375 216700 58 114 457 35773753 1749173 -1 5825141 -1 28683350 117459 201508 64575587 323716 16610172 3959091 0 570 34498369 21969418 19289...
result:
ok 300 numbers
Test #4:
score: 10
Accepted
time: 1ms
memory: 3712kb
input:
300 1 491 19238896 24359756 2923207 -8745945 1 28452 -33430186 -3983771 18956 9495 1 1198593 -53848855 -4734461 93056 1105536 1 676 2931070 -9330910 52 -67 1 10 55228984 8970 -5 0 1 765812 2781176 64328480 -208 -223 1 0 -18744011 -35145767 -24 -45 1 251234 23812841 -10427626 -6279 -6797 1 996 -44886...
output:
-1 37413957 58583316 15424 11047591 88 -1 137 103025 69345443 2 -1 -1 4395 -1 -1 -1 -1 537956 149379205 -1 -1 25894733 440611 8990 3 -1 -1 -1 52207537 60700 420024 19149414 1 10 -1 52 -1 15156244 -1 320 -1 17647291 16255 0 3325 34073206 50713 -1 495 1 6 599074 3 -1 54344608 -1 30919544 -1 -1 11 -1 2...
result:
ok 300 numbers
Test #5:
score: 10
Accepted
time: 4ms
memory: 3656kb
input:
686 4 123 61343816 -81149292 43 62 -26 -93 68 31 -103 0 2 41 5546 -92990467 -40 0 -25 0 6 835927 -25588646 -89091109 644485 191442 677934 157993 398739 437187 762871 73056 776002 59925 553067 282859 2 542128 21060442 -2011 -23932 0 -25454 0 3 1 44172958 49903094 -1 0 -1 0 0 0 1 4491 18010618 -313236...
output:
1202474 10940708 344039265 41 282228156 5805 501513 282 12686985 113472955 115108557 12 17505368 209920957 7 14432 81544610 14 2 85768513 0 1396 4156 187149083 19428 1 6561618 1808 27 39193857 4 276 32462 251870741 1 862 66898 128 14266788 469 2 134 15193816 3881718 172988585 3 2159 129025368 137673...
result:
ok 686 numbers
Test #6:
score: 10
Accepted
time: 6ms
memory: 3624kb
input:
684 7 0 -4659965 65259689 -4659965 -99999977 0 0 0 0 0 0 4659965 99999979 0 0 0 0 1 0 18167938 67528693 18167938 67528693 7 0 -98200220 34188772 -98200220 34188772 -68294507 12668575 -28670964 -87244428 -98971553 90836074 74941179 92402443 10378449 63151034 -11200823 12733866 3 0 -80260647 -12683275...
output:
578408832 1 1 -1 1 -1 -1 -1 1 6 2128095 -1 1 1324125443 306230 -1 6 -1 5 -1 2804421 2 -1 -1 230055022 1 -1 -1 -1 1 -1 368563393 3 -1 1354128 1 732875 -1 -1 -1 1560100 -1 -1 -1 -1 -1 355038951 1779555255578 -1 -1 -1 103976047 -1 -1 12496201 -1 10 158771807 5 -1 6 -1 2 212817988 1346785 -1 -1 1 145106...
result:
ok 684 numbers
Test #7:
score: 10
Accepted
time: 4ms
memory: 3564kb
input:
667 6 22320 -47869922 -94574425 -35667 -912623 452472 -751486 42399 685787 -602148 221313 389986 58340 504503 896866 3 568 40479510 -78492210 -218 -454519 249230 -310323 -501776 -456425 4 96 -34634275 -41782650 450066 2475397 -1983097 1089604 -2006742 1395784 394497 -1700181 2 586988 87270830 324220...
output:
-1 -1 -1 239385813 1938779 6492421 -1 15294 291525169 10818277 49646093 202281 31128 1 -1 6053 -1 48575 -1 -1 12309331 -1 -1 4 2498 -1 464 -1 99423973 -1 -1 2337 -1 303530 205751489 37597620 101 4331250 11453 -1 -1 617 652 -1 171 0 -1 -1 245 2144 4142528904 0 251723 -1 22466088 127693 103361571 4289...
result:
ok 667 numbers
Test #8:
score: 10
Accepted
time: 58ms
memory: 3848kb
input:
5026 7 1536 96224177 3215062 -431 -1063 -930 207 392 -343 -151 -351 190 240 708 -222 1084 -118 2 2007 4875 8961 0 -1006 1282 725 3 74 6255 36271857 2 0 2 0 39 0 4 299644 51336139 54387095 -223835 -75808 -50044 -249599 -36180 -263463 -257793 -41851 5 87337 46515166 83800720 -45698 -41639 -38633 -4870...
output:
69860 6 607804 140964311 651579427 295842 781696 1860552 820363 97878227 875 10669352 113239787 41144 104 929275 4899340 228104447 79 29357925 433986768 1369 12933859 6292206 1 58638783 19199022 -1 6 136901931 9566917 3515420 64052003 9896 93383864 5847 1881477 19872258 2 3549 49 22157 199 204 26644...
result:
ok 5026 numbers
Test #9:
score: 10
Accepted
time: 106ms
memory: 3860kb
input:
5021 4 0 -12747354 40715188 8473127 -24739598 -4402460 47229129 -63791499 59230380 38500351 -16265125 1 0 13024199 16963243 -2413 -27747 4 0 85556443 48034225 66661568 99999993 18894875 99999991 -19570239 -99999994 -65986204 -99999993 1 0 -64373357 -92003118 3 0 3 0 -57596351 -55622531 -97485 -45744...
output:
5 -1 202621014 -1 -1 -1 -1 -1 -1 -1 903348426 1017644 3 -1 -1 -1 -1 3 9 -1 -1 -1 -1 131427163 3773967 -1 63606 4918116 341309620 -1 269616 307975448 425315146 2 1 -1 5270454 -1 411686418 -1 37840064 0 -1 -1 -1 1181692 10 4 855299912 -1 -1 -1 1392987 -1 -1 -1 -1 371539975 631281061 -1 6 -1 1 2331264 ...
result:
ok 5021 numbers
Test #10:
score: 0
Time Limit Exceeded
input:
50122 5 25999922 8405 55768791 -1508111 -18663017 17765724 618297 -4046292 -11237396 -7742552 -12278384 6308331 3503946 2 204 -78318892 -78082051 582 -858 -620 -1217 2 33912059 -80164190 40071329 -4 -3 4 -3 1 281690 -6253970 14352972 -4363 328 5 11522477 13398456 -59393899 -173 -366 -221 -193 -484 1...
output:
4 -1 4 72 7 29646446 20208 9128183 6 165801675 13185324 11 5073737 -1 145 -1 -1 3534192 -1 156149623 65428515 614 -1 7 -1 6 808046 113618577 23028975 -1 20 10 1643705 51 -1 1195 2678557 -1 17991403 -1 391633112 -1 14045 6680 1790748528 158710 14 -1 74758279 130579777 14 -1 233685110 6 270663276 30 1...