oj.uz

Submission #119361

# Submission time Handle Problem Language Result Execution time Memory
119361 2019-06-21T05:43:24 Z tmwilliamlin168 Printed Circuit Board (CEOI12_circuit) C++14
50 / 100
 100 ms 17660 KB 
#include <bits/stdc++.h>
using namespace std;

int in() {
	char c=0;
	while(c<'0'||c>'9')
		c=getchar_unlocked();
	int r=0;
	while(c>='0'&&c<='9') {
		r=r*10+c-'0';
		c=getchar_unlocked();
	}
	return r;
}

void out(int x) {
	int c=0, r=0;
	for(; x%10==0; ++c, x/=10);
	for(; x; x/=10)
		r=r*10+x%10;
	for(; r; r/=10)
		putchar_unlocked(r%10+'0');
	while(c--)
		putchar_unlocked('0');
}

const int mxN=2e5;
int n, b[mxN], c[mxN+1], e1[mxN], e2[mxN], a1, ft[mxN+1], tp[mxN];
long long x[mxN+1], y[mxN+1];
vector<int> r[mxN];
bool ans[mxN];

bool cw(int a, int b, int c) {
	return (y[c]-y[a])*(x[b]-x[a])<(y[b]-y[a])*(x[c]-x[a]);
}

bool pcmp(const int &i, const int &j) {
	return y[i]*x[j]<y[j]*x[i];
}

bool scmp(const int &i, const int &j) {
	if(i<0)
		return 0;
	if(j<0)
		return 1;
	if(e1[i]==e1[j])
		return c[e2[i]]<c[e2[j]]?!cw(e1[j], e2[j], e2[i]):cw(e1[i], e2[i], e2[j]);
	return c[e1[i]]<c[e1[j]]?cw(e1[i], e2[i], e1[j]):!cw(e1[j], e2[j], e1[i]);
}

void upd(int i, int x) {
	for(++i; i<=n; i+=i&-i)
		ft[i]=min(x, ft[i], scmp);
}

int qry(int i) {
	int r=-1;
	for(; i; i-=i&-i)
		r=min(ft[i], r, scmp);
	return r;
}

int main() {
	n=in();
	for(int i=0; i<n; ++i)
		x[i]=in(), y[i]=in();
	x[n]=x[0];
	y[n]=y[0];
	iota(b, b+n, 0);
	sort(b, b+n, pcmp);
	memset(tp, -1, 4*n);
	for(int i=0, j=0; i<n; i=j) {
		for(; j<n&&y[b[i]]*x[b[j]]==y[b[j]]*x[b[i]]; ++j) {
			c[b[j]]=i;
			if(tp[i]<0||x[b[j]]+y[b[j]]<x[tp[i]]+y[tp[i]])
				tp[i]=b[j];
		}
	}
	c[n]=c[0];
	for(int i=0; i<n; ++i) {
		e1[i]=i;
		e2[i]=i+1;
		if(c[e2[i]]<c[e1[i]])
			swap(e1[i], e2[i]);
		r[c[e2[i]]].push_back(i);
	}
	for(int i=n-1; ~i; --i) {
		for(int j : r[i])
			upd(c[e1[j]], j);
		int j=qry(i);
		if(~tp[i]&&(j<0||!cw(e1[j], e2[j], tp[i]))) {
			ans[tp[i]]=1;
			++a1;
		}
	}
	out(a1);
	putchar_unlocked('\n');
	for(int i=0; i<n; ++i) {
		if(ans[i]) {
			out(i+1);
			putchar_unlocked(' ');
		}
	}
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Incorrect 6 ms 5120 KB Output isn't correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 7 ms 5376 KB Output is correct
5 Correct 11 ms 5760 KB Output is correct
6 Correct 10 ms 5760 KB Output is correct
7 Correct 16 ms 6400 KB Output is correct
8 Correct 9 ms 5660 KB Output is correct
9 Incorrect 9 ms 5624 KB Output isn't correct
10 Correct 11 ms 5760 KB Output is correct
11 Correct 11 ms 5888 KB Output is correct
12 Incorrect 14 ms 6400 KB Output isn't correct
13 Correct 22 ms 7040 KB Output is correct
14 Incorrect 21 ms 7680 KB Output isn't correct
15 Incorrect 25 ms 8320 KB Output isn't correct
16 Incorrect 42 ms 11512 KB Output isn't correct
17 Correct 78 ms 11256 KB Output is correct
18 Incorrect 83 ms 17660 KB Output isn't correct
19 Incorrect 85 ms 17652 KB Output isn't correct
20 Execution timed out 162 ms 17168 KB Time limit exceeded