Submission #932207

#	Time	Username	Problem	Language	Result	Execution time	Memory
932207		sleepntsheep	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	58 ms	1960 KiB

bridge

#include<stdio.h>
unsigned X=12345;int rand_(){return(X*=3)>>1;}
int abs(int a){return a<0?-a:a;}
long long minll(long long a,long long b){return a<b?a:b;}
int(*compar)(int,int);
void sort(int*aa,int l,int r){ while(l<r){int i=l,j=l,k=r,tmp,p=aa[l+rand_()%(r-l)]; while(j<k)switch(compar(aa[j],p)){case 0:++j;break;case -1:tmp=aa[j],aa[j]=aa[i],aa[i]=tmp,++i,++j;break;case 1:tmp=aa[j],aa[j]=aa[--k],aa[k]=tmp;break;}sort(aa,l,i);l=k;} }

int c0(int a,int b){return a<b?-1:a>b?1:0;}

int m,s[1<<17],t[1<<17],a[1<<18],k,n0,n;char p,q;long long z;

long long c2(int x,int y){
    long long z=0;for(int i=0;i<m;++i)z+=minll(abs(s[i]-y)+abs(t[i]-y),abs(s[i]-x)+abs(t[i]-x));return z;}

int main(){
    scanf("%d%d",&k,&n0);for(int w,e,i=0;i<n0;++i){scanf(" %c%d %c%d",&p,&w,&q,&e);if(p-q)s[m]=a[n++]=w,t[m++]=a[n++]=e,++z;else z+=abs(w-e);}
    compar=c0;sort(a,0,n);
    if(k==1){for(int i=0;i<n;++i)z+=abs(a[i]-a[n/2]);return printf("%lld",z),0;}

    if(m<=1000){
        long long zz=1e18;for(int i=0;i<n*n;++i)zz=minll(zz,c2(a[i/n],a[i%n]));return printf("%lld",zz+z),0;
    }
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d%d",&k,&n0);for(int w,e,i=0;i<n0;++i){scanf(" %c%d %c%d",&p,&w,&q,&e);if(p-q)s[m]=a[n++]=w,t[m++]=a[n++]=e,++z;else z+=abs(w-e);}
      |     ~~~~~^~~~~~~~~~~~~~~
bridge.cpp:16:57: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d%d",&k,&n0);for(int w,e,i=0;i<n0;++i){scanf(" %c%d %c%d",&p,&w,&q,&e);if(p-q)s[m]=a[n++]=w,t[m++]=a[n++]=e,++z;else z+=abs(w-e);}
      |                                                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37