Submission #119321

#	Time	Username	Problem	Language	Result	Execution time	Memory
119321		tmwilliamlin168	Printed Circuit Board (CEOI12_circuit)	C++14	80 / 100	958 ms	37368 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;
array<ll, 2> a[mxN+1];
vector<int> va[mxN], vr[mxN], vp[mxN];
bool ans[mxN];

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

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

struct scmp {
	__attribute__((always_inline)) bool operator()(const int &i, const int &j) const {
		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]);
	}
};
set<int, scmp> s;

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);
	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;
			vp[c[b[j]]].push_back(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]]) {
			va[c[e1[i]]].push_back(i);
			vr[c[e2[i]]].push_back(i);
		}
	}
	for(int i=0; i<n; ++i) {
		for(int j : vr[i])
			s.erase(j);
		for(int j : va[i])
			s.insert(j);
		int mj=-1;
		for(int j : vp[i])
			if(mj<0||a[j][0]+a[j][1]<a[mj][0]+a[mj][1])
				mj=j;
		if(~mj&&(!s.size()||!cw(e1[*s.begin()], e2[*s.begin()], mj)))
			ans[mj]=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:39:37: warning: always_inline function might not be inlinable [-Wattributes]
 __attribute__((always_inline)) bool pcmp(const int &i, const int &j) {
                                     ^~~~
circuit.cpp:35:37: warning: always_inline function might not be inlinable [-Wattributes]
 __attribute__((always_inline)) bool cw(int x, int y, int z) {
                                     ^~

• Subtask 1: 80 / 100