oj.uz

Submission #54988

# Submission time Handle Problem Language Result Execution time Memory
54988 2018-07-05T16:46:20 Z linkret Printed Circuit Board (CEOI12_circuit) C++14
10 / 100
 100 ms 33792 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, 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) {
	// 	swap(i, j);
	// 	swap(x, y);
	// }


	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][addlen[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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 3 ms 904 KB Output isn't correct
3 Correct 7 ms 1368 KB Output is correct
4 Correct 5 ms 1368 KB Output is correct
5 Runtime error 13 ms 3732 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 14 ms 3764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 23 ms 6280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 15 ms 6280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 14 ms 6280 KB Output isn't correct
10 Runtime error 14 ms 6280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 15 ms 6280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 28 ms 7712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 52 ms 9604 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 31 ms 10704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 74 ms 18124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 158 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 107 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 313 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 219 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 36 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)