Submission #102295

#	Time	Username	Problem	Language	Result	Execution time	Memory
102295		Nicholas_Patrick	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	81 ms	2148 KiB

bridge

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

int k, n;
vector <int> h, w, hw;
int movementI, movementJ;
long long check(int i, int j){
	if(i>=n<<1||j>=n<<1||i<0||j<0)return 200000000000000;
	long long tot=0;
	movementI=0, movementJ=0;
	int throughI, throughJ;
	for(int k = 0;k < n;k ++){
		throughI=abs(h[k]-hw[i])+abs(w[k]-hw[i]);
		throughJ=abs(h[k]-hw[j])+abs(w[k]-hw[j]);
		if(throughI<throughJ){
			if(hw[i]<h[k])
				movementI++;
			if(hw[i]>w[k])
				movementI--;
			tot+=throughI;
		}else{
			if(hw[j]<h[k])
				movementJ++;
			if(hw[j]>w[k])
				movementJ--;
			tot+=throughJ;
		}
	}
	return tot;
}
int main(){
	scanf("%d %d", &k, &n);
	bool cross;int s, t;
	long long tot1=0;
	char c;
	while(n--){
		while(true){
			c=getchar();
			if(c=='A'){
				cross=false;
				break;
			}else if(c=='B'){
				cross=true;
				break;
			}
		}
		scanf("%d", &s);
		while(true){
			c=getchar();
			if(c=='A'){
				break;
			}else if(c=='B'){
				cross^=true;
				break;
			}
		}
		scanf("%d", &t);
		if(cross){
			if(s>t)
				swap(s, t);
			h.push_back(s);
			w.push_back(t);
			hw.push_back(s);
			hw.push_back(t);
			tot1++;
		}else{
			tot1+=abs(t-s);
		}
	}
	n=h.size();
	sort(hw.begin(), hw.end());
	if(k==1){
		n=hw.size();
		long long tot2=0;
		k=n>>1;
		for(int i = 0;i < n;i ++)
			tot2+=abs(hw[k]-hw[i]);
		printf("%lld\n", tot1+tot2);
	}else if(k==2){
		long long tot2=200000000000000;
		long long curtot;
		long long up, down, left, right, minall;
		int i=(n<<1)/3, j=(n<<2)/3;
		for(int l = 0;l < 400;l ++){
			curtot=check(i, j);
			i+=movementI;
			j+=movementJ;
			tot2=min(tot2, curtot);
		}
		for(int l = 0;l < 400;l ++){
			curtot=check(i, j);
			if(l&1)
				i+=movementI;
			else
				j+=movementJ;
			tot2=min(tot2, curtot);
		}
		while(true){
			curtot=check(i, j);
			up=check(i, j+1);
			down=check(i, j-1);
			left=check(i-1, j);
			right=check(i+1, j);
			minall=min(curtot, min(up, min(down, min(left, right))));
			tot2=min(tot2, minall);
			if(curtot==minall)
				break;
			if(up==minall)
				j++;
			if(down==minall)
				j--;
			if(left==minall)
				i--;
			if(right==minall)
				i++;
		}
		printf("%lld\n", tot1+tot2);
	}
	return 0;
}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

*/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &k, &n);
  ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s);
   ~~~~~^~~~~~~~~~
bridge.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~

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