oj.uz

Submission #99057

# Submission time Handle Problem Language Result Execution time Memory
99057 2019-02-28T08:35:37 Z 조승현(#2855, ainta) Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 2 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];
		if (i == e && s1 + s2 == 1) {
			C[i][0] = s1;
			C[i][1] = s2;
			continue;
		}
		if (s1 == 0) {
			C[i][0] = C[i][1] = 1;
			s2 -= 2;
			res++;
		}
		if (s2 == 0) {
			C[i][0] = C[i][1] = 1;
			s1 -= 2;
			res++;
		}
		else {
			C[i][0] = C[i][1] = 1;
			s1--, s2--;
		}
	}
}
void Go(int b, int e, int pv) {
	int i;
	int s1 = 0, s2 = 0;
	for (i = b; i < pv; i++) {
		s1 += C[i][0];
		s2 += C[i][1];
		if (s1 > i-b+1) {
			int t = s1 - (i - b + 1);
			C[i][0] -= t;
			C[i][1] += t;
			res += t;
			s1 -= t;
			s2 += t;
		}
		if(s2 > i-b+1){
			int t = s2 - (i - b + 1);
			C[i][0] += t;
			C[i][1] -= t;
			res += t;
			s1 += t;
			s2 -= t;
		}
	}
	s1 = pv - b - s1;
	s2 = pv - b - s2;
	if (s1 > C[pv][0]) {
		int t = s1 - C[pv][0];
		C[pv][0] += t;
		C[pv][1] -= t;
		res += t;
	}
	if (s2 > C[pv][1]) {
		int t = s2 - C[pv][1];
		C[pv][0] -= t;
		C[pv][1] += t;
		res += t;
	}
	C[pv][0] -= s1;
	C[pv][1] -= s2;
	for (i = b; i < pv; i++) {
		C[i][0] = C[i][1] = 1;
	}
	Right(pv, e);
}
int main() {
	//freopen("input.txt", "r", stdin);
	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:85: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:87: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 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Incorrect 2 ms 384 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Incorrect 2 ms 384 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Incorrect 2 ms 384 KB Output isn't correct
16 Halted 0 ms 0 KB -