Submission #47980

#	Time	Username	Problem	Language	Result	Execution time	Memory
47980		yusufake	Palembang Bridges (APIO15_bridge)	C++98	0 / 100	2 ms	936 KiB

bridge

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

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

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

ll f(int a){
    if(!a || a>w) return 1LL<<55;
	a = W[a];
	ll t=0,i;
	for(i=1;i<=nn;i++)
		t += abs(a - A[i]) + abs(a - B[i]) + 1;
	return t;
}

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;
		T[++t] = x; T[++t] = y;
	}
	sort(T+1 , T+t+1); T[0] = -1;
	for(i=1;i<=t;i++) if(T[i] != T[i-1]) W[++w] = T[i];
	
	l=1; r=w;
	for(i=22; 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 'int main()':
bridge.cpp:22: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:22:35: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'll* {aka long long int*}' [-Wformat=]
bridge.cpp:33:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   m = l+r >> 1;
       ~^~
bridge.cpp:22: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: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37