oj.uz

답안 #99039

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
99039 2019-02-28T07:14:26 Z 조승현(#2855, ainta) Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 2 ms 256 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];
	}
	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;
		}
	}
	res += abs((s1 - s2) / 2);
}
void Left(int b, int e) {

	int s1 = 0, s2 = 0, i;
	for (i = b; i < e; i++) {
		s1 += C[i][0];
		s2 += C[i][1];
	}
	int c = (e - b) * 2 - (s1 + s2);
	int c1 = e - b - s1;
	int c2 = e - b - s2;
	if (c1 < 0) {
		c2 += c1;
		c1 = 0;
	}
	if (c2 < 0) {
		c1 += c2;
		c2 = 0;
	}
	if (C[e][0] < c1) {
		c2 += c1 - C[e][0];
		c1 = C[e][0];
	}
	if (C[e][1] < c2) {
		c1 += c2 - C[e][1];
		c2 = C[e][1];
	}
	C[e][0] -= c1;
	C[e][1] -= c2;
	s1 += c1;
	s2 += c2;
	res += abs((s1 - s2) / 2);
	if (!T[e]) {
		res += abs((C[e][0] - C[e][1]) / 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;
		}
		else {
			for (j = i; j < n; j++)if (T[j] >= 0)break;
			Left(i, j);
			i = j - 1;
		}
	}
	printf("%lld\n", res);
}

Compilation message

joi2019_ho_t4.cpp: In function 'void Left(int, int)':
joi2019_ho_t4.cpp:37:6: warning: unused variable 'c' [-Wunused-variable]
  int c = (e - b) * 2 - (s1 + s2);
      ^
joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:67: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:69: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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -