oj.uz

답안 #55001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55001 2018-07-05T18:47:36 Z linkret Printed Circuit Board (CEOI12_circuit) C++14
75 / 100
 100 ms 27148 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define f first
#define s second

const int maxn = 1 << 18, inf = 1e9;

struct line {
	int a, b;
};

int n, k;
pair<pii, int> p[maxn];
pii org[maxn];
int arr[maxn];

int addlen[maxn], remlen[maxn];

line *add[maxn];
line *rem[maxn];

pair<pii, int> query[maxn];

vector<int> ans;

pii zero;

ll ccw(const pii &a, const pii &b, const pii &c) {
	return ll(a.f) * (b.s - c.s) + ll(b.f) * (c.s - a.s) + ll(c.f) * (a.s - b.s);
}

bool comp(pair<pii, int> a, pair<pii, int> b) {
	ll c = ccw(zero, a.f, b.f);

	if(c == 0)
		return a.s < b.s;
	return c > 0;
}

bool operator<(line x, line y) {
	const pii &xa = org[x.a];
	const pii &xb = org[x.b];

	const pii &ya = org[y.a];
	const pii &yb = org[y.b];

	if(xa == ya && xb == yb)
		return false;

	ll sum = ccw(xa, ya, xb) + ccw(xb, ya, yb);

	if(!sum) {
		if(xa.s == ya.s)
			return xa.f < ya.f;
		return xa.f < ya.f;
	}

	return sum > 0;
}

void sweep() {
	multiset<line> st;

	for(int t = 1; t <= k; t++) {
		for(int i = 0; i < addlen[t]; i++) {
			st.insert(add[t][i]);
		}
		
		if(!st.empty()) {
			line f = *st.begin();

			auto mnm = query[t];
			
			if(ccw(org[f.a], org[f.b], mnm.f) == 0) {
				ans.push_back(mnm.s);
			}
		}

		for(int i = 0; i < remlen[t]; i++) {
			auto it = st.find(rem[t][i]);
			st.erase(it);
		}
	}
}

void add_edge(int i, int j, int x, int y, bool b) {
	if(i < j) {
		if(b) {
			addlen[i]++;
			remlen[j]++;
		} else {
			add[i][addlen[i]++] = line{x, y};
			rem[j][remlen[j]++] = line{x, y};
		}
	} else {
		if(b) {
			addlen[j]++;
			remlen[i]++;
		} else {
			add[j][addlen[j]++] = line{y, x};
			rem[i][remlen[i]++] = line{y, x};
		}
	}
}

void compress() {
	sort(p, p + n, comp);

	for(int i = 0; i <= n; i++) {
		query[i] = {{inf, inf}, inf};
	}

	for(int i = 0; i < n; i++) {
		if(i == 0 || ccw(pii(0, 0), p[i].f, p[i - 1].f))
			k++;
		arr[p[i].s] = k;
		query[k] = min(query[k], p[i]);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;

	for(int i = 0; i < n; i++) {
		pii tmp;
		cin >> tmp.f >> tmp.s;
		
		p[i].f = tmp;
		p[i].s = i;

		org[i] = p[i].f;
	}

	compress();

	for(int i = 0; i < n - 1; i++) 
		add_edge(arr[i], arr[i + 1], i, i + 1, true);
	add_edge(arr[n - 1], arr[0], n - 1, 0, true);

	for(int i = 1; i <= k; i++) {
		add[i] = new line[addlen[i]];
		rem[i] = new line[remlen[i]];
		
		addlen[i] = 0;
		remlen[i] = 0;
	}

	for(int i = 0; i < n - 1; i++) 
		add_edge(arr[i], arr[i + 1], i, i + 1, false);
	add_edge(arr[n - 1], arr[0], n - 1, 0, false);

	sweep();

	cout << ans.size() << endl;

	sort(ans.begin(), ans.end());

	for(int i : ans) {
		cout << i + 1 << " ";
	}

	cout << endl;

	return 0;
}

Subtask #1
75.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 616 KB Output is correct
3 Correct 4 ms 928 KB Output is correct
4 Correct 5 ms 1004 KB Output is correct
5 Correct 12 ms 1800 KB Output is correct
6 Correct 16 ms 1916 KB Output is correct
7 Correct 36 ms 3156 KB Output is correct
8 Correct 9 ms 3156 KB Output is correct
9 Correct 11 ms 3156 KB Output is correct
10 Correct 14 ms 3156 KB Output is correct
11 Correct 19 ms 3156 KB Output is correct
12 Correct 21 ms 3216 KB Output is correct
13 Correct 54 ms 4576 KB Output is correct
14 Correct 34 ms 5516 KB Output is correct
15 Correct 49 ms 6796 KB Output is correct
16 Execution timed out 127 ms 12904 KB Time limit exceeded
17 Execution timed out 197 ms 13872 KB Time limit exceeded
18 Execution timed out 234 ms 25164 KB Time limit exceeded
19 Execution timed out 173 ms 25164 KB Time limit exceeded
20 Execution timed out 425 ms 27148 KB Time limit exceeded