oj.uz

Submission #119316

# Submission time Handle Problem Language Result Execution time Memory
119316 2019-06-21T02:41:14 Z tmwilliamlin168 Printed Circuit Board (CEOI12_circuit) C++14
30 / 100
 100 ms 38120 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 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(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> pq1, pq2;

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])
			pq2.push(j);
		for(int j : va[i])
			pq1.push(j);
		while(pq1.size()&&pq2.size()&&pq1.top()==pq2.top()) {
			pq1.pop();
			pq2.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&&(!pq1.size()||!cw(e1[pq1.top()], e2[pq1.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(' ');
		}
	}
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 14464 KB Output isn't correct
2 Correct 14 ms 14592 KB Output is correct
3 Correct 17 ms 14848 KB Output is correct
4 Correct 18 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 27 ms 16768 KB Output isn't correct
8 Incorrect 19 ms 15360 KB Output isn't correct
9 Correct 22 ms 15360 KB Output is correct
10 Incorrect 23 ms 15616 KB Output isn't correct
11 Incorrect 21 ms 15744 KB Output isn't correct
12 Correct 33 ms 16896 KB Output is correct
13 Incorrect 41 ms 17920 KB Output isn't correct
14 Incorrect 43 ms 19444 KB Output isn't correct
15 Correct 77 ms 20472 KB Output is correct
16 Execution timed out 155 ms 26308 KB Time limit exceeded
17 Execution timed out 124 ms 25904 KB Time limit exceeded
18 Execution timed out 319 ms 38120 KB Time limit exceeded
19 Execution timed out 309 ms 38080 KB Time limit exceeded
20 Execution timed out 278 ms 37224 KB Time limit exceeded