QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#525775 | #7122. Overtaking | kimmoqt | 0 | 3ms | 6252kb | C++20 | 3.1kb | 2024-08-20 22:15:08 | 2024-08-20 22:15:09 |
answer
#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=1005;
ll E[MX][MX], F[MX][MX];
vector<array<ll,3>> G[MX];
vector<ll> T;
vector<pair<ll,ll>> v;
vector<int> W, S;
int L,N,X,M;
ll mx;
pair<ll,ll> work(ll Y, int id) {
ll cur=Y;
ll res=-1;
for(int j=1;j<M;j++) {
array<ll,3> t={cur,0,0};
auto nxt=lower_bound(G[j].begin(),G[j].end(),t);
if(nxt!=G[j].begin()) {
nxt--;
cur+=1LL*(S[j]-S[j-1])*X;
if(cur<(*nxt)[1]) {
cur=(*nxt)[1];
if(res==-1) res=(*nxt)[2];
}
} else {
cur+=1LL*(S[j]-S[j-1])*X;
}
}
if(res==-1) {
return {-1,-1};
}
return {res,cur};
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
W.push_back(X);
::T=T, ::W=W, ::S=S;
::L=L, ::N=N, ::X=X, ::M=M;
for(int i=0;i<N;i++) {
F[0][i]=T[i];
}
for(int j=1;j<M;j++) {
for(int i=0;i<N;i++) {
E[j][i]=F[j-1][i]+1LL*W[i]*(S[j]-S[j-1]);
}
vector<int> ord;
for(int i=0;i<N;i++) ord.push_back(i);
sort(ord.begin(),ord.end(),[&](int x, int y){
return F[j-1][x]<F[j-1][y];
});
ll mx=0;
for(int p=0;p<ord.size();p++) {
int q=p;
while(q+1<ord.size() && F[j-1][ord[q+1]]==F[j-1][ord[q]]) q++;
for(int k=p;k<=q;k++) {
F[j][ord[k]]=max(mx,E[j][ord[k]]);
}
for(int k=p;k<=q;k++) {
mx=max(mx,E[j][ord[k]]);
}
G[j].push_back({F[j-1][ord[p]],mx,ord[p]});
p=q;
}
}
mx=*max_element(F[M-1],F[M-1]+N);
ll prv=0;
while(v.size()<=2*N) {
ll l=prv,r=mx,res=-1;
while(l<=r) {
ll mid=(l+r)/2;
if(work(mid,v.size()+1).first==work(prv,v.size()+1).first) {
l=mid+1,res=mid;
} else {
r=mid-1;
}
}
v.push_back(work(prv,v.size()+1));
v.back().first=prv;
if(res==-1) break;
prv=res+1;
}
return;
}
long long arrival_time(long long Y) {
auto it=upper_bound(v.begin(),v.end(),make_pair(Y,0ll));
if(it==v.end()) return 1LL*X*L+Y;
it--;
if((*it).second==-1) {
return 1LL*X*L+Y;
} else {
return (*it).second;
}
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 6244kb
input:
XwWPuInrOjpekAwGKojzwKw3yVDtdkGS 2500 1 78 100 1000 100000 80 0 38 51 89 92 105 117 119 122 126 142 179 259 355 385 410 419 443 483 496 551 671 691 698 709 762 778 818 860 888 897 909 930 938 946 951 955 995 1045 1091 1164 1187 1215 1243 1264 1301 1363 1409 1416 1448 1504 1518 1535 1555 1562 1597 16...
output:
mGlgT4yvr1qPbquFwkxRVh9hMn0Mrxoz OK 299632 298224 299162 297964 295102 298066 297104 298618 298242 296390 296472 298054 295828 296910 296888 297368 298654 295180 295604 299062 296354 298684 298110 297916 299516 298706 295962 299062 296784 298984 299736 296414 298580 296874 295078 299850 295590 29576...
result:
wrong answer 3rd lines differ - on the 1st token, expected: '299664', found: '299632'
Subtask #2:
score: 0
Wrong Answer
Test #12:
score: 10
Accepted
time: 1ms
memory: 6160kb
input:
XwWPuInrOjpekAwGKojzwKw3yVDtdkGS 2000000 100 100 2 1000 566035866 424023571 564031634 266012245 266012901 566037245 106005324 106003684 266012594 424028440 424019007 106005224 564034079 424024371 424024546 566039191 424016814 424029581 82000890 754044052 566036512 424018510 424017279 424019925 42401...
output:
mGlgT4yvr1qPbquFwkxRVh9hMn0Mrxoz OK 768035150 768029581 1144044184 308008207 768029581 768029581 956039191 768029581 956041170 768029581 768029581 308008207 956039191 308008207 768029581 768029891 1144044184 418008550 768029581 468009953 308008207 1144044184 768035150 768029581 468010817 768029581 6...
result:
ok
Test #13:
score: 10
Accepted
time: 1ms
memory: 5912kb
input:
XwWPuInrOjpekAwGKojzwKw3yVDtdkGS 10000000 400 1011 2 1000 173387969125 200337983261 77920310897 77652037350 182097978669 118267907350 174157972712 57062023028 118267909308 107247901578 174157973485 146027951049 53742020545 118267912197 174167974422 207927989121 137207921414 143227933063 77992040344 ...
output:
mGlgT4yvr1qPbquFwkxRVh9hMn0Mrxoz OK 128387906425 192867977136 218447987834 162297954325 192867978986 34992000977 147437922857 192867979350 67182020640 56912011273 63862013824 162297954325 43302006404 92682052132 120767905711 218447987834 98882054684 138667917161 63862014242 117367898279 210667984418...
result:
ok
Test #14:
score: 10
Accepted
time: 2ms
memory: 5940kb
input:
XwWPuInrOjpekAwGKojzwKw3yVDtdkGS 10000 800 1522451 2 1000 102691961165 356949771920 280550316262 154390571762 439415828789 473733275923 465056851706 434971147676 473185083883 407141567243 446269133331 245826204010 132720147100 266857422544 300276587668 200566213815 304647607947 8994460481 3661139508...
output:
mGlgT4yvr1qPbquFwkxRVh9hMn0Mrxoz OK 480548847785 422389308676 261050720686 480548847785 24218980889 488958822294 290598660610 61394536039 454767827473 117916481772 160323101016 454767828952 109098515326 222192213960 467092876761 319997647668 369154287532 146931915291 501350951422 319997648312 242189...
result:
ok
Test #15:
score: 10
Accepted
time: 0ms
memory: 6252kb
input:
XwWPuInrOjpekAwGKojzwKw3yVDtdkGS 500000 1000 10000 2 1000 148512009450 164605927216 127484617319 27096740437 161301908126 227401559568 220855479544 152976736303 161069395645 159703894172 122292102200 189557102648 122405102528 39895753566 164605425801 106641054484 84900003806 152618881097 73504974935...
output:
mGlgT4yvr1qPbquFwkxRVh9hMn0Mrxoz OK 237134063601 77319966760 172553429697 60674183017 13155506385 85565990030 188380679354 132653620072 213967471779 69226440539 137641624766 166302397011 221523969131 80847981443 46376261447 37662245837 106741029379 130318611384 221523968061 93106503930 230318554599 ...
result:
ok
Test #16:
score: 10
Accepted
time: 3ms
memory: 5952kb
input:
XwWPuInrOjpekAwGKojzwKw3yVDtdkGS 500000 1000 10000 2 1000 36612285378 23369050451 152360966961 15872520226 182265836399 188728204731 213864007043 57066096669 80835239061 207526883647 43857790862 65146624890 89690753835 154413657390 20424038673 49803808788 126917115886 52711828720 118899204834 158725...
output:
mGlgT4yvr1qPbquFwkxRVh9hMn0Mrxoz OK 66580596995 198079362901 188002837585 194288360880 167111986766 73714107129 222229390881 108513769364 159439969371 25424526704 108513769364 25424526704 186703323340 108513769364 10576002438 140488624579 62066832985 36920571209 157371466325 100548265663 15330145069...
result:
ok
Test #17:
score: 10
Accepted
time: 2ms
memory: 5948kb
input:
XwWPuInrOjpekAwGKojzwKw3yVDtdkGS 500000 1000 10000 2 1000 4337004497 176521204259 51880125384 34694128785 180975708661 218870562416 97250810605 114586115166 24846112541 64565181841 125706138427 91643555516 73078310445 109339605796 117687618529 131699541732 8692016529 131699546538 62862679197 2229305...
output:
mGlgT4yvr1qPbquFwkxRVh9hMn0Mrxoz OK 57488656585 119672114103 159363389223 80550700997 193898735338 201967251391 209771544023 186206211435 61144668391 178885696551 195291238682 205565526206 108392081703 148442568746 201967251391 122724619987 186206206389 39694619414 108392081703 61144668391 396946227...
result:
ok
Test #18:
score: 10
Accepted
time: 0ms
memory: 5960kb
input:
XwWPuInrOjpekAwGKojzwKw3yVDtdkGS 1 1000 1 2 1000 655 476 606 503 746 669 142 668 383 118 398 946 53 282 396 67 739 265 86 976 405 472 467 350 740 326 426 516 763 329 894 645 782 34 390 44 614 387 539 527 88 437 978 873 155 46 190 725 613 957 111 342 605 483 295 333 766 981 177 716 371 424 572 338 70...
output:
mGlgT4yvr1qPbquFwkxRVh9hMn0Mrxoz OK 759 863 796 178 489 864 882 160 829 938 525 707 820 894 910 783 458 24 945 913 265 774 764 775 890 885 844 807 803 872 869 992 784 922 792 867 888 764 682 844 962 209 363 325 726 197 793 914 821 984 772 302 689 219 840 844 774 898 776 526 945 835 976 756 812 923 9...
result:
ok
Test #19:
score: 0
Wrong Answer
time: 1ms
memory: 6224kb
input:
XwWPuInrOjpekAwGKojzwKw3yVDtdkGS 100 1000 99 2 1000 64001 97600 61200 79400 29101 55800 93800 44301 22300 74300 22201 41601 76700 29901 20101 12000 71600 27101 82100 97101 27300 41000 95901 81701 78200 55100 69800 63901 20901 72301 19700 4600 39201 1401 83900 96601 82201 59401 86101 47101 36000 5260...
output:
mGlgT4yvr1qPbquFwkxRVh9hMn0Mrxoz OK 99220 91571 51808 31404 15025 102051 97697 98289 35020 66126 65088 35989 63029 97491 94795 26299 47747 30618 29561 59521 108491 104538 85816 23279 85574 24383 84643 93830 102730 100010 86069 98993 52849 91534 56483 65932 91989 18928 92730 85437 95023 92493 104194 ...
result:
wrong answer 3rd lines differ - on the 1st token, expected: '99300', found: '99220'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%