oj.uz

Submission #99044

# Submission time Handle Problem Language Result Execution time Memory
99044 2019-02-28T07:30:00 Z 조승현(#2855, ainta) Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 3 ms 384 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 201000
using namespace std;
long long res;
struct point {
	int x, y;
}w[N_];
int C[N_][2], n, S[N_], T[N_];
void Right(int b, int e) {
	int i;
	int s1 = 0, s2 = 0;
	for (i = b; i <= e; i++) {
		s1 += C[i][0];
		s2 += C[i][1];
	}
	for (i = b; i < e; i++) {
		C[i][0] = C[i][1] = 1;
	}
	if ((s1 + s2) % 2 == 1) {
		if (s1 > s2) {
			C[e][0] = 1;
			C[e][1] = 0;
		}
		else {
			C[e][0] = 1;
			C[e][1] = 0;
		}
	}
	else {
		C[e][0] = C[e][1] = 1;
	}
	res += abs((s1 - s2) / 2);
}
void Go(int b, int e, int pv) {
	int i;
	int s1 = 0, s2 = 0;
	for (i = b; i <= e; i++) {
		s1 += C[i][0];
		s2 += C[i][1];
	}
	for (i = b; i < e; i++) {
		C[i][0] = C[i][1] = 1;
	}
	if ((s1 + s2) % 2 == 1) {
		if (s1 > s2) {
			C[e][0] = 1;
			C[e][1] = 0;
		}
		else {
			C[e][0] = 1;
			C[e][1] = 0;
		}
	}
	else {
		C[e][0] = C[e][1] = 1;
	}
	res += abs((s1 - s2) / 2);
}
int main() {
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n*2; 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 > n) {
			res += w[i].x - n;
			w[i].x = n;
		}
		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;
		}
		C[w[i].x][w[i].y - 1]++;
	}
	for (i = 1; i <= n; i++) {
		S[i] = S[i - 1] + C[i][0] + C[i][1];
		T[i] = S[i] - i * 2;
	}
	for (i = 1; i < n; i++) {
		res += abs(T[i]);
	}
	for (i = 1; i < n; i++) {
		if (T[i] == 0)continue;
		if (T[i] > 0) {
			for (j = i; j < n; j++)if (T[j] <= 0)break;
			Right(i, j);
			i = j - 1;
			continue;
		}
		else {
			for (j = i; j < n; j++)if (T[j] >= 0)break;
			int pv = j;
			if (T[pv] > 0) {
				for (j = pv; j < n; j++)if (T[j] <= 0)break;
				Go(i, j, pv);
				i = j - 1;
			}
			else {
				Go(i, pv, pv);
				i = pv - 1;
			}
		}
	}
	for (i = 1; i <= n; i++) {
		res += abs(C[i][0] - C[i][1]) / 2;
	}
	printf("%lld\n", res);
}

Compilation message

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:63: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:65: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 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 284 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Incorrect 1 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 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 284 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Incorrect 1 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 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 284 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Incorrect 1 ms 384 KB Output isn't correct
15 Halted 0 ms 0 KB -