oj.uz

Submission #220744

# Submission time Handle Problem Language Result Execution time Memory
220744 2020-04-08T14:23:19 Z DmitryGrigorev Coin Collecting (JOI19_ho_t4) C++14
0 / 100
 5 ms 384 KB 
#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 != v[i].second) {
			ans += abs(res.back().first - v[i].first);
			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]++;
	}

	vector<pair<int, int> > a, b;
	for (int i = 0; i < n; ++i) {
		int W = sum[i+1][1];
		while (W > 1) {
			a.push_back({i, 0});
			W--;
		}
		while (W < 1) {
			a.push_back({i, 1});
			W++;
		}

		W = sum[i+1][2];
		while (W > 1) {
			b.push_back({i, 0});
			W--;
		}
		while (W < 1) {
			b.push_back({i, 1});
			W++;
		}
	}

	a = calc(a, ans);
	b = calc(b, ans);

	ans += a.size();
	for (int i = 0; i < b.size(); ++i) a.push_back(b[i]);

	sort(all(a));

	calc(a, ans);

	cout << ans;

}

Compilation message

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(){
      ^
joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < b.size(); ++i) a.push_back(b[i]);
                  ~~^~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 29.0

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

Subtask #3
0 / 63.0

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