Submission #119327

#	Time	Username	Problem	Language	Result	Execution time	Memory
119327		tmwilliamlin168	Printed Circuit Board (CEOI12_circuit)	C++14	95 / 100	157 ms	21512 KiB

circuit

#include <bits/stdc++.h>
using namespace std;

#define ll long long

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[18][mxN], tp[mxN];
array<ll, 2> a[mxN+1];
bool ans[mxN];

bool cw(int x, int y, int z) {
	return (a[z][1]-a[x][1])*(a[y][0]-a[x][0])<(a[y][1]-a[x][1])*(a[z][0]-a[x][0]);
}

bool pcmp(const int &i, const int &j) {
	return a[i][1]*a[j][0]<a[j][1]*a[i][0];
}

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]);
}

int main() {
	n=in();
	for(int i=0; i<n; ++i)
		a[i]={in(), in()};
	a[n]=a[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&&a[b[i]][1]*a[b[j]][0]==a[b[j]][1]*a[b[i]][0]; ++j) {
			c[b[j]]=i;
			if(tp[i]<0||a[b[j]][0]+a[b[j]][1]<a[tp[i]][0]+a[tp[i]][1])
				tp[i]=b[j];
		}
	}
	c[n]=c[0];
	memset(t, -1, sizeof(t));
	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]]);
			t[k][c[e1[i]]]=min(i, t[k][c[e1[i]]], scmp);
			t[k][c[e2[i]]-(1<<k)]=min(i, t[k][c[e2[i]]-(1<<k)], scmp);
		}
	}
	for(int i=17; i; --i) {
		for(int j=0; j<=n-(1<<i); ++j) {
			t[i-1][j]=min(t[i][j], t[i-1][j], scmp);
			t[i-1][j+(1<<i-1)]=min(t[i][j], t[i-1][j+(1<<i-1)], scmp);
		}
	}
	for(int i=0; i<n; ++i)
		if(~tp[i]&&(t[0][i]<0||!cw(e1[t[0][i]], e2[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(' ');
		}
	}
}

Compilation message (stderr)

circuit.cpp: In function 'int main()':
circuit.cpp:83:18: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    t[i-1][j+(1<<i-1)]=min(t[i][j], t[i-1][j+(1<<i-1)], scmp);
                 ~^~
circuit.cpp:83:50: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    t[i-1][j+(1<<i-1)]=min(t[i][j], t[i-1][j+(1<<i-1)], scmp);
                                                 ~^~

• Subtask 1: 95 / 100