oj.uz

Submission #263871

# Submission time Handle Problem Language Result Execution time Memory
263871 2020-08-14T02:50:58 Z kaage Palembang Bridges (APIO15_bridge) C++17
63 / 100
 284 ms 2732 KB 
#line 2 "/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp"
#define _CRT_SECURE_NO_WARNINGS
#pragma target("avx2")
#pragma optimize("O3")
#pragma optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define all(V) V.begin(),V.end()
typedef long long lint;
typedef unsigned long long ulint;
typedef std::pair<int, int> P;
typedef std::pair<lint, lint> LP;
constexpr int INF = INT_MAX/2;
constexpr lint LINF = LLONG_MAX/2;
constexpr double eps = DBL_EPSILON;
constexpr double PI=3.141592653589793238462643383279;
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
inline lint gcd(lint a, lint b) {
	while (b) {
		lint c = a;
		a = b; b = c % b;
	}
	return a;
}
inline lint lcm(lint a, lint b) {
	return a / gcd(a, b) * b;
}
bool isprime(lint n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
template<typename T>
T mypow(T a, lint b) {
	T res(1);
	while(b){
		if(b&1)res*=a;
		a*=a;
		b>>=1;
	}
	return res;
}
lint modpow(lint a, lint b, lint m) {
	lint res(1);
	while(b){
		if(b&1){
			res*=a;res%=m;
		}
		a*=a;a%=m;
		b>>=1;
	}
	return res;
}
template<typename T>
void printArray(std::vector<T>& vec) {
	rep(i, vec.size()){
		std::cout << vec[i];
		std::cout<<(i==(int)vec.size()-1?"\n":" ");
	}
}
template<typename T>
void printArray(T l, T r) {
	T rprev = std::prev(r);
	for (T i = l; i != rprev; i++) {
		std::cout << *i << " ";
	}
	std::cout << *rprev << std::endl;
}
LP extGcd(lint a,lint b) {
	if(b==0)return {1,0};
	LP s=extGcd(b,a%b);
	std::swap(s.first,s.second);
	s.second-=a/b*s.first;
	return s;
}
LP ChineseRem(const lint& b1,const lint& m1,const lint& b2,const lint& m2) {
	lint p=extGcd(m1,m2).first;
	lint tmp=(b2-b1)*p%m2;
	lint r=(b1+m1*tmp+m1*m2)%(m1*m2);
	return std::make_pair(r,m1*m2);
}
/*template<typename F>
inline constexpr decltype(auto) lambda_fix(F&& f){
	return [f=std::forward<F>(f)](auto&&... args){
		return f(f,std::forward<decltype(args)>(args)...);
	};
}*/
#line 2 "main.cpp"
int n,k;
std::vector<P> vec;
lint check(int x,int y){
	lint res=0;
	for(const P& i:vec){
		int a=std::abs(i.first-x)+1+std::abs(x-i.second);
		int b=std::abs(i.first-y)+1+std::abs(y-i.second);
		res+=std::min(a,b);
	}
	return res;
}
int main(){
	std::cin>>k>>n;
	lint ans=0;
	rep(i,n){
		char p,q;
		int s,t;
		std::cin>>p>>s>>q>>t;
		if(p!=q){
			if(s>t)std::swap(s,t);
			vec.emplace_back(s,t);
		}
		else ans+=std::abs(s-t);
	}
	if(vec.empty()){
		std::cout<<ans<<std::endl;
		return 0;
	}
	if(k==1){
		std::vector<int> vec2;
		for(const P& i:vec){
			vec2.emplace_back(i.first);
			vec2.emplace_back(i.second);
		}
		std::sort(all(vec2));
		int x=vec2[vec2.size()/2];
		for(const P& i:vec){
			ans+=std::abs(i.first-x)+1+std::abs(x-i.second);
		}
		std::cout<<ans<<std::endl;
	}
	else{
		std::vector<int> vec2;
		for(const P& i:vec){
			vec2.emplace_back(i.first);
			vec2.emplace_back(i.second);
		}
		std::sort(all(vec2));
		lint cnt=LINF,beforeupdate=0;
		for(int i=std::max(0,((int)vec2.size()-1000)/3);i<vec2.size();i++){
			if(i&&vec2[i]==vec2[i-1])continue;
			int min=-1,max=1000000001;
			while(min+2<max){
				int mid=(min+max)/2;
				if(check(vec2[i],mid)<=check(vec2[i],mid+1))max=mid+1;
				else min=mid;
			}
			if(chmin(cnt,check(vec2[i],min)))beforeupdate=i;
			if(chmin(cnt,check(vec2[i],min+1)))beforeupdate=i;
			if(chmin(cnt,check(vec2[i],max)))beforeupdate=i;
			if(beforeupdate+1000<i)break;
		}
		std::cout<<ans+cnt<<std::endl;
	}
}

Compilation message

/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:3: warning: ignoring #pragma target  [-Wunknown-pragmas]
/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:4: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:5: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
main.cpp: In function 'int main()':
main.cpp:51:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 89 ms 2732 KB Output is correct
13 Correct 209 ms 2668 KB Output is correct
14 Correct 123 ms 2540 KB Output is correct
15 Correct 121 ms 1568 KB Output is correct
16 Correct 147 ms 2668 KB Output is correct
17 Correct 193 ms 2708 KB Output is correct
18 Correct 173 ms 2668 KB Output is correct
19 Correct 208 ms 2712 KB Output is correct
20 Correct 167 ms 2668 KB Output is correct
21 Correct 184 ms 2672 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 6 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 15 ms 384 KB Output is correct
15 Correct 268 ms 388 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 13 ms 384 KB Output is correct
18 Correct 63 ms 376 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 284 ms 384 KB Output is correct
21 Correct 251 ms 504 KB Output is correct
22 Correct 260 ms 504 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 229 ms 380 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 6 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 6 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 15 ms 384 KB Output is correct
15 Correct 275 ms 504 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 12 ms 384 KB Output is correct
18 Correct 64 ms 376 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 258 ms 384 KB Output is correct
21 Correct 219 ms 384 KB Output is correct
22 Correct 248 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 222 ms 384 KB Output is correct
25 Correct 113 ms 2664 KB Output is correct
26 Incorrect 145 ms 2664 KB Output isn't correct
27 Halted 0 ms 0 KB -