oj.uz

Submission #119367

# Submission time Handle Problem Language Result Execution time Memory
119367 2019-06-21T06:03:57 Z tmwilliamlin168 Printed Circuit Board (CEOI12_circuit) C++14
45 / 100
 100 ms 19340 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[e1[i]]].push_back(i);
	}
	for(int i=0; i<n; ++i) {
		for(int j : r[i])
			upd(n-1-c[e2[j]], j);
		int j=qry(n-1-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
45.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 7 ms 5248 KB Output is correct
4 Incorrect 8 ms 5376 KB Output isn't correct
5 Correct 11 ms 5760 KB Output is correct
6 Correct 10 ms 5760 KB Output is correct
7 Correct 16 ms 6528 KB Output is correct
8 Correct 9 ms 5632 KB Output is correct
9 Incorrect 8 ms 5632 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 13 ms 6528 KB Output isn't correct
13 Correct 22 ms 7296 KB Output is correct
14 Incorrect 22 ms 7936 KB Output isn't correct
15 Incorrect 24 ms 8704 KB Output isn't correct
16 Incorrect 43 ms 12280 KB Output isn't correct
17 Correct 74 ms 12152 KB Output is correct
18 Incorrect 81 ms 19192 KB Output isn't correct
19 Incorrect 93 ms 19340 KB Output isn't correct
20 Execution timed out 174 ms 18808 KB Time limit exceeded