Submission #220746

#	Time	Username	Problem	Language	Result	Execution time	Memory
220746		DmitryGrigorev	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	69 ms	6008 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
#define int long long
#define db long double
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

using namespace std;

int sum[100007][3];

vector<pair<int, int> > calc(vector<pair<int, int> > v, int &ans) {
	vector<pair<int, int> > res;
	for (int i = 0; i < v.size(); ++i) {
		if (res.size() && res.back().second%2 != v[i].second%2) {
			ans += abs(res.back().first - v[i].first) + abs(res.back().second/2 - v[i].first/2) ;
			res.pop_back();
		}
		else res.push_back(v[i]);
	}

	return res;
}

main(){
#ifdef LOCAL
	freopen("N_input.txt", "r", stdin);
	//freopen("N_output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	int ans = 0;

	for (int i = 0; i < 2*n; ++i) {
		int x, y;
		cin >> x >> y;

		int z, t;
		if (x <= 0) z = 1;
		else if (x > n) z = n;
		else z = x;

		if (y <= 1) t = 1;
		else t = 2;

		ans += abs(x-z) + abs(y-t);

		sum[z][t]++;
	}

	int wa = 0, wb = 0;
	for (int i = 0; i < n; ++i) {
		//cout << wa << " " << wb << endl;
		int A = sum[i+1][1] - 1, B = sum[i+1][2] - 1;

		//cout << "== " << A << " " << B << endl;

		while (A < 0 && wa > 0) {
			A++, wa--;
		}

		while (A > 0 && wa < 0) {
			A--, wa++;
		}

		while (B < 0 && wb > 0) {
			B++, wb--;
		}

		while (B > 0 && wb < 0) {
			B--, wb++;
		}

		while (A > 0 && B < 0) {
			ans++, A--, B++;
		}

		while (A < 0 && B > 0) {
			ans++, A++, B--;
		}


		while (A < 0 && wb > 0) {
			A++, wb--;
			ans++;
		}

		while (A > 0 && wb < 0) {
			A--, wb++;
			ans++;
		}

		while (B < 0 && wa > 0) {
			B++, wa--;
			ans++;
		}

		while (B > 0 && wa < 0) {
			B--, wa++;
			ans++;
		}

		wa+=A, wb+=B;
		ans += abs(wa) + abs(wb);





	}
	cout << ans;

}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'std::vector<std::pair<long long int, long long int> > calc(std::vector<std::pair<long long int, long long int> >, long long int&)':
joi2019_ho_t4.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); ++i) {
                  ~~^~~~~~~~~~
joi2019_ho_t4.cpp: At global scope:
joi2019_ho_t4.cpp:27:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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