Submission #47987

#	Time	Username	Problem	Language	Result	Execution time	Memory
47987		yusufake	Palembang Bridges (APIO15_bridge)	C++98	31 / 100	64 ms	2284 KiB

bridge

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 5;

ll A[N],B[N],n,k,nn,t,w,i,x,y,l,m,r,ans;
char c1,c2;

ll g(ll a, ll b){
	ll t=0,i;
	for(i=1;i<=nn;i++)
		t += min( abs(a - A[i]) + abs(a - B[i]) , b == -1 ? 1LL<<55 : abs(b - A[i]) + abs(b - B[i]) ) + 1;
	return t;
}

ll f(ll a){
    if(k == 1) return g(a,-1);
    ll i, l=a+1,m,r=1<<30;
    for(i=33; i--;){
        m = l+r >> 1;
        if(g(a,m) > g(a,m+1)) l = m;
        else r = m;
    }
    return min( g(a,l-1) , min( g(a,l),g(a,l+1))  );
}

int main(){
	cin >> k >> n;
	for(i=1;i<=n;i++){
		scanf(" %c%d %c%d",&c1,&x,&c2,&y);
		if(x > y) swap(x,y);
        if(c1 == c2) { ans += y-x; continue; }
		A[++nn] = x; B[nn] = y;
	}

    l=0; r=1<<30;
	for(i=33; i--;){
		m = l+r >> 1;
		if(f(m) > f(m+1)) l = m;
		else r = m;
	}

    cout << ans + min( f(l-1), min( f(l) , f(l+1) ) );
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'll f(ll)':
bridge.cpp:21:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         m = l+r >> 1;
             ~^~
bridge.cpp: In function 'int main()':
bridge.cpp:31:35: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
   scanf(" %c%d %c%d",&c1,&x,&c2,&y);
                          ~~       ^
bridge.cpp:31:35: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'll* {aka long long int*}' [-Wformat=]
bridge.cpp:39:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   m = l+r >> 1;
       ~^~
bridge.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d %c%d",&c1,&x,&c2,&y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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