oj.uz

답안 #545882

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545882 2022-04-05T15:51:26 Z rainboy Printed Circuit Board (CEOI12_circuit) C++
85 / 100
 100 ms 6104 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <stdio.h>
#include <string.h>
 
#define N	200000
 
unsigned int X = 12345;
 
int rand_() {
	return (X *= 3) >> 1;
}
 
long long cross2(int x1, int y1, int x2, int y2) {
	return (long long) x1 * y2 - (long long) x2 * y1;
}
 
int xx[N], yy[N], ii[N * 2];
 
long long cross(int i, int j, int k) {
	return cross2(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}
 
int cmp(int h1, int h2) {
	long long c = cross2(xx[ii[h1]], yy[ii[h1]], xx[ii[h2]], yy[ii[h2]]);
 
	return c ? (c < 0 ? -1 : 1) : (h1 & 1) - (h2 & 1);
}
 
void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h_ = hh[l + rand_() % (r - l)], tmp;
 
		while (j < k) {
			int c = cmp(hh[j], h_);
 
			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}
 
int iq[1 + N], pq[N], cnt, x_, y_;
 
int lt(int i, int j) {
	int i0 = ii[i << 1 | 0], i1 = ii[i << 1 | 1], j0 = ii[j << 1 | 0], j1 = ii[j << 1 | 1];
 
	return cross(i0, i1, j0) >= 0 && cross(i0, i1, j1) >= 0 || cross(j0, j1, i0) <= 0 && cross(j0, j1, i1) <= 0;
}
 
int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}
 
void pq_up(int i) {
	int p, q, j;
 
	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}
 
void pq_dn(int i) {
	int p, q, j;
 
	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}
 
void pq_add(int i) {
	pq[i] = ++cnt, pq_up(i);
}
 
void pq_remove(int i) {
	if (pq[i]) {
		int j = iq[cnt--];
 
		if (j != i)
			pq[j] = pq[i], pq_up(j), pq_dn(j);
		pq[i] = 0;
	}
}
 
int main() {
	static int hh[N * 2];
	static char visible[N];
	int n, n_, g, h, h_, i;
 
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	n_ = 0;
	for (i = 0; i < n; i++) {
		long long c = cross2(xx[i], yy[i], xx[(i + 1) % n], yy[(i + 1) % n]);
 
		if (c < 0) {
			ii[i << 1 | 0] = i, ii[i << 1 | 1] = (i + 1) % n;
			hh[n_++] = i << 1 | 0, hh[n_++] = i << 1 | 1;
		} else if (c > 0) {
			ii[i << 1 | 0] = (i + 1) % n, ii[i << 1 | 1] = i;
			hh[n_++] = i << 1 | 0, hh[n_++] = i << 1 | 1;
		}
	}
	sort(hh, 0, n_);
	memset(visible, 1, n * sizeof *visible);
	for (h = 0; h < n_; h++) {
		h_ = hh[h];
		x_ = xx[ii[h_]], y_ = yy[ii[h_]];
		if ((h_ & 1) == 0)
			pq_add(h_ >> 1);
		else
			pq_remove(h_ >> 1);
		if (cnt) {
			i = iq[1];
			if (cross(ii[i << 1 | 0], ii[i << 1 | 1], ii[h_]) > 0)
				visible[ii[h_]] = 0;
		}
	}
	for (h = 0; h < n_; h = h_) {
		int h1, i_;
 
		h1 = hh[h], h_ = h, i_ = -1;
		while (h_ < n_ && cross2(xx[ii[h1]], yy[ii[h1]], xx[ii[hh[h_]]], yy[ii[hh[h_]]]) == 0) {
			i = ii[hh[h_++]];
			if (i_ == -1 || xx[i_] > xx[i])
				i_ = i;
		}
		for (g = h; g < h_; g++) {
			i = ii[hh[g]];
			if (i != i_)
				visible[i] = 0;
		}
	}
	cnt = 0;
	for (i = 0; i < n; i++)
		if (visible[i])
			cnt++;
	printf("%d\n", cnt);
	for (i = 0; i < n; i++)
		if (visible[i])
			printf("%d ", i + 1);
	printf("\n");
	return 0;
}

Compilation message

circuit.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
circuit.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
circuit.cpp: In function 'int lt(int, int)':
circuit.cpp:58:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |  return cross(i0, i1, j0) >= 0 && cross(i0, i1, j1) >= 0 || cross(j0, j1, i0) <= 0 && cross(j0, j1, i1) <= 0;
      |         ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'int main()':
circuit.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
circuit.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
85.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 6 ms 552 KB Output is correct
7 Correct 12 ms 780 KB Output is correct
8 Correct 5 ms 468 KB Output is correct
9 Correct 7 ms 588 KB Output is correct
10 Correct 6 ms 564 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 9 ms 852 KB Output is correct
13 Correct 22 ms 1108 KB Output is correct
14 Correct 20 ms 1404 KB Output is correct
15 Correct 26 ms 1620 KB Output is correct
16 Correct 54 ms 3024 KB Output is correct
17 Correct 69 ms 3156 KB Output is correct
18 Execution timed out 105 ms 5872 KB Time limit exceeded
19 Execution timed out 105 ms 5864 KB Time limit exceeded
20 Execution timed out 150 ms 6104 KB Time limit exceeded