oj.uz

Submission #380588

# Submission time Handle Problem Language Result Execution time Memory
380588 2021-03-22T12:06:25 Z peijar Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 1 ms 364 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -