Submission #1294237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294237		Jawad_Akbar_JJ	Coin Collecting (JOI19_ho_t4)	C++20	0 / 100	1 ms	576 KiB

joi2019_ho_t4

#include <iostream>
#include <set>

using namespace std;
#define int long long
int a[3][1<<17], Ans;

signed main(){
	int n;
	cin>>n;

	for (int i=1, x, y, X, Y;i<=n + n;i++){
		cin>>x>>y;

		Y = 1 + (y >= 2);
		X = max(1LL, min(x, n));

		a[Y][X]++;
		Ans += abs(x - X) + abs(y - Y);
		// cout<<X<<" "<<Y<<endl;
	}
	a[1][n+2] = a[2][n+2] = n * 10;

	set<int> f, s;
	for (int i=1;i<=n + 2;i++){
		if (a[1][i] > 1)
			f.insert(i);
		if (a[2][i] > 1)
			s.insert(i);
	}

	for (int i=1;i<=n;i++){

		// cout<<Ans<<endl;
		// for (int j=1;j<=n + 5;j++)
		// 	cout<<a[1][j]<<' ';
		// cout<<'\n';
		// for (int j=1;j<=n + 5;j++)
		// 	cout<<a[2][j]<<' ';
		// cout<<'\n';
		// cout<<endl<<endl;

		int f1 = *begin(f), f2 = *begin(s);
		f.erase(f1);
		s.erase(f2);

		if (a[1][i] == 0 and a[2][i] == 0){
			if (f1 < f2){
				a[1][f1]--, a[1][i]++;
				Ans += f1 - i;
				if (a[1][f1] == 1)
					f1 = *begin(f), f.erase(f1);
				
				if (f1 + 1 <= f2)
					a[1][f1]--, a[2][i]++, Ans += f1 - i + 1;
				else
					a[2][f2]--, a[2][i]++, Ans += f2 - i;
			}
			else if (f1 == f2){
				a[1][f1]--, a[2][f2]--, a[1][i]++, a[2][i]++;
				Ans += f1 + f2 - i - i;
			}
			else{
				a[2][f2]--, a[2][i]++;
				Ans += f2 - i;
				if (a[2][f2] == 1)
					f2 = *begin(s), s.erase(f2);
				
				if (f2 + 1 <= f1)
					a[2][f2]--, a[1][i]++, Ans += f2 - i + 1;
				else
					a[1][f1]--, a[1][i]++, Ans += f1 - i;
			}
		}
		else if (a[1][i] == 0){
			if (f2 + 1 <= f1)
				a[2][f2]--, a[1][i]++, Ans += f2 - i + 1;
			else
				a[1][f1]--, a[1][i]++, Ans += f1 - i;
		}
		else if (a[2][i] == 0){
			if (f1 + 1 <= f2)
				a[1][f1]--, a[2][i]++, Ans += f1 - i + 1;
			else
				a[2][f2]--, a[2][i]++, Ans += f2 - i;
		}

		if (a[1][i] > 1)
			Ans += a[1][i] - 1, a[1][i+1] += a[1][i] - 1;
		if (a[2][i] > 1)
			Ans += a[2][i] - 1, a[2][i+1] += a[2][i] - 1;
		a[1][i] = 1, a[2][i] = 1;

		if (a[1][f1] > 1)
			f.insert(f1);
		if (a[2][f2] > 1)
			s.insert(f2);
		
		f.erase(i), s.erase(i);

		if (a[1][i + 1] > 1)
			f.insert(i + 1);
		if (a[2][i + 1] > 1)
			s.insert(i + 1);
	}

	cout<<Ans<<'\n';
}

/*
3
0 0
0 4
4 0
2 1
2 5
-1 1


*/

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