Submission #1322108

#TimeUsernameProblemLanguageResultExecution timeMemory
1322108blopCoin Collecting (JOI19_ho_t4)C++20
0 / 100
0 ms332 KiB
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template<class T>
using ordered_set = tree<T, null_type, less<T>, 
					rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U>
using ordered_map = tree<T, U, less<T>, rb_tree_tag,
					tree_order_statistics_node_update>;
#define ll long long
#define MOD 1000000007
#define MAXN 2e5
#define SIZE 314
#define pb push_back


ll power(ll a, ll b){
	if (b == 0) return 1;
	ll res = power(a, b / 2);
	if (b % 2 == 1) return res * res % MOD * a % MOD;
	return res * res % MOD;
	
//	if (b % 2 == 1) return res * res * a;
//	return res * res;
}

int main(){
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);
	
	ll n;
	cin >> n;
	vector<pair<ll, ll>> nums(2 * n);
	for (int i = 0; i < 2 * n; i++){
		ll x, y;
		cin >> x >> y;
		nums[i] = {x, y};
	}
	vector<vector<ll>> cnt(n + 1, vector<ll>(3, 0));
	ll ans = 0;
	
	for (int i = 0; i < 2 * n; i++){
		auto [x, y] = nums[i];
		if (x >= 1 && x <= n && y >= 1 && y <= 2){
			cnt[x][y]++;
			continue;
		}
		if (x >= 1 && x <= n){
			if (y > 2){
				cnt[x][2]++;
				ans += y - 2;
				continue;
			}
			else{
				cnt[x][1]++;
				ans += 1 - y;
				continue;
			}
		}
		else if (y >= 1 && y <= 2){
			if (x < 1){
				cnt[1][y]++;
				ans += 1 - x;
			}
			else{
				cnt[n][y]++;
				ans += x - n;
			}
			continue;
		}
		else{
			if (x < 1){
				if (y < 1){
					cnt[1][1]++;
					ans += (1 - x) + (1 - y);
				}
				else{
					cnt[1][2]++;
					ans += (1 - x) + (y - 2);
				}
			}
			else{
				if (y < 1){
					cnt[n][1]++;
					ans += (x - n) + (1 - y);
				}
				else{
					cnt[n][2]++;
					ans += (x - n) + (y - 2);
				}
			}
		}
	}
//	cout << ans << " GG\n";
//	for (int j = 1; j <= 2; j++){
//		for (int i = 1; i <= n; i++){
//			cout << cnt[i][j] << " ";
//		}
//		cout << "\n";
//	}
	
//	queue<tuple<int, int, int, int, int>> q;
//	for (int i = 1; i <= n; i++){
//		for (int j = 1; j <= 2; j++){
//			if (cnt[i][j] > 1){
//				q.push({i, j, 0, i, j});
//			}
//		}
//	}
//	int xDir[] = {0, 0, -1, 1};
//	int yDir[] = {-1, 1, 0, 0};
//	while(!q.empty()){
//		auto [x, y, cost, oriX, oriY] = q.front();
//		q.pop();
//		if (cnt[oriX][oriY] <= 1){
//			continue;
//		}
//		for (int i = 0; i < 4; i++){
//			
//		}
//	}
	ll lastYes = n;
	for (int i = n; i >= 1; i--){
		while (lastYes >= 1 && cnt[lastYes][1] <= 1 && cnt[lastYes][2] <= 1){
			lastYes--;
			continue;
		}
		if (lastYes <= 0) break;
		if (cnt[i][1] == 0){
			cnt[i][1]++;
			if (cnt[lastYes][1] > 1){
				cnt[lastYes][1]--;
				ans += abs(i - lastYes);
			}
			else if (lastYes - 1 >= 1 && cnt[lastYes - 1][1] > 1){
				cnt[lastYes - 1][1]--;
				ans += abs(i - lastYes) + 1;
			}
			else{
				cnt[lastYes][2]--;
				ans += abs(i - lastYes) + 1;
			}
			i++;
//			for (int j = 1; j <= 2; j++){
//				for (int i = 1; i <= n; i++){
//					cout << cnt[i][j] << " ";
//				}
//				cout << "\n";
//			}
//			cout << "\n\n";
			continue;
		}
		if (cnt[i][2] == 0){
			cnt[i][2]++;
			if (cnt[lastYes][2] > 1){
				cnt[lastYes][2]--;
				ans += abs(i - lastYes);
			}
			else if (lastYes - 1 >= 1 && cnt[lastYes - 1][2] > 1){
				cnt[lastYes - 1][2]--;
				ans += abs(i - lastYes) + 1;
			}
			else{
				cnt[lastYes][1]--;
				ans += abs(i - lastYes) + 1;
			}
			i++;
//			for (int j = 1; j <= 2; j++){
//				for (int i = 1; i <= n; i++){
//					cout << cnt[i][j] << " ";
//				}
//				cout << "\n";
//			}
//			cout << "\n\n";
			continue;
		}
		
	}
	cout << ans << "\n";
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...