oj.uz

Submission #99028

# Submission time Handle Problem Language Result Execution time Memory
99028 2019-02-28T06:14:49 Z 조승현(#2855, ainta) Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 8 ms 5120 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 201000
using namespace std;
long long res;
struct point {
	int x, y;
	bool operator<(const point &p)const {
		return x != p.x ? x < p.x : y < p.y;
	}
}w[N_];
long long D[N_][3], INF = 3e18;
int n, chk[N_], cnt, MM;
vector<int>G[N_];
void Go(int x, int y, int t) {
	res += abs(w[t].x - x);
	res += abs(w[t].y - y);
}
int main() {
	int i, j;
	scanf("%d", &n);
	MM = n;
	n *= 2;
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &w[i].x, &w[i].y);
		if (w[i].x < 1) {
			res += 1 - w[i].x;
			w[i].x = 1;
		}
		if (w[i].x > MM) {
			res += w[i].x - MM;
			w[i].x = MM;
		}
		if (w[i].y < 1) {
			res += 1 - w[i].y;
			w[i].y = 1;
		}
		if (w[i].y > 2) {
			res += w[i].y - 2;
			w[i].y = 2;
		}
	}
	sort(w + 1, w + n + 1);
	for (i = 1; i <= n; i++) {
		G[w[i].x].push_back(i);
	}
	for (i = 0; i <= n; i++)D[i][0] = D[i][1] = D[i][2] = INF + 100;
	int ck = 0;
	for (i = 1; i <= n; i++) {
		if (G[i].empty()) {
			for (j = 0; j < 3; j++)D[i][j] = D[i - 1][j];
			continue;
		}
		int sz = G[i].size();
		if (ck == 0) {
			for (j = 0; j < sz / 2; j++) {
				cnt++;
				Go(cnt, 1, G[i][j]);
				Go(cnt, 2, G[i][sz-j-1]);
			}
			if (sz % 2 == 1) {
				cnt++;
				int t = G[i][sz / 2];
				if (w[t].y <= 1) {
					Go(cnt, 1, t);
					ck = 1;
				}
				else {
					Go(cnt, 2, t);
					ck = 2;
				}
			}
		}
		else if (ck == 1) {
			ck = 0;
			Go(cnt, 2, G[i][sz - 1]);
			for (j = 0; j < (sz - 1) / 2; j++) {
				cnt++;
				Go(cnt, 1, G[i][j]);
				Go(cnt, 2, G[i][sz - j - 2]);
			}
			if (sz % 2 == 0) {
				cnt++;
				int t = G[i][sz / 2 - 1];
				if (w[t].y <= 1) {
					Go(cnt, 1, t);
					ck = 1;
				}
				else {
					Go(cnt, 2, t);
					ck = 2;
				}
			}
		}
		else if (ck == 2) {
			ck = 0;
			Go(cnt, 1, G[i][0]);
			for (j = 0; j < (sz - 1) / 2; j++) {
				cnt++;
				Go(cnt, 1, G[i][j + 1]);
				Go(cnt, 2, G[i][sz - j - 1]);
			}
			if (sz % 2 == 0) {
				cnt++;
				int t = G[i][sz / 2];
				if (w[t].y <= 1) {
					Go(cnt, 1, t);
					ck = 1;
				}
				else {
					Go(cnt, 2, t);
					ck = 2;
				}
			}
		}
	}
	printf("%lld\n", res);
}

Compilation message

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
joi2019_ho_t4.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &w[i].x, &w[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 29.0

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

Subtask #3
0 / 63.0

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