QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#727362 | #9574. Strips | ucup-team073# | AC ✓ | 51ms | 12628kb | C++23 | 1.8kb | 2024-11-09 12:57:45 | 2024-11-09 12:57:52 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define st first
#define nd second
#define pb push_back
#define mpr make_pair
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())f^=ch=='-';
for(;isdigit(ch);ch=getchar())x=x*10+(ch^48);
return f?x:-x;
}
const int N=2e5+5;
pii A[N];
int n,m,w,k,qh,qt,que[N],ans,b[N],tot;
vector<int> oper;
int f[N],g[N],nxt[N];
int work(int l,int r){
tot=0;
for(int i=1;i<=qt;++i)b[++tot]=que[i]-l;
r-=l;
for(int i=0;i<=tot;++i){
f[i]=g[i]=nxt[i]=-1;
}
f[0]=g[0]=0;
que[qh=qt=1]=0;
b[tot+1]=r;
for(int i=1;i<=tot;++i){
int l=0,r=i,FIND=-1;
while(l<=r){
int mid=(l+r)>>1;
if(b[i]-b[mid]>=k)FIND=mid,l=mid+1;
else r=mid-1;
}
if(FIND==-1){
if(b[i+1]>k){
f[i]=1;
g[i]=k;
que[++qt]=i;
nxt[i]=0;
}
}
else{
while(qh<=qt&&que[qh]<FIND)++qh;
if(qh<=qt){
if(g[que[qh]]+k<b[i+1]){
g[i]=max(b[i],g[que[qh]]+k);
f[i]=f[que[qh]]+1;
nxt[i]=que[qh];
que[++qt]=i;
}
}
else{
return -1;
}
}
}
if(f[tot]==-1)return -1;
int p=tot;
while(p){
oper.pb(g[p]-k+1+l);
p=nxt[p];
}
return f[tot];
}
void solve(){
ans=0;
oper.clear();
n=read(),m=read(),k=read(),w=read();
for(int i=1;i<=n;++i)A[i]=mpr(read(),1);
for(int i=1;i<=m;++i)A[i+n]=mpr(read(),0);
A[n+m+1]=mpr(w+1,0);
n=n+m+1;
sort(A+1,A+n+1);
int last=0;
qh=1,qt=0;
for(int i=1;i<=n;++i){
if(A[i].nd==0){
int t=work(last,A[i].st);
if(t==-1){puts("-1");return;}
ans+=t;
last=A[i].st;
qh=1,qt=0;
}
else{
que[++qt]=A[i].st;
}
}
printf("%lld\n",ans);
sort(oper.begin(),oper.end());
for(int x:oper)printf("%lld ",x);
puts("");
}
signed main(){
for(int cas=read();cas--;)solve();
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9912kb
input:
4 5 2 3 16 7 11 2 9 14 13 5 3 2 4 11 6 10 2 1 11 2 1 2 6 1 5 3 2 1 2 6 1 5 2
output:
4 1 6 9 14 -1 2 1 4 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: 0
Accepted
time: 11ms
memory: 9916kb
input:
11000 3 8 2 53 32 3 33 35 19 38 20 1 30 10 6 7 10 1 42 3 14 4 36 28 40 22 17 20 12 41 27 7 1 19 13 9 6 6 13 78 55 76 53 32 54 58 62 45 21 4 7 61 8 7 3 68 9 26 54 31 22 3 38 65 34 16 58 47 52 29 53 5 8 4 33 33 5 30 6 15 27 12 9 28 19 2 13 10 6 1 2 48 8 12 48 1 41 31 40 7 6 7 61 20 19 30 52 49 17 40 3...
output:
2 2 32 7 3 4 14 22 28 36 40 3 22 46 64 8 1 7 20 24 30 36 54 63 3 3 14 30 6 1 7 11 30 41 47 4 14 27 34 47 2 42 65 1 27 1 9 1 62 5 24 33 42 47 60 2 3 31 3 11 19 29 3 2 15 33 3 25 30 42 3 2 17 59 4 1 11 21 32 2 53 65 3 49 58 65 3 43 60 78 1 78 4 1 11 15 21 5 3 7 17 36 48 2 1 44 ...
result:
ok ok 11000 cases (11000 test cases)
Test #3:
score: 0
Accepted
time: 35ms
memory: 12344kb
input:
2 62980 100000 9859 200000 132897 135912 27509 54599 183887 53114 127233 138596 120860 52471 83158 110644 114040 34102 100501 94779 188044 118947 57443 93009 179886 117863 142316 103026 133746 181956 88732 133751 178946 135462 99588 142382 116231 142902 98641 93039 34860 180746 34292 64655 31584 265...
output:
10 25298 45553 55916 80278 91309 101654 112655 127053 138336 178309 10 19003028 88441083 141717798 296180043 362424389 454856685 535769141 620489184 771756205 925304609
result:
ok ok 2 cases (2 test cases)
Test #4:
score: 0
Accepted
time: 39ms
memory: 12284kb
input:
2 62968 100000 987 200000 132608 47259 159851 136656 33393 145766 92631 125475 63424 186957 111759 164400 22296 95239 28164 39213 176169 72721 179002 29390 26931 55261 57111 143625 62022 48092 13696 31056 31569 136324 120007 167521 106377 119894 48641 106130 151757 146461 151941 92629 57328 134514 1...
output:
100 562 1592 5467 9868 11009 13012 14623 16508 20465 21483 24037 26079 27895 29239 30705 32052 33064 34282 38471 40932 42029 43429 44471 45848 47154 48454 51256 52449 55048 56388 58340 60318 61620 62764 64617 66496 67760 69515 70897 72155 74261 76183 77224 78525 83084 85061 87039 88856 91678 92834 9...
result:
ok ok 2 cases (2 test cases)
Test #5:
score: 0
Accepted
time: 26ms
memory: 11988kb
input:
2 11000 100000 11 200000 163012 113063 193436 164804 38223 97954 77455 12645 65893 7472 154060 115066 197136 68157 57696 125883 36460 36327 2594 182329 52863 9384 142218 108307 164812 102263 68023 123052 114544 38027 42624 82629 131406 110330 63104 198666 154174 168712 164172 28565 120683 174248 170...
output:
1000 263 350 1037 1048 1158 1258 1339 1797 1837 1856 2473 2512 2593 2721 2807 3624 3751 3893 4073 4577 4984 5418 5458 5817 6409 6723 7120 7320 7467 7736 7999 8249 8406 8520 8912 8926 9034 9293 9326 9337 9377 9461 9479 9529 9557 9926 10040 10424 10570 10754 10815 11241 11271 11390 11495 11703 11824 1...
result:
ok ok 2 cases (2 test cases)
Test #6:
score: 0
Accepted
time: 40ms
memory: 12628kb
input:
2 60562 100000 9 200000 124614 82957 175069 159802 77713 148208 87119 195619 137203 187199 151696 49407 92632 129159 22947 9508 83213 155794 8801 14455 4343 187591 112872 118191 84055 164173 127507 13848 193356 103420 67764 102061 151883 129600 112204 64020 118263 44490 15496 61703 177926 140419 918...
output:
9999 10 24 39 54 66 98 127 136 175 189 221 237 249 263 300 350 371 383 402 414 432 442 458 474 487 511 522 533 555 581 592 612 656 669 685 696 706 748 774 791 829 883 903 930 948 1015 1035 1046 1076 1103 1122 1151 1162 1234 1252 1262 1276 1286 1297 1312 1326 1361 1384 1398 1408 1429 1441 1472 1487 1...
result:
ok ok 2 cases (2 test cases)
Test #7:
score: 0
Accepted
time: 51ms
memory: 11400kb
input:
2 78636 100000 2 1000000 160618 689882 425029 248098 24811 473647 831221 372052 602440 158077 883901 645470 489547 863556 32157 371442 621866 941885 650516 873053 188342 224449 770318 464999 453057 304754 700410 82432 583687 478953 393561 989660 199977 458427 411530 814363 964896 69063 874312 224036...
output:
62519 13 17 20 25 64 101 104 131 147 167 188 216 236 257 270 275 280 284 286 289 298 345 361 374 386 408 416 427 429 433 438 441 443 454 462 471 474 495 500 524 556 567 570 628 637 649 655 668 693 741 758 763 771 809 818 836 841 862 868 899 913 938 958 967 987 1001 1010 1022 1039 1057 1059 1082 1096...
result:
ok ok 2 cases (2 test cases)
Extra Test:
score: 0
Extra Test Passed