oj.uz

Submission #54981

# Submission time Handle Problem Language Result Execution time Memory
54981 2018-07-05T15:51:38 Z linkret Printed Circuit Board (CEOI12_circuit) C++14
75 / 100
 100 ms 29484 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);
		}
		
		line f = *st.begin();

		sort(query[t].begin(), query[t].end());

		for(const pair<pii, int> &i : query[t]) {
			if(ccw(org[f.a], org[f.b], i.f) == 0) {
				ans.push_back(i.s);
			}

			break;
		}

		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 9592 KB Output is correct
2 Correct 10 ms 9832 KB Output is correct
3 Correct 11 ms 10036 KB Output is correct
4 Correct 12 ms 10208 KB Output is correct
5 Correct 21 ms 10768 KB Output is correct
6 Correct 25 ms 10804 KB Output is correct
7 Correct 46 ms 11992 KB Output is correct
8 Correct 24 ms 11992 KB Output is correct
9 Correct 19 ms 11992 KB Output is correct
10 Correct 25 ms 11992 KB Output is correct
11 Correct 23 ms 11992 KB Output is correct
12 Correct 28 ms 11992 KB Output is correct
13 Correct 52 ms 13036 KB Output is correct
14 Correct 47 ms 13932 KB Output is correct
15 Correct 61 ms 14956 KB Output is correct
16 Execution timed out 105 ms 20076 KB Time limit exceeded
17 Execution timed out 180 ms 20580 KB Time limit exceeded
18 Runtime error 57 ms 27168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 67 ms 29484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 71 ms 29484 KB Execution killed with signal 11 (could be triggered by violating memory limits)