Submission #119374

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

circuit

#pragma GCC optimize("unroll-loops")
#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, mxA=1e6;
int n, b[2][mxN], c[mxA+1], d[mxN+1], e1[mxN], e2[mxN], a1, t[2][mxN], tp[mxN];
long long x[mxN+1], y[mxN+1];
array<int, 3> a[mxN];
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 scmp(const int &i, const int &j) {
	if(i<0)
		return 0;
	if(j<0)
		return 1;
	if(e1[i]==e1[j])
		return d[e2[i]]<d[e2[j]]?!cw(e1[j], e2[j], e2[i]):cw(e1[i], e2[i], e2[j]);
	return d[e1[i]]<d[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();
		long long z1=y[i]*mxA*mxA/x[i]-mxA, z2=z1/mxA, z3=z2/mxA;
		a[i]={z1%mxA, z2%mxA, z3};
	}
	x[n]=x[0];
	y[n]=y[0];
	iota(b[0], b[0]+n, 0);
	for(int k=0; k<3; ++k) {
		memset(c+1, 0, 4*mxA);
		for(int i=0; i<n; ++i)
			++c[a[i][k]+1];
		for(int i=0; i<mxA; ++i)
			c[i+1]+=c[i];
		for(int i=n-1; ~i; --i)
			b[k&1^1][--c[a[b[k&1][i]][k]+1]]=b[k&1][i];
	}
	memset(tp, -1, 4*n);
	for(int i=0, j=0; i<n; i=j) {
		for(; j<n&&a[b[1][j]]==a[b[1][i]]; ++j) {
			d[b[1][j]]=i;
			if(tp[i]<0||x[b[1][j]]+y[b[1][j]]<x[tp[i]]+y[tp[i]])
				tp[i]=b[1][j];
		}
	}
	d[n]=d[0];
	for(int i=0; i<n; ++i) {
		e1[i]=i;
		e2[i]=i+1;
		if(d[e2[i]]<d[e1[i]])
			swap(e1[i], e2[i]);
		if(d[e1[i]]<d[e2[i]]) {
			int k=31-__builtin_clz(d[e2[i]]-d[e1[i]]);
			r[k].push_back({d[e1[i]], i});
			r[k].push_back({d[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:54:11: warning: narrowing conversion of '(z1 % 1000000)' from 'long long int' to 'int' inside { } [-Wnarrowing]
   a[i]={z1%mxA, z2%mxA, z3};
         ~~^~~~
circuit.cpp:54:19: warning: narrowing conversion of '(z2 % 1000000)' from 'long long int' to 'int' inside { } [-Wnarrowing]
   a[i]={z1%mxA, z2%mxA, z3};
                 ~~^~~~
circuit.cpp:54:27: warning: narrowing conversion of 'z3' from 'long long int' to 'int' inside { } [-Wnarrowing]
   a[i]={z1%mxA, z2%mxA, z3};
                           ^
circuit.cpp:66:7: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    b[k&1^1][--c[a[b[k&1][i]][k]+1]]=b[k&1][i];
      ~^~
circuit.cpp:93:14: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    memset(t[i&1^1], -1, 4*n);
             ~^~
circuit.cpp:95: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:95: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:96: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:96: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:96: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:96: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