Submission #380588

#	Time	Username	Problem	Language	Result	Execution time	Memory
380588		peijar	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	364 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 2e18;

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbPieces;
	cin >> nbPieces;
	nbPieces *= 2;

	map<int, vector<int>> pieces;
	for (int iPiece = 0; iPiece < nbPieces; ++iPiece) 
	{
		int x, y;
		cin >> x >> y;
		pieces[x].push_back(y);
	}

	int last1(0), last2(0);

	int nbVus(0);
	for (auto [x, ys] : pieces)
	{
		sort(ys.begin(), ys.end());
		int nbY = ys.size();
		int totCostX(0);
		for (int i(0); i < nbY; ++i)
			totCostX += abs((nbVus + i) / 2 + 1 - x);
		int nxt1 = INF, nxt2 = INF;
		// On utilise last1 : 
		int cost = totCostX + last1;
		int mod2 = nbVus % 2;
		if (mod2)
			cost += abs(ys.back() - 2);
		// On met dernier en 1 :
		int cost1 = cost;
		nbY -= mod2;
		for (int i(0); i < (nbY+1)/2; ++i)
			cost1 += abs(ys[i] - 1);
		for (int i((nbY+1)/2); i < nbY; ++i)
			cost1 += abs(ys[i] - 2);
		nxt1 = min(nxt1, cost1);
		// On met dernier en 2 :
		int cost2 = cost;
		for (int i(0); i < nbY/2; ++i)
			cost2 += abs(ys[i] - 1);
		for (int i(nbY/2); i < nbY; ++i)
			cost2 += abs(ys[i] - 2);
		nxt2 = min(nxt2, cost2);

		// On utilise last2 :
		cost = totCostX + last2;
		if (mod2)
			cost += abs(ys[0] - 1);
		// On met dernier en 1
		cost1 = cost;
		for (int i(0); i < (nbY+1)/2; ++i)
			cost1 += abs(ys[i+mod2] - 1);
		for (int i((nbY+1)/2); i < nbY; ++i)
			cost1 += abs(ys[i+mod2] - 2);
		nxt1 = min(nxt1, cost1);
		// On met dernier en 2
		cost2 = cost;
		for (int i(0); i < (nbY)/2; ++i)
			cost2 += abs(ys[i+mod2] - 1);
		for (int i(nbY/2); i < nbY; ++i)
			cost2 += abs(ys[i+mod2] - 2);
		nxt2 = min(nxt2, cost2);
		last1 = nxt1, last2 = nxt2;
		nbY += mod2;
		//cout << last1 << ' ' << last2 << endl;
		nbVus += nbY;
	}
	cout << min(last1, last2) << endl;
}

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