Submission #1149360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149360		adlin	Coin Collecting (JOI19_ho_t4)	C++20	0 / 100	0 ms	328 KiB

joi2019_ho_t4

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define F first
#define S second
#define all(v) (v).begin(),(v).end()
#define ull unsigned long long
#define ahahahant ios_base::sync_with_stdio(0);cin.tie(0); 
#define int long long

using namespace std;

//mt19937 rng( chrono::steady_clock::now().time_since_epoch().count());
// 
//ll rand( ll l, ll r )
//{
//    uniform_int_distribution <ll> uid( l, r );
//    return uid( rng );
//}

ll lcm(ll x, ll y){
	return x / __gcd(x,y) * y;
}

ll binpow(ll a, ll b, ll m){
	if(!b) return 1ll;
	if(b & 1) return binpow(a,b-1,m) * a % m;
	int res = binpow(a,b/2,m) % m;
	return res * res % m;
}

const int maxn = 1e6 + 6;

const int mod = 1e9 + 7;

const int mod2 = 998244353;

const ll inf = 1e18;

const int inf2 = 1e9;

const int K = 300;

int n,x[maxn],y[maxn];

int d[maxn][3],cnt[maxn][3];

bool used[maxn];

void who(){
	
	cin >> n;
		
	for(int i = 1; i <= n + n; i++){
		cin >> x[i] >> y[i];
	}
	
	ll ans = 0;
	
	for(int i = 1; i <= n + n; i++){
		if(1 <= x[i] && x[i] <= n && 1 <= y[i] && y[i] <= 2){
			cnt[x[i]][y[i]]++;
		}
		else if(1 <= x[i] && x[i] <= n){
			if(y[i] > 2){
				ans += abs(y[i] - 2);
				cnt[x[i]][2]++;
			}
			else {
				ans += abs(y[i] - 1);
				cnt[x[i]][1]++;
			}
		}
		else if(1 <= y[i] && y[i] <= 2){
			if(x[i] < 1){
				ans += abs(x[i] - 1);
				cnt[1][y[i]]++;
			}
			else {
				ans += abs(x[i] - n);
				cnt[n][y[i]]++;
			}
		}
		else {
			if(x[i] < 1){
				if(y[i] < 1){
					cnt[1][1]++;
					ans += abs(x[i] - 1) + abs(y[i] - 1);	
				}
				else {
					cnt[1][2]++;
					ans += abs(x[i] - 1) + abs(y[i] - 2);
				}
			}
			else {
				if(y[i] < 1){
					cnt[n][1]++;
					ans += abs(x[i] - n) + abs(y[i] - 1);	
				}
				else {
					cnt[n][2]++;
					ans += abs(x[i] - n) + abs(y[i] - 2);
				}
			}
		}
	}	
	
	vector <pair<int,int>> q;
		
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= 2; j++){
			while(cnt[i][j]--) {
				q.push_back({i,j});
			}
		}
	}
	
	sort(all(q));
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= 2; j++){
			ll mn = 1e18;
			int ind = -1;
			for(int k = 0; k < q.size(); k++){
				if(used[k]) continue;
				if(mn > abs(i - q[k].F) + abs(j - q[k].S)){
					mn = abs(i - q[k].F) + abs(j - q[k].S);
					ind = k;
				}
			}
			used[ind] = 1;
			ans += mn;
		}
	}
	
	cout << ans;
	
}

signed main(){
	
//	freopen("yinyang.in", "r", stdin);
//	freopen("yinyang.out", "w", stdout);
	
	ahahahant
		
	int tt = 1;
	
//	cin >> tt;
	
	while(tt--){
		who();
	}
	
	
	return 0;
}

/*
__builtin_popcount
__builtin_clz
__builtin_ctz
__builtin_parity
int get(int r){
	int res = 0;
	for(; r >= 0; r = (r & (r + 1)) - 1) res += f[r];
	return res;
}
 
void upd(int i, int val){
	for(; i <= n; i = (i | (i + 1))) f[i] += val;
}
*/ 	

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