oj.uz

Submission #54982

# Submission time Handle Problem Language Result Execution time Memory
54982 2018-07-05T15:58:14 Z linkret Printed Circuit Board (CEOI12_circuit) C++14
75 / 100
 100 ms 29544 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 << 17;

struct line {
	int a, b;
};

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

vector<line> add[maxn];
vector<line> rem[maxn];
vector<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) {
// 	return org[x.a] == org[y.a] && org[x.b] == org[y.b];
// }

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(const line &i : add[t]) {
			st.insert(i);
		}
		
		if(!st.empty()) {
			line f = *st.begin();

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

		for(const line &i : rem[t]) {
			auto it = st.find(i);
			st.erase(it);
		}
	}
}

void add_edge(int i, int j, int x, int y) {
	if(i < j) {
		add[i].push_back(line{x, y});
		rem[j].push_back(line{x, y});
	} else {
		add[j].push_back(line{y, x});
		rem[i].push_back(line{y, x});
	}
}

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

	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].push_back(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);
	add_edge(arr[n - 1], arr[0], n - 1, 0);

	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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9596 KB Output is correct
2 Correct 11 ms 9700 KB Output is correct
3 Correct 15 ms 10164 KB Output is correct
4 Correct 13 ms 10256 KB Output is correct
5 Correct 21 ms 10768 KB Output is correct
6 Correct 26 ms 10896 KB Output is correct
7 Correct 45 ms 11924 KB Output is correct
8 Correct 29 ms 11924 KB Output is correct
9 Correct 21 ms 11924 KB Output is correct
10 Correct 25 ms 11924 KB Output is correct
11 Correct 23 ms 11924 KB Output is correct
12 Correct 36 ms 11924 KB Output is correct
13 Correct 54 ms 13040 KB Output is correct
14 Correct 75 ms 13936 KB Output is correct
15 Correct 71 ms 15104 KB Output is correct
16 Execution timed out 114 ms 20084 KB Time limit exceeded
17 Execution timed out 186 ms 20480 KB Time limit exceeded
18 Runtime error 59 ms 27176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 79 ms 29544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 63 ms 29544 KB Execution killed with signal 11 (could be triggered by violating memory limits)