Submission #119342

#	Time	Username	Problem	Language	Result	Execution time	Memory
119342		tmwilliamlin168	Printed Circuit Board (CEOI12_circuit)	C++14	0 / 100	34 ms	16100 KiB

circuit

#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, t[2][mxN], tp[mxN];
long long x[mxN+1], y[mxN+1], dx[mxN], dy[mxN];
vector<array<int, 2>> r[18];
bool ans[mxN];

bool cw(int s, int p) {
	return (y[p]-y[e1[s]])*dx[s]<dy[s]*(x[p]-x[e1[s]]);
}

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(j, e2[i]):cw(i, e2[j]);
	return c[e1[i]]<c[e1[j]]?cw(i, e1[j]):!cw(j, e1[i]);
}

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]);
		if(c[e1[i]]<c[e2[i]]) {
			int k=31-__builtin_clz(c[e2[i]]-c[e1[i]]);
			r[k].push_back({c[e1[i]], i});
			r[k].push_back({c[e2[i]]-(1<<k), i});
			dx[i]=x[e2[i]]-x[e1[i]];
			dy[i]=y[e2[i]]-y[e1[i]];
		}
	}
	memset(t[1], -1, 4*n);
	/*
	for(int i=17; ~i; --i) {
		for(array<int, 2> a : r[i])
			t[i&1][a[0]]=min(a[1], t[i&1][a[0]], scmp);
		if(i) {
			memset(t[i&1^1], -1, 4*n);
			for(int j=0; j<=n-(1<<i); ++j) {
				t[i&1^1][j]=min(t[i&1][j], t[i&1^1][j], scmp);
				t[i&1^1][j+(1<<i-1)]=min(t[i&1][j], t[i&1^1][j+(1<<i-1)], scmp);
			}
		}
	}
	*/
	for(int i=0; i<n; ++i)
		if(~tp[i]&&(t[0][i]<0||!cw(t[0][i], tp[i])))
			ans[tp[i]]=1;
	for(int i=0; i<n; ++i)
		a1+=ans[i];
	out(a1);
	putchar_unlocked('\n');
	for(int i=0; i<n; ++i) {
		if(ans[i]) {
			out(i+1);
			putchar_unlocked(' ');
		}
	}
}

• Subtask 1: 0 / 100