oj.uz

Submission #221663

# Submission time Handle Problem Language Result Execution time Memory
221663 2020-04-10T21:31:39 Z hanagasumi Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 5 ms 384 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll

using namespace std;
typedef long long ll;



signed main() {
	#ifdef PC
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	vector<vector<int>> have(n, vector<int> (2, 0));
	int ans = 0;
	for (int i = 0; i < 2 * n; i++) {
		int x, y;
		cin >> x >> y;
		if(y < 1) 
			ans += (1 - y), y = 1;
		if(y > 2) 
			ans += (y - 2), y = 2;
		if(x < 1) 
			ans += (1 - x), x = 1;
		if(x > n) 
			ans += (x - n), x = n;
		have[x - 1][y - 1]++;
	}

	// for (int j = 0; j < 2; j++) {
	// 	for (int i = 0; i < n; i++) {
	// 		cout << have[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

	// cout << ans << endl;
	// ans = 0;
	int top = 0, down = 0;
	for (int i = 0; i < n; i++) {
		top += have[i][0], down += have[i][1];
		// cout << i << " " << top << " " << down << " " << ans << endl;
		have[i][0] = 0, have[i][1] = 0;
		if(top > 0) {
			have[i][0] = 1;
			top--;
		}
		if(down > 0) {
			have[i][1] = 1;
			down--;
		}
		if(have[i][0] == 0 && down > 0) {
			have[i][0] = 1;
			ans++;
			down--;
		}
		if(have[i][1] == 0 && top > 0) {
			have[i][1] = 1;
			ans++;
			top--;
		}
		for (int j = i + 1; j <= n; j++) {
			if(j < n && have[i][0] == 0 && have[j][0] > 1) {
				have[i][0] = 1;
				// cout << "(" << i << ", " << 0 << ") -> (" << j << ", " << 0 << ")" << endl;
				ans += (j - i);
				have[j][0]--;
			}
			if(j < n && have[i][1] == 0 && have[j][1] > 1) {
				have[i][1] = 1;
				// cout << "(" << i << ", " << 1 << ") -> (" << j << ", " << 1 << ")" << endl;
				ans += (j - i);
				have[j][1]--;
			}
			if(have[i][0] == 0 && have[j - 1][1] > 1) {
				have[i][0] = 1;
				// cout << "(" << i << ", " << 0 << ") -> (" << j - 1 << ", " << 1 << ")" << endl;
				ans += (j - i);
				have[j - 1][1]--;
			}
			if(have[i][1] == 0 && have[j - 1][0] > 1) {
				have[i][1] = 1;
				// cout << "(" << i << ", " << 1 << ") -> (" << j - 1 << ", " << 0 << ")" << endl;
				ans += (j - i);
				have[j - 1][0]--;
			}
		}
		if(i == n - 1) 
			break;
		ans += top + down;
		// cout << have[i][0] << " " << have[i][1] << endl;
	}
		
	cout << ans << '\n';
}

/*
if(have[i][0] == 0) {

			for (int j = i + 1; j < n; j++) {
				if(have[j][0] > 1) {
					cout << "X  " << i << " " << j << endl; 
					have[j][0]--;
					ans += (j - i);
					have[i][0] = 1;
					break;
				}
				if(j == i + 1 && down != 0) {
					down--;
					ans += 1;
					have[i][0] = 1;
					break;
				}
				if(have[j - 1][1] > 1) {
					have[j - 1][1]--;
					ans += (j - i);
					have[i][0] = 1;
					break;
				}
			}
			if(have[i][0] == 0) {
				ans += (n - i);
				have[i][0] = 1;
				if(i != n - 1)
					have[n - 1][1]--;
			}
			
		}
		if(have[i][1] == 0) {
			for (int j = i + 1; j < n; j++) {
				if(have[j][1] > 1) {
					have[j][1]--;
					ans += (j - i);
					have[i][1] = 1;
					break;
				}
				if(j == i + 1 && top != 0) {
					top--;
					ans += 1;
					have[i][1] = 1;
					break;
				}
				if(have[j - 1][0] > 1) {
					have[j - 1][0]--;
					ans += (j - i);
					have[i][1] = 1;
					break;
				}
			}
			if(have[i][1] == 0) {
				have[i][1] = 1;
				ans += (n - i);
				if(i != n - 1)
					have[n - 1][0]--;
			}
		}
		if(i == n - 1) 
			break;
		ans += top + down;
	}
	*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Incorrect 5 ms 384 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Incorrect 5 ms 384 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Incorrect 5 ms 384 KB Output isn't correct
15 Halted 0 ms 0 KB -