답안 #119319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
119319 2019-06-21T02:45:41 Z tmwilliamlin168 Printed Circuit Board (CEOI12_circuit) C++14
40 / 100
100 ms 37748 KB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#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;
array<ll, 2> a[mxN+1];
vector<int> va[mxN], vr[mxN], vp[mxN];
bool tr[mxN], 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];
}

struct scmp {
	bool operator()(const int &i, const int &j) const {
		if(tr[i])
			return 1;
		if(tr[j])
			return 0;
		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]);
	}
};
priority_queue<int, vector<int>, scmp> pq;

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])
			tr[j]=1;
		for(int j : va[i])
			pq.push(j);
		while(pq.size()&&tr[pq.top()])
			pq.pop();
		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&&(!pq.size()||!cw(e1[pq.top()], e2[pq.top()], 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(' ');
		}
	}
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 14488 KB Output isn't correct
2 Correct 14 ms 14592 KB Output is correct
3 Correct 15 ms 14848 KB Output is correct
4 Correct 17 ms 14976 KB Output is correct
5 Incorrect 20 ms 15616 KB Output isn't correct
6 Incorrect 20 ms 15616 KB Output isn't correct
7 Incorrect 26 ms 16764 KB Output isn't correct
8 Incorrect 18 ms 15360 KB Output isn't correct
9 Correct 20 ms 15352 KB Output is correct
10 Incorrect 20 ms 15656 KB Output isn't correct
11 Incorrect 21 ms 15708 KB Output isn't correct
12 Correct 25 ms 16896 KB Output is correct
13 Incorrect 36 ms 17776 KB Output isn't correct
14 Correct 37 ms 19320 KB Output is correct
15 Correct 42 ms 20344 KB Output is correct
16 Correct 83 ms 26128 KB Output is correct
17 Execution timed out 101 ms 25624 KB Time limit exceeded
18 Execution timed out 142 ms 37748 KB Time limit exceeded
19 Execution timed out 142 ms 37744 KB Time limit exceeded
20 Execution timed out 214 ms 36632 KB Time limit exceeded