oj.uz

Submission #537120

# Submission time Handle Problem Language Result Execution time Memory
537120 2022-03-14T15:05:36 Z rainboy 별자리 2 (JOI14_constellation2) C
100 / 100
 1758 ms 464 KB 
#include <stdio.h>
#include <string.h>

#define N	3000

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int xx[N], yy[N], cc[N];

long long cross(int i, int j, int k) {
	return (long long) (xx[j] - xx[i]) * (yy[k] - yy[i]) - (long long) (xx[k] - xx[i]) * (yy[j] - yy[i]);
}

int o;

int compare(int i, int j) {
	int sgni = xx[i] < xx[o] || xx[i] == xx[o] && yy[i] < yy[o] ? -1 : 1;
	int sgnj = xx[j] < xx[o] || xx[j] == xx[o] && yy[j] < yy[o] ? -1 : 1;
	long long c;

	if (sgni != sgnj)
		return sgni - sgnj;
	c = cross(o, i, j);
	return c == 0 ? 0 : (c < 0 ? -1 : 1);
}

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int main() {
	static int jj[N];
	static int kk[3], kk_[3];
	int n, m, i, j, j_, j1, j2, a, b;
	long long ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d%d%d", &xx[i], &yy[i], &cc[i]);
		kk_[cc[i]]++;
	}
	ans = 0;
	for (i = 0; i < n; i++) {
		m = 0;
		for (j = 0; j < n; j++)
			if (j != i)
				jj[m++] = j;
		o = i, sort(jj, 0, m);
		memset(kk, 0, sizeof kk);
		for (j = 0, j_ = 0; j < m; j++) {
			j1 = jj[j];
			while (j_ < j + m && cross(o, j1, j2 = jj[j_ % m]) <= 0)
				kk[cc[j2]]++, j_++;
			a = cc[i], b = cc[j1];
			kk[b]--;
			if (i < j1) {
				kk_[a]--, kk_[b]--;
				ans += (long long) kk[(a + 1) % 3] * kk[(a + 2) % 3] * (kk_[(b + 1) % 3] - kk[(b + 1) % 3]) * (kk_[(b + 2) % 3] - kk[(b + 2) % 3]);
				kk_[a]++, kk_[b]++;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

constellation2.c: In function 'compare':
constellation2.c:21:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   21 |  int sgni = xx[i] < xx[o] || xx[i] == xx[o] && yy[i] < yy[o] ? -1 : 1;
      |                              ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
constellation2.c:22:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   22 |  int sgnj = xx[j] < xx[o] || xx[j] == xx[o] && yy[j] < yy[o] ? -1 : 1;
      |                              ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
constellation2.c: In function 'main':
constellation2.c:59:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
constellation2.c:61:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d%d%d", &xx[i], &yy[i], &cc[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 4 ms 304 KB Output is correct
5 Correct 7 ms 300 KB Output is correct
6 Correct 18 ms 212 KB Output is correct
7 Correct 15 ms 300 KB Output is correct
8 Correct 15 ms 300 KB Output is correct
9 Correct 14 ms 212 KB Output is correct
10 Correct 10 ms 212 KB Output is correct
11 Correct 14 ms 300 KB Output is correct
12 Correct 14 ms 212 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 284 KB Output is correct
2 Correct 152 ms 212 KB Output is correct
3 Correct 174 ms 292 KB Output is correct
4 Correct 168 ms 296 KB Output is correct
5 Correct 394 ms 296 KB Output is correct
6 Correct 768 ms 316 KB Output is correct
7 Correct 1172 ms 344 KB Output is correct
8 Correct 1751 ms 356 KB Output is correct
9 Correct 1758 ms 352 KB Output is correct
10 Correct 1695 ms 352 KB Output is correct
11 Correct 1685 ms 356 KB Output is correct
12 Correct 1702 ms 364 KB Output is correct
13 Correct 1695 ms 352 KB Output is correct
14 Correct 1750 ms 464 KB Output is correct
15 Correct 1678 ms 360 KB Output is correct
16 Correct 1691 ms 364 KB Output is correct