Submission #119336

#	Time	Username	Problem	Language	Result	Execution time	Memory
119336		tmwilliamlin168	Printed Circuit Board (CEOI12_circuit)	C++14	95 / 100	134 ms	12792 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];
vector<array<int, 2>> r[18];
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]);
}

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});
		}
	}
	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(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:84:14: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    memset(t[i&1^1], -1, 4*n);
             ~^~
circuit.cpp:86:8: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     t[i&1^1][j]=min(t[i&1][j], t[i&1^1][j], scmp);
       ~^~
circuit.cpp:86:35: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     t[i&1^1][j]=min(t[i&1][j], t[i&1^1][j], scmp);
                                  ~^~
circuit.cpp:87:8: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     t[i&1^1][j+(1<<i-1)]=min(t[i&1][j], t[i&1^1][j+(1<<i-1)], scmp);
       ~^~
circuit.cpp:87:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     t[i&1^1][j+(1<<i-1)]=min(t[i&1][j], t[i&1^1][j+(1<<i-1)], scmp);
                    ~^~
circuit.cpp:87:44: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     t[i&1^1][j+(1<<i-1)]=min(t[i&1][j], t[i&1^1][j+(1<<i-1)], scmp);
                                           ~^~
circuit.cpp:87:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     t[i&1^1][j+(1<<i-1)]=min(t[i&1][j], t[i&1^1][j+(1<<i-1)], scmp);
                                                        ~^~

• Subtask 1: 95 / 100