Submission #119359

#	Time	Username	Problem	Language	Result	Execution time	Memory
119359		tmwilliamlin168	Printed Circuit Board (CEOI12_circuit)	C++14	50 / 100	214 ms	18812 KiB

circuit

#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 / 100