oj.uz

Submission #119359

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

#define getchar_unlocked getchar
#define putchar_unlocked putchar

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 7 ms 5376 KB Output is correct
4 Correct 8 ms 5376 KB Output is correct
5 Correct 12 ms 5732 KB Output is correct
6 Correct 12 ms 5760 KB Output is correct
7 Correct 20 ms 6528 KB Output is correct
8 Correct 10 ms 5632 KB Output is correct
9 Incorrect 9 ms 5632 KB Output isn't correct
10 Correct 11 ms 5760 KB Output is correct
11 Correct 12 ms 5888 KB Output is correct
12 Incorrect 14 ms 6528 KB Output isn't correct
13 Correct 27 ms 7288 KB Output is correct
14 Incorrect 24 ms 8056 KB Output isn't correct
15 Incorrect 26 ms 8824 KB Output isn't correct
16 Incorrect 50 ms 12456 KB Output isn't correct
17 Correct 89 ms 12352 KB Output is correct
18 Incorrect 95 ms 18812 KB Output isn't correct
19 Incorrect 98 ms 18812 KB Output isn't correct
20 Execution timed out 214 ms 18424 KB Time limit exceeded