Submission #521297

#	Time	Username	Problem	Language	Result	Execution time	Memory
521297		AdamGS	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	320 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
const ll INF=1e9+7;
pair<ll,ll>T[LIM];
vector<ll>V[2];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n, ans=0, ile[2];
	cin >> n; n*=2;
	ile[0]=ile[1]=0;
	rep(i, n) {
		cin >> T[i].st >> T[i].nd;
		if(T[i].st<1) {
			ans+=abs(T[i].st-1);
			T[i].st=1;
		} else if(T[i].st>n) {
			ans+=abs(T[i].st-n);
			T[i].st=n;
		}
		if(T[i].nd<1) {
			ans+=abs(T[i].nd-1);
			T[i].nd=1;
		} else if(T[i].nd>2) {
			ans+=abs(T[i].nd-2);
			T[i].nd=2;
		}
		V[T[i].nd-1].pb(T[i].st);
	}
	sort(all(V[0]));
	sort(all(V[1]));
	int l1=0, l2=0;
	rep(i, n/2) {
		if(l1<V[0].size()) {
			if(l2<V[1].size()) {
				ll a=abs(V[0][l1]-i-1)+abs(V[1][l2]-i-1), b=INF, c=INF;
				if(l1+1<V[0].size()) {
					b=abs(V[0][l1]-i-1)+abs(V[0][l1+1]-i-1)+1;
				}
				if(l2+1<V[1].size()) {
					c=abs(V[1][l2]-i-1)+abs(V[1][l2+1]-i-1)+1;
				}
				ans+=min(min(a, b), c);
				if(a<=b && a<=c) {
					++l1; ++l2;
				} else if(b<=a && b<=c) l1+=2;
				else l2+=2;
			} else {
				ans+=abs(V[0][l1]-i-1)+abs(V[0][l1+1]-i-1)+1;
				l1+=2;
			}
		} else {
			ans+=abs(V[1][l2]-i-1)+abs(V[1][l2+1]-i-1)+1;
			l2+=2;
		}
	}	
	cout << ans << '\n';
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:41:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   if(l1<V[0].size()) {
      |      ~~^~~~~~~~~~~~
joi2019_ho_t4.cpp:42:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    if(l2<V[1].size()) {
      |       ~~^~~~~~~~~~~~
joi2019_ho_t4.cpp:44:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     if(l1+1<V[0].size()) {
      |        ~~~~^~~~~~~~~~~~
joi2019_ho_t4.cpp:47:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     if(l2+1<V[1].size()) {
      |        ~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63