Submission #497046

#	Time	Username	Problem	Language	Result	Execution time	Memory
497046		AQ0212	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	280 KiB

joi2019_ho_t4

#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>

#define ll long long int
#define pb push_back
#define pll pair < ll , ll >
#define fi first
#define se second
#define all(x) x.begin(), x.end()

using namespace std;

ll inf2 = 3e18;

ll x[ 100111 ], y[ 100111 ], used[ 3 ][ 100111 ], ans;
vector < pll > unused, overused;

int main(){
    ll n;

	cin >> n;

	for(int i = 1; i <= n * 2; i ++){
		cin >> x[ i ] >> y[ i ];
	}

	for(int i = 1; i <= n * 2; i ++){
		if(1 <= x[ i ] && x[ i ] <= n && 1 <= y[ i ] && y[ i ] <= 2){
			used[ y[ i ] ][ x[ i ] ] ++;
			// cout << "Selam\n";
		}else if(1 <= x[ i ] && x[ i ] <= n){
			if(y[ i ] < 1){
				ans += abs(1 - y[ i ]);
				used[ 1 ][ x[ i ] ] ++;
				// cout << "1: " << ans << " i:" << i << "\n";
			}else{
				ans += abs(2 - y[ i ]);
				used[ 2 ][ x[ i ] ] ++;
				// cout << "2: " << ans << " i:" << i << "\n";
			}
		}else if(1 <= y[ i ] && y[ i ] <= 2){
			if(x[ i ] < 1){
				ans += abs(1 - x[ i ]);
				used[ y[ i ] ][ 1 ] ++;
				// cout << "3: " << ans << " i:" << i << "\n";
			}else{
				ans += abs(n - x[ i ]);
				used[ y[ i ] ][ n ] ++;
				// cout << "4: " << ans << " i:" << i << "\n";
			}
		}else{
			ll lt, rt, lb, rb, mn;

			lt = abs(x[ i ] - 1) + abs(y[ i ] - 2);
			lb = abs(x[ i ] - 1) + abs(y[ i ] - 1);
			rt = abs(x[ i ] - n) + abs(y[ i ] - 2);
			rb = abs(x[ i ] - n) + abs(y[ i ] - 1);

			mn = min(min(lt, lb), min(rb, rt));
			ans += mn;

			if(mn == lt){
				used[ 2 ][ 1 ] ++;
			}else if(mn == lb){
				used[ 1 ][ 1 ] ++;
			}else if(mn == rt){
				used[ 2 ][ n ] ++;
			}else{
				used[ 1 ][ n ] ++;
			}

			// cout << "5: " << ans << " i:" << i << "\n";
		}

	}

	for(int i = 1; i <= 2; i ++){
		for(int j = 1; j <= n; j ++){
			if(!used[ i ][ j ]){
				unused.pb(make_pair(i, j));
			}
			if(used[ i ][ j ] > 1){
				for(int k = 2; k <= used[ i ][ j ]; k ++)
					overused.pb(make_pair(i, j));
			}
		}
	}

	for(int i = 0; i < overused.size(); i ++){
		ll mn = inf2, id = -1;
		for(int j = 0; j < unused.size(); j ++){
			ll manhut_dis = abs(overused[ i ].fi - unused[ j ].fi) + abs(overused[ i ].se - unused[ j ].se);

			if(manhut_dis < mn){
				mn = manhut_dis;
				id = j;
			}
		}

		ans += mn;
		unused.erase(unused.begin() + id);
	}


	// for(int i = 1; i <= 2; i ++){
	// 	for(int j = 1; j <= n; j ++){
	// 		cout << used[ i ][ j ] << " ";
	// 	}
	// 	cout << "\n";
	// }
	cout << "\n" << ans;

}

/*

4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1

3
0 0
0 4
4 0
2 1
2 5
-1 1

5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3

*/

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(int i = 0; i < overused.size(); i ++){
      |                 ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t4.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for(int j = 0; j < unused.size(); j ++){
      |                  ~~^~~~~~~~~~~~~~~

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