Submission #494765

#	Time	Username	Problem	Language	Result	Execution time	Memory
494765		Haruto810198	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	324 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 200010;

int n;
pii pt[MAX];
int tx[MAX];
int res;

int dp[3], newdp[3];

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	FOR(i, 1, 2*n, 1){
		cin>>pt[i].F>>pt[i].S;
		tx[i] = (i + 1) / 2;
	}
	
	sort(pt+1, pt+2*n+1);

	FOR(i, 1, 2*n, 1){
		res += abs(pt[i].F - tx[i]);
	}
	
	vector<vi> groups;
	vi tmp = {pt[1].S};
	int pv = pt[1].S;

	FOR(i, 2, 2*n, 1){
		if(pt[i].F != pv){
			pv = pt[i].F;
			sort(tmp.begin(), tmp.end());
			groups.pb(tmp);
			tmp.clear();
		}
		tmp.pb(pt[i].S);
	}
	
	if(!tmp.empty()) groups.pb(tmp);
	
	dp[0] = 0;
	dp[1] = LNF;
	dp[2] = LNF;
	
	for(vi G : groups){
		int sz = szof(G);
		int c1;
		int sum;
		
		FOR(i, 0, 2, 1) newdp[i] = LNF;
		
		if(dp[0] < LNF){
			if(sz % 2 == 0){
				// 0 -> 0
				c1 = sz / 2;
				sum = 0;
				FOR(i, 0, c1-1, 1) sum += abs(G[i] - 1);
				FOR(i, c1, sz-1, 1) sum += abs(G[i] - 2);
				newdp[0] = min(newdp[0], dp[0] + sum);
			}
			else{
			 	// 0 -> 1
				c1 = sz / 2 + 1;
				sum = 0;
				FOR(i, 0, c1-1, 1) sum += abs(G[i] - 1);
				FOR(i, c1, sz-1, 1) sum += abs(G[i] - 2);
				newdp[1] = min(newdp[1], dp[0] + sum);
				
				// 0 -> 2
				c1 = sz / 2;
				sum = 0;
				FOR(i, 0, c1-1, 1) sum += abs(G[i] - 1);
				FOR(i, c1, sz-1, 1) sum += abs(G[i] - 2);
				newdp[2] = min(newdp[2], dp[0] + sum);
			}
		}
		else{
			if(sz % 2 == 0){
				// 1 -> 2
				c1 = sz / 2 - 1;
				sum = 0;
				FOR(i, 0, c1-1, 1) sum += abs(G[i] - 1);
				FOR(i, c1, sz-1, 1) sum += abs(G[i] - 2);
				newdp[2] = min(newdp[2], dp[1] + sum);

				// 1 -> 1, 2 -> 2
				c1 = sz / 2;
				sum = 0;
				FOR(i, 0, c1-1, 1) sum += abs(G[i] - 1);
				FOR(i, c1, sz-1, 1) sum += abs(G[i] - 2);
				newdp[1] = min(newdp[1], dp[1] + sum);
				newdp[2] = min(newdp[2], dp[2] + sum);
				
				// 2 -> 1
				c1 = sz / 2 + 1;
				sum = 0;
				FOR(i, 0, c1-1, 1) sum += abs(G[i] - 1);
				FOR(i, c1, sz-1, 1) sum += abs(G[i] - 2);
				newdp[1] = min(newdp[1], dp[2] + sum);

			}
			else{
				// 1 -> 0
				c1 = sz / 2;
				sum = 0;
				FOR(i, 0, c1-1, 1) sum += abs(G[i] - 1);
				FOR(i, c1, sz-1, 1) sum += abs(G[i] - 2);
				newdp[0] = min(newdp[0], dp[1] + sum);

				// 2 -> 0
				c1 = sz / 2 + 1;
				sum = 0;
				FOR(i, 0, c1-1, 1) sum += abs(G[i] - 1);
				FOR(i, c1, sz-1, 1) sum += abs(G[i] - 2);
				newdp[0] = min(newdp[0], dp[2] + sum);
			}
		}

		FOR(i, 0, 2, 1) dp[i] = newdp[i];
		/*
		FOR(i, 0, 2, 1){
			cerr<<"dp["<<i<<"] = ";
			if(dp[i] < LNF) cerr<<dp[i]<<" ";
			else cerr<<"- ";
		}
		
		cerr<<"G : ";
		for(int i : G){
			cerr<<i<<" ";
		}
		cerr<<endl;
		*/
	}
	
	res += dp[0];
	cout<<res<<'\n';
	
	return 0;

}

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