oj.uz

Submission #263839

# Submission time Handle Problem Language Result Execution time Memory
263839 2020-08-14T02:36:16 Z kaage Palembang Bridges (APIO15_bridge) C++17
63 / 100
 2000 ms 3468 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;
		rep(i,vec2.size()){
			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;
			}
			chmin(cnt,check(vec2[i],min));
			chmin(cnt,check(vec2[i],min+1));
			chmin(cnt,check(vec2[i],max));
		}
		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()':
/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:33:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
main.cpp:51:3: note: in expansion of macro 'rep'

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 276 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 288 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 1 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 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 3 ms 384 KB Output is correct
12 Correct 94 ms 2668 KB Output is correct
13 Correct 211 ms 2796 KB Output is correct
14 Correct 121 ms 2572 KB Output is correct
15 Correct 126 ms 1520 KB Output is correct
16 Correct 152 ms 2668 KB Output is correct
17 Correct 198 ms 2696 KB Output is correct
18 Correct 187 ms 2672 KB Output is correct
19 Correct 218 ms 2668 KB Output is correct
20 Correct 165 ms 2684 KB Output is correct
21 Correct 188 ms 2664 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 7 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 9 ms 256 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 5 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 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 4 ms 368 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 5 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 5 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 439 ms 384 KB Output is correct
14 Correct 454 ms 400 KB Output is correct
15 Correct 427 ms 408 KB Output is correct
16 Correct 47 ms 276 KB Output is correct
17 Correct 146 ms 388 KB Output is correct
18 Correct 63 ms 384 KB Output is correct
19 Correct 457 ms 384 KB Output is correct
20 Correct 489 ms 504 KB Output is correct
21 Correct 481 ms 384 KB Output is correct
22 Correct 458 ms 408 KB Output is correct
23 Correct 455 ms 504 KB Output is correct
24 Correct 570 ms 508 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 4 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 5 ms 384 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 384 KB Output is correct
11 Correct 5 ms 256 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 437 ms 392 KB Output is correct
14 Correct 501 ms 404 KB Output is correct
15 Correct 448 ms 408 KB Output is correct
16 Correct 47 ms 376 KB Output is correct
17 Correct 126 ms 388 KB Output is correct
18 Correct 90 ms 384 KB Output is correct
19 Correct 483 ms 400 KB Output is correct
20 Correct 482 ms 412 KB Output is correct
21 Correct 469 ms 400 KB Output is correct
22 Correct 477 ms 408 KB Output is correct
23 Correct 484 ms 404 KB Output is correct
24 Correct 461 ms 400 KB Output is correct
25 Execution timed out 2076 ms 3468 KB Time limit exceeded
26 Halted 0 ms 0 KB -