QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#618147#1961. PostmanCheek_supportWA 1ms9952kbC++204.4kb2024-10-06 19:10:252024-10-06 19:10:26

Judging History

你现在查看的是最新测评结果

  • [2024-10-06 19:10:26]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9952kb
  • [2024-10-06 19:10:25]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define mk(x,y) make_pair(x,y)
using namespace std;
int read(){
    char ch=getchar();int x=0,f=1;
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return f*x;
}
int n,m;
const int N=300100;
ll a[N],b[N];
pair<ll ,int> c[N];
int x,y;
bool bo[N];
void work1(){
    int L=m,R=n-m-1;
    if(L==0){
        if(x==1)printf("%lld\n",a[n]-a[1]);
        else puts("-1");
        return;
    }
    if(R==0){
        if(x==n)printf("%lld\n",a[n]-a[1]);
        else puts("-1");
        return;
    }
    ll ans=(1ll<<60);
    {
        ll res=0;
        int t=n-x-R;
        if(t>0){
            if(t==n-x-1)res=a[n]-a[x+1];
            else{
                for(int i=1;i<=n-x-2;i++)
                    c[i]=mk(b[i+x],i+x);
                sort(c+1,c+n-x-1);
                ll num=0;res=(1ll<<60);
                for(int i=1;i<=t;i++)
                    num+=c[i].first*2,bo[c[i].second]=1;
                res=min(res,num);
                int i=t;
                for(int j=n-1;j>=n-t;j--){
                    if(bo[j-1]){
                        bo[j-1]=0;
                        num+=b[j]-2*b[j-1];
                    }else{
                        for(;!bo[c[i].second];)i--;
                        bo[c[i].second]=0;
                        num+=b[j]-2*c[i].first;
                    }
                    res=min(res,num);
                }
            }
        }
        ans=min(ans,res+a[x]+a[n]-2*a[1]);
    }

    // for(int i=1;i<=n;i++)a[i]=-a[i];
    // sort(a+1,a+n+1);
    // for(int i=1;i<n;i++)b[i]=a[i+1]-a[i];
    // x=n-x+1;
    // swap(L,R);
    // memset(bo,0,sizeof(bo));

    // {
    //     ll res=0;
    //     int t=n-x-R;
    //     if(t>0){
    //         if(t==n-x-1)res=a[n]-a[x+1];
    //         else{
    //             for(int i=1;i<=n-x-2;i++)
    //                 c[i]=mk(b[i+x],i+x);
    //             sort(c+1,c+n-x-1);
    //             ll num=0;res=(1ll<<60);
    //             for(int i=1;i<=t;i++)
    //                 num+=c[i].first*2,bo[c[i].second]=1;
    //             res=min(res,num);
    //             int i=t;
    //             for(int j=n-1;j>=n-t;j--){
    //                 if(bo[j-1]){
    //                     bo[j-1]=0;
    //                     num+=b[j]-2*b[j-1];
    //                 }else{
    //                     for(;!bo[c[i].second];)i--;
    //                     bo[c[i].second]=0;
    //                     num+=b[j]-2*c[i].first;
    //                 }
    //                 res=min(res,num);
    //             }
    //         }
    //     }
    //     ans=min(ans,res+a[x]+a[n]-2*a[1]);
    // }

    printf("%lld\n",ans);
}
void work2(){
    // for(;;);
    int L=m,R=n-m;
    
    if(y<x){
        for(int i=1;i<=n;i++)a[i]=-a[i];
        sort(a+1,a+n+1);
        for(int i=1;i<n;i++)b[i]=a[i+1]-a[i];
        x=n-x+1;y=n-y+1;
        swap(L,R);
    }

    if(R==0){puts("-1");return;}
    if(L==1){
        if(x==1&&y==n){
            ll minn=(1ll<<60);
            for(int i=2;i<n-1;i++)
                minn=min(minn,b[i]);
            if(minn==(1ll<<60))puts("-1");
            else printf("%lld\n",a[n]-a[1]+2*minn);
            return;
        }
        if(x==1||y==n)printf("%lld\n",2*(a[n]-a[1])-(a[y]-a[x]));
        else puts("-1");
        return;
    }
    if(L==0){
        if(x==1&&y==n)printf("%lld\n",a[n]-a[1]);
        else puts("-1");
        return;
    }
    if(R==1){
        if(y-x==1)printf("%lld\n",2*(a[n]-a[1])-(a[y]-a[x]));
        else puts("-1");
        return;
    }

    int t=y-x-R;
    ll res=0;
    if(t>0){
        ll num=0;
        for(int i=1;i<y-x-1;i++)
            c[i]=mk(b[x+i],x+i);
        sort(c+1,c+y-x-1);
        for(int i=1;i<=t;i++)
            num+=2*c[i].first;
        res=num;
    }
    printf("%lld\n",res+2*(a[n]-a[1])-(a[y]-a[x]));

}
int main(){
    n=read();m=read();
    int k=read();
    for(int i=1;i<=n;i++)a[i]=read();
    x=0,y=a[n];
    a[n+1]=0;n++;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        if(a[i]==x){x=i;break;}
    for(int i=1;i<=n;i++)
        if(a[i]==y){y=i;break;}
    for(int i=1;i<n;i++)b[i]=a[i+1]-a[i];
    if(k==1)work1();
    else work2();
    return 0;
}
/*
5 4 2
-20 -15 20 30 10

5 4 1
-20 -15 20 30 10

7 1 2
10 13 -30 24 50 -5 -21
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 9952kb

input:

100 0 1
751 558 131 292 317 886 785 847 224 668 649 358 725 250 953 65 176 733 461 84 114 977 628 673 798 863 373 827 51 630 518 347 527 876 366 241 452 670 813 314 846 342 357 460 985 581 841 843 282 907 327 656 411 944 421 99 441 388 568 763 167 351 793 916 517 109 999 390 272 639 513 534 304 253 ...

output:

999

result:

ok single line: '999'

Test #2:

score: 0
Accepted
time: 1ms
memory: 9952kb

input:

100 50 1
654 349 533 94 619 754 498 939 469 518 3 661 431 214 195 198 989 548 561 312 262 629 807 981 624 639 178 765 706 782 888 611 553 363 336 91 176 485 735 791 596 455 390 760 995 202 417 82 798 883 209 155 725 908 789 56 49 899 231 423 815 228 314 400 748 946 736 840 385 446 938 284 10 917 593...

output:

1397

result:

ok single line: '1397'

Test #3:

score: 0
Accepted
time: 1ms
memory: 7852kb

input:

100 99 1
266 337 80 671 358 778 217 288 219 48 863 19 137 987 602 415 155 398 753 956 210 317 94 303 997 192 123 442 666 959 685 71 34 588 615 214 327 881 582 51 646 630 291 354 749 108 984 308 813 182 384 699 114 692 611 296 590 432 103 240 341 465 969 370 771 914 250 656 742 708 174 323 939 493 17...

output:

1986

result:

ok single line: '1986'

Test #4:

score: 0
Accepted
time: 1ms
memory: 7732kb

input:

100 100 1
713 172 634 763 181 502 78 995 598 751 792 961 585 335 952 343 375 627 651 515 856 121 743 931 18 492 726 517 136 143 314 993 80 29 283 427 248 274 114 200 535 94 174 782 818 90 806 88 104 808 910 892 791 462 304 676 67 973 901 891 705 567 475 444 949 846 299 735 233 914 803 27 810 210 396...

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 7636kb

input:

100 0 1
-102 -827 -638 -660 -604 -258 -692 -237 -927 -371 -129 -908 -830 -229 -585 -364 -103 -58 -975 -153 -563 -17 -201 -443 -56 -560 -606 -45 -891 -331 -349 -420 -266 -219 -482 -716 -51 -723 -876 -211 -121 -63 -814 -239 -937 -541 -74 -69 -334 -42 -227 -479 -571 -137 -913 -885 -525 -475 -930 -405 -...

output:

-1

result:

ok single line: '-1'

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 7920kb

input:

100 1 1
-747 -27 -215 -283 -833 -584 -531 -295 -636 -725 -100 -506 -108 -426 -574 -305 -919 -207 -540 -770 -264 -67 -388 -444 -77 -778 -474 -957 -706 -467 -438 -245 -240 -228 -40 -523 -803 -669 -198 -11 -740 -911 -990 -604 -236 -628 -864 -897 -440 -789 -874 -941 -153 -1 -52 -345 -819 -480 -731 -612 ...

output:

1980

result:

wrong answer 1st lines differ - expected: '1979', found: '1980'